CODEWITHSUNDEEP
scalacase-classtraits
Kevin Meredith
Kevin Meredith

Reputation: 41939

Instantiating Case Class with Trait

How can I instantiate a Tree per the below trait and case classes?

sealed trait Tree[+A] 
case class Leaf[A](value: A) extends Tree[A]
case class Branch[A](left: Tree[A], right: Tree[A]) extends Tree[A]

Source: Functional Programming in Scala

Example: How would I code the following tree of type String?

           "top"
          /     \
  "middle-left"    "middle-right"
       /          \
  "bottom-left"   "bottom-right"

Upvotes: 1

Views: 1053

Answers (2)

stefan.schwetschke
stefan.schwetschke

Reputation: 8932

Short answer

You can't. Your data structure is built in a way that it can only hold data in the leafs, but not in the inner nodes.

Long answer

You have here a monadic tree. This tree can only store values in its leafs, but it has a very nice property: When the value is again a monadic tree (sou you have a tree in a tree), you can flatten the construct out, so you can get a tree again.

"Proof" in Haskell (because type classes are a little bit strange in Scala) for being monadic:

data Tree a = Leaf a | Branch (Tree a) (Tree a)

instance Monad Tree where
   return = Leaf
   Leaf a >>= f = f a
   Branch l r >>= f = Branch (l >>= f) (r >>= f)

OK, it's not a full proof, until I show that the mondic laws hold for this type class. But I think you can see the idea.

Upvotes: 2

Shadowlands
Shadowlands

Reputation: 15074

With the class hierarchy as you have given it you wouldn't be able to create something properly resembling the example tree you want, because Branch can only accept left and right sub-trees, not a value (the text "top").

If you want the branch nodes to also have a value, I would modify your class hierarchy as follows:

sealed trait Tree[+A]
case class Leaf[A](value: A) extends Tree[A]
case class Branch[A](value: A, left: Option[Tree[A]] = None, right: Option[Tree[A]] = None) extends Tree[A]

Note the Option-al nature of the sub-trees, with a default of None, allowing for missing left or right sub-trees without resorting to nulls.

Your example tree could then be generated as follows:

val tree = Branch("top",
                  Some(Branch("middle-left", Some(Leaf("bottom-left")))),
                  Some(Branch("middle-right", right = Some(Leaf("bottom-right")))))

Upvotes: 2

Related Questions