"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 
        node = None
    }

    node
  }
}

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

StackExchange Code Review Q#77361, answer score: 3