CODEWITHSUNDEEP
scalatypesfunctional-programming
Omid
Omid

Reputation: 1989

How to define a tree data structure that has edge type

I want to define a tree datastructure that has a label for its edges, here is my initial thought:

sealed trait Tree[+N,+E]
case class Branch[N,E](value:N, children:Map[E, Tree[N,E]]) extends Tree[N,E]
case class Leaf[N](value:N) extends Tree[N, Unit]

As you may guess, if I make a tree instance like following, the type of the instance would be Tree[Int, Any]. I also don't want to have a contravariant type for E. 

  val tree =
    Branch(0,
      Map(
        "a" -> Leaf(1),
        "b" -> Branch(2,
          Map(
            "c" -> Leaf(4))))
    )

I want to know what would be a better way to implement this Tre. I've heard of Fix type classes and recursion schemes but I don't know if they can be useful here.

Upvotes: 0

Views: 250

Answers (1)

Joe K
Joe K

Reputation: 18424

Have Leaf extend Tree[N, Nothing], not Tree[N, Unit]. Nothing is a bottom type, so that means Leaf[N] will be a subtype of Tree[N, E] for any E since you have it covariant.

case class Leaf[N](value:N) extends Tree[N, Nothing]

With that change, your example tree definition works just fine.

Fixpoint types are more complicated but not always necessary. But you could certainly modify this to make use of them. If you do want to go down that road, it might be better to ask it as another more specific question.

Upvotes: 1

Related Questions