You have selected the right tool (case classes) but are not using it properly. In functional programming, a tree is an Algebraic Data Type. In Scala, these are constructed with case classes but this is done with a sealed base trait (or abstract class) and a set of case classes which represent the different states/components of the type. Here is how yours might look:
sealed abstract class CrockPotTree[+A]
case object Empty[A] extends CrockPotTree[Nothing]
case class Node[A](value: A, negative: CrockPotTree[A],
positive: CrockPotTree[A]) extends CrockPotTree[A]
Now all I need do is create functions which can add to, prune or walk the tree. These will do so recursively, using pattern matching to do the appropriate thing depending on the type of the node. There is more than one way to do this, but first let me say a few things about the example code above:
- I used a sealed abstract as the base. This class can only be used within this module and not elsewhere. This means code for walking/fetching/manipulating CrockPotTrees will not fail because somebody extended the class and added something crazy and unpredictable. It is abstract because only the derivative case classes have meaningful state (Empty, not Empty etc).
- I could have used a trait. There are still different opinions about this.
- I have made it generic: CrockPotTree[+A] rather than CrockPotTree[String], so it can hande all types of objects. You can use it (once an apply method has been added to the companion object) to create a CrockPotTree[String] or CrockPotTree[Int] or whatever.
- I have made it covariant (CrockPotTree[+A] rather than CrockPotTree[A]). This opens the possibility that if you add a Bear value to a tree full of Wolf objects, you will get back a CrockPotTree[Animal] rather than a simple error.
- There is no need for Option[CrockPotTree] because of the Empty crockpot type. I will explain later.
Now, the functions that work should be recursive (or fold over a path through the tree, which is a kind of recursion). Why? Because this is a recursive data type. The first point to consider about this is that your steps type in WalkTree is wrong. It is almost certainly better to have it a list than an array. That way, each recursive iteration of walkTree can look something like this:
steps match {
Case Nil => // Return Some(value) if this is a Node or Nothing if it is an Empty
Case x :: xs => walkTree(walk(x), xs)
}
Note how walkTree still returns Option[value] even though Option[CrockPotTree] is no longer part of the structure.
Using the list is both faster and simpler than using an array. That said, the next important question is where to put these functions. You have 2 basic choices:
- In the companion object. In this case, functions should use pattern matching to decide what is the appropriate option for the particular case class.
- Abstract methods defined in the abstract class (where appropriate) and concrete implementations in the case classes.
(If you use a trait rather than abstract class, you also have the choice of making some functions concrete in the parent trait).
Option 1 is the functional approach as seen in functional languages which don't offer OO. I've written tree types in Haskell code and that's just how it is done there. Option 2 is more OO (pattern matching goes away because each case class knows how to deal with itself) while still being good functional code if you do it right. Option 2 is the way most functions in the Scala collections library are done.
Ironically, your function is very much Option 1 style despite the fact that you put it into the class. It could be moved into the companion object with almost no modification, because it doesn't use polymorphism properly.
Since I have already given an example of how walkTree would look in Option 1 style (which is how your code is effectively done), here's how some simple functions would be done Option 2 stylee:
sealed abstract class CrockPotTree[+A] {
def isEmpty: Boolean
def size: Int
}
case object Empty[A] extends CrockPotTree[Nothing] {
def isEmpty = true
def size = 0
}
case class Node[A](value: A, negative: CrockPotTree[A],
positive: CrockPotTree[A]) extends CrockPotTree[A] {
def isEmpty = false
def size = positive.size + negative.size + 1
/* This implementation of size is *not* tail recursive
* and could create a stack overflow. There is a better
* way to do it but this way is chosen for simplicity here
*/
}
Now, despite my warning about the stack overflow risk, look at the size function. It works because an empty tree will return a size of zero. A non-empty tree will add 1 (for itself) to the combined sizes of its positive and negative trees. I want to make two points about this:
- You should now have enough knowledge to create an Option 2 style walk, if you think hard enough.
- This is why we seal algebraic data types so they cannot be extended. My size function knows that the answer will always be 0 or more, because there are only two CrockPotTree types and they both return a proper value. If some idiot added an new case class which returned something else (null, for example), things could explode.
My final two observations...
Firstly, you should have an apply function in the companion object, so that you could create a CrockPotTree like this
val cpt = CrockPotTree(values)
where values is some collection of booleans and values which CrockPotTree will know how to build into a tree. the apply function would need to call an append function recursively. In Option 2 style, Empty and Node classes would both have their own recursive append function.
Secondly, I am not at all sure that Boolean is an appropriate type here. You might want to create your own binary type (if that really is appropriate for this tree structure). Guess what? It would also be an ADT (algebraic data type).
I leave you with some useful links:
