# “Functionalizing” this tree walking method and cleaning it up

I have a MessageTree class that represents a binary tree of negative/positive. I'm looking to improve my walkTree method and make it more functional and succinct. Right now the try/catch is kind of ugly.

The goal is to feed an array of "steps" (Array[Boolean]) that indicate whether to walk right or left through each node. If the number of steps exceeds the number of available children, it simply returns None.

Here's what I've got:

case class MessageTree(
val value: String,
val negative: Option[MessageTree] = None,
val positive: Option[MessageTree] = None

) {

/**
* Walk the node using a boolean input.
* @param step
* @return
*/
def walk(step: Boolean): Option[MessageTree] = {
step match {
case true => this.positive
case false => this.negative
}
}
}

object MessageTree {

/**
* Walk the tree and retrieve a child using a sequence of boolean steps.
* @param tree
* @param steps
* @return
*/
def walkTree(tree: MessageTree, steps: Array[Boolean]): Option[MessageTree] = {
var walks = 0
var node: Option[MessageTree] = Some(tree)

try {
while (walks < steps.size) {
node = node.get.walk(steps(walks))
walks += 1
}
} catch {
case e: Throwable =>
node = None
}

node
}
}

• Why are you using booleans? Is the choice of placing a message into the tree entirely arbitrary or is there some clear rule for how a tree should grow based on the state of the tree and or the content of the message? If there is a clear rule, booleans are probably not appropriate. – itsbruce Jan 13 '15 at 11:47
• It would help to know what the messages are for, what their content is about, how you intend to retrieve the messages, whether each message is unique or if each will be associated with a unique key. – itsbruce Jan 14 '15 at 8:48

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 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:

1. In the companion object. In this case, functions should use pattern matching to decide what is the appropriate option for the particular case class.
2. 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:

1. You should now have enough knowledge to create an Option 2 style walk, if you think hard enough.
2. 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:

• I saw your comment on @amon's response. Agreed that Boolean is not the best type, since it defeats the purpose of direction on a tree. What about using the built-in scala.util.Left and Right? Also, because this class is designed to deal only with String messages and is purpose-specific, I'm curious do I gain more by still opening it up to any type? Thanks! – crockpotveggies Jan 14 '15 at 7:45
• About left/right... I'm not sure you need Left/Right at all. Trees are usually designed to decide automatically where to store each added value. This may be done based on the current state of the tree (and possibly the value being added) or on a key associated with the value (as in a Trie). Why do you feel you have to specify the precise placement of each message? You don't care about the internal layout of a Map when you add or retrieve items. Will left/right/left mean anything at all to the rest of your application? How do you intend to retrieve the keys? – itsbruce Jan 14 '15 at 8:35
• About generic structures... I often make structures generic even if I know I plan to use them for one type. The code is slightly less verbose and helps with separation of concerns - if I don't specify String, the storage class only knows about the mechanics of storage and isn't polluted with details of string representation. Specifying a specific type is easily and permanently done when a variable is declared. And if I suddenly find I need to store not a string but a message object (with a little extra info about the message), no change to the tree code. Bonus. – itsbruce Jan 14 '15 at 8:42
• I might decide not to allow variance, depending on the context. – itsbruce Jan 14 '15 at 8:46
• Doing it that way hides internal tree implementation details (which you may change later without breaking external code that uses the tree). It also makes the apply method much easier to write, since it just needs a list of messages as input, over which it can recurse/fold to add each message in turn. – itsbruce Jan 14 '15 at 13:45

In your walk method, you have this code:

step match {
case true => this.positive
case false => this.negative
}


Matching on a boolean is very unusual since you could have simply used a conditional instead:

if (step)
this. positive
else
this.negative


But this looks really weird: this method is called walk and not shouldIGetThePositiveChildNode. In particular, I'd expect a direction and not a boolean that's implicitly used to denote a direction. It would be generally preferable to leverage the type system to bring your code closer to the problem domain:

sealed abstract class Direction
object Left extends Direction
object Right extends Direction


Then the pattern match you started with makes sense again:

direction match {
case Right => this.positive
case Left => this.negative
}


Also, your walkTree method would receive an Array[Direction].

Another thing that bothered me is the main logic of your tree walk. You are essentially reimplementing Traversable.foldLeft and Option.flatMap (and quite inefficiently so since you're using exceptions). This line should be equivalent, although it's a bit more difficult to understand.

val root: Option[Tree] = Some(tree)
(steps foldLeft root)((t, direction) => t flatMap (_ walk direction))

• @crockpotveggies , this has the ADT for Right/Left that I was talking about. – itsbruce Jan 13 '15 at 12:21
• Very helpful, and I agree using the foldLeft is a lot more elegant. Since you've implemented the directional left/right, is there any reason I shouldn't consider using the built-in classes such as scala.util.Left and scala.util.Right? – crockpotveggies Jan 14 '15 at 7:40
• @crockpotveggies Thanks. Don't use scala.util.Left because that is an instance of the Either type which represents a type union, not a direction. – amon Jan 14 '15 at 9:03
• @amon noticed a compiler issue with your foldLeft flatMap line, is it Scala 2.10 or 2.11? type mismatch; found : Option[MessageTree] required: Some[MessageTree] – crockpotveggies Jan 15 '15 at 18:36
• @crockpotveggies you're right, the type inference goes wrong here. I fixed it in the answer by using an explicit type annotation. We could also have supplied the type parameter explicitly steps.foldLeft[Option[Tree]](Some(tree))(...) or could have used a different way to create the default value: (steps foldLeft Option(tree)) (which does a null-check). (I am using Scala 2.10, but didn't test the the code before submitting my answer since I wrote it on a mobile device) – amon Jan 15 '15 at 20:53