Scala tree recursive shift method

Question

Given the following definition for a (non-binary) tree:

sealed trait Tree[+A] case class Node[A](value: A, children: List[Node[A]]) extends Tree[A] object Tree {...} 

I wrote the following fold method:

 def fold[A, B](t: Node[A])(f: A ⇒ B)(g: (B, List[B]) ⇒ B): B = g(f(t.value), t.children map (fold(_)(f)(g))) 

which can be well used for (among other things) this map method:

 def map[A, B](t: Node[A])(f: A ⇒ B): Node[B] = fold(t)(x ⇒ Node(f(x), List()))((x, y) ⇒ Node(x.value, y)) 

Question: can someone help me in writing a tail recursive version above fold ?

Answer 1

I believe you need a stack for such a workaround, as in imperative programming, there would be no natural way to write this without a recursive method. Of course, you can always manage the stack yourself, which moves it to the heap and prevents stack overflows. Here is an example:

 sealed trait Tree[+A] case class Node[+A](value: A, children: List[Node[A]]) extends Tree[A] case class StackFrame[+A,+B]( value: A, computedChildren: List[B], remainingChildren: List[Node[A]]) def fold[A,B](t: Node[A])(f: A => B)(g: (B, List[B]) => B) : B = { def go(stack: List[StackFrame[A,B]]) : B = stack match { case StackFrame(v, cs, Nil) :: tail => val folded = g(f(v), cs.reverse) tail match { case Nil => folded case StackFrame(vUp, csUp, remUp) :: rest => go(StackFrame(vUp, folded::csUp, remUp)::rest) } case StackFrame(v, cs, nextChild :: others) :: tail => go( StackFrame(nextChild.value, Nil, nextChild.children) :: StackFrame(v, cs, others) :: tail) case Nil => sys.error("Should not go there") } go(StackFrame(t.value, Nil, t.children) :: Nil) } 

Note. I made Node covariance, and not strictly necessary, but if it is not, you need to be explicit in the multiple Nil type (for example, replace with List[X]() ) in some place.

go it is clearly tail recursive, but only because it controls the stack itself.

You can find a more fundamental and systematic technique (but not so easy to understand at the beginning) based on continuations and trampolines, in this nice blog post .