LIBRENEITOR

Create a functor for a binary tree in Scala

Wed, Jul 17, 2019

How to create a functor in Scala without using recursion. And how to do the same with deferred evaluation.

I’m trying to really really understand the scala cats library. So while I was reading the book “Scala with Cats”, I found an exercise which told me to: create a functor for a binary tree:

sealed trait Tree[+A]

final case class Branch[A](left: Tree[A], right: Tree[A])
  extends Tree[A]

final case class Leaf[A](values: A) extends Tree[A]

The most immediate solution is to use recursion. In this way, the solution is extremely simple:

override def map[A, B](tree: Tree[A])(func: A => B): Tree[B] = {
  tree match {
    case Branch(left, right) =>
      Branch(map(left)(func),  map(right)(func))
    case Leaf(value) =>
      Leaf(func(value))
  }
}

But I felt that this code won’t scale well in a practical scenario for very deep trees. So, I decided I will use my knowledge of data structures in C++ to do this. But it wasn’t that easy. I found many problems:

I wasted many hours trying to resolve the problem using stacks. But the code was so complex that I couldn’t even verify the logic without debugging. For me that is not a real solution. I also tried very hard to avoid the creation of any auxiliary data structure, but I found my self making my code even harder to read.

After some thinking I decided that I needed this class:

case class Node[A,B](var value: Tree[A],
                     var parent: Option[Node[A,B]] = None,
                     var output: Option[Tree[B]] = None,
                     var vars: List[Tree[B]] = List())

Variable explanations:

I know that you may be thinking that I shouldn’t be using vars for the Node class. But because my real objective was to support arbitrary deep trees, I believe that is a good trade-off. Also the Node can be private.

The map function for the Tree functor is this:

override def map[A, B](inputTree: Tree[A])(func: A => B): Tree[B] = {
  var current = Node[A,B](value = inputTree)
  while(!(current.parent.isEmpty && current.output.isDefined)){
    current match {
      case Node(_, Some(parent), Some(mapedResult), _) =>
        parent.vars = mapedResult :: parent.vars
        current = parent
      case Node(_, _, _, right :: left :: _) =>
        current.output = Branch(left, right).some
      case Node(Leaf(leafVal), _, _, _) =>
        current.output = Leaf(func(leafVal)).some
      case Node(Branch(left, _), _, _, List()) =>
        current = Node(left, current.some)
      case Node(Branch(_, right), _, _, List(_)) =>
        current = Node(right, current.some)
    }
  }
  current.output.get
}

It has mutation inside the function, but it’s minimal and self-contained. You can even have the Node class inside the map function is you wanted.

Trampoline

I found a little bit difficult to read the non-recursive version of the functor. After all, is an algorithm that is recursive by nature. Also, you may be forced to do it recursively or functionally anyways.

Welcome to cats defer. It allows us to have stack safety.

def deferredMap[A,B](tree: Tree[A])(func: A => B): Eval[Tree[B]] = {
  tree match {
    case Leaf(value) => Eval.now(Leaf(func(value)))
    case Branch(left, right) => for {
      mappedLeft  <- Eval.defer(deferredMap(left)(func))
      mappedRight <- Eval.defer(deferredMap(right)(func))
      mapped      <- Eval.now(Branch(mappedLeft, mappedRight))
    } yield mapped
  }
}

This is much simpler than the previous version with a mutable data structure. The only problem is that: is harder to come up with this solution in the first place. This requires you to know cats and also the eval monads.

If I didn’t use Eval.defer, a stack-overflow would have happened. You may be thinking about using Eval.later, but it doesn’t work. later is just like a lazy val, it will blow your stack when you call .value.

Testing it

I thought that the best way to test if these function aren’t really consuming my stack is to create a really nested map in the first place. And I didn’t want to test my knoledge in mutable data structures again so I used Eval again to create a random function that generates a tree of a given depth.

def branchRandomSwap[A](a: Tree[A], b: Tree[A]): Tree[A] =
  if(math.random() > 5) branch(a, b) else branch(b, a)

def random(n: BigInt): Eval[Tree[Float]] =
  n > 1 match {
    case true =>
      for {
        elem1 <- Eval.defer(random(n-1))
        elem2 <- Eval.now(leaf(2f))
        branch <- Eval.now(branchRandomSwap(elem1, elem2))
      } yield branch
    case false =>
      Eval.now(Leaf(1f))
  }

If you do everything correctly the following code shouldn’t crash:

val randomTree = random(100000).value
randomTree.map(_*2)