anch anch - 2 months ago 17x
Scala Question

Tail recursive functions for BinaryTree

I am stuck with implementing tail recursive foreach, reduce, map and toList functions for a very simple implementation of binary tree.

sealed trait Tree[+A]
case object EmptyTree extends Tree[Nothing]
case class Node[A](value: A, left: Tree[A], right: Tree[A]) extends Tree[A]

object Tree {

def apply[A]: Tree[A] = EmptyTree
def apply[A](value: A): Tree[A] = Node(value, EmptyTree, EmptyTree)
def apply[A](value: A, left: Tree[A], right: Tree[A]): Tree[A] = Node(value, left, right)

def foreach[A](tree: Tree[A], f: (A) => Unit): Unit = {
def iter[A](tree: Tree[A], f: (A) => Unit): Unit = tree match {
case EmptyTree =>
case Node(v, l, r) =>
iter(l, f)
iter(r, f)
iter(tree, f)

def reduce[A](tree: Tree[A], value: A, f: (A, A) => A): A = {
def loop(tree: Tree[A], value: A): A = tree match {
case Node(v, l, r) => loop(l, f(loop(r, value), v))
case EmptyTree => value
loop(tree, value)

def map[A, B](tree: Tree[A], f: A => B): Tree[B] = {
def iter[A](tree: Tree[A], f: A => B): Tree[B] = tree match {
case Node(v, l, r) => Node(f(v), iter(l, f), iter(r, f))
case EmptyTree => EmptyTree
iter(tree, f)

def toList[A](t: Tree[A]): List[A] = {
def iter[A](t: Tree[A]): List[A] = t match {
case Node(v, l, r) => v :: iter(l) ::: iter(r)
case EmptyTree => List.empty

Code for testing:

val tree = Tree(1, Tree(2, Tree(3), Tree(4)), Tree(5, Tree(6), Tree(7)))
Tree.foreach(tree, (x: Int) => println(x))
Tree.reduce(tree, 0, (x: Int, y: Int) => x + y), (x: Int) => x + 1)

I cant use @tailrec attribute because as you can see, recursive calls are not the last calls in a function, and I do not know how to rewrite it because there are several calls in one function, for example

v :: iter(l) ::: iter(r)

I know that I can use accumulator for inner recursive functions but how I should use it in case of several calls ?

Thanks in advance.


def toListRec[A](tree: Tree[A]): List[A] = {
def iter(result: List[A], todo: List[Tree[A]]): List[A] = todo match {
case x :: tail => x match {
case Node(v, l, r) => iter(v :: result, l :: r :: tail)
case EmptyTree => iter(result, tail)
case Nil => result.reverse
iter(List.empty, List(tree))


Without tail recursion, a(/the) stack is used to keep track of calling functions. If you want to use tail recursion, you'll have to find a way to keep track of this information elsewhere. In simpler "linear" cases, such as factorial, this information is pretty limited and can often easily be taken care of by using an accumulator.

In your case, the problem is that the recursion isn't linear. After one recursive call, the function doesn't just compute the result, but it makes another recursive call before being able to get to the result.

In order to apply tail recursion in this case, you will have to explicitly keep track of the remaining recursive calls that have to be made. An easy way is to simply keep a "to-do" list. For example:

def toList[A](t: Tree[A]): List[A] = {
  @tailrec def iter[A](todo: List[Tree[A]], r: List[A]): List[A] =
  todo match {
    case t :: rest => t match {
      case Node(v, l, r) => iter(l :: r :: rest,  v :: r)
      case EmptyTree => iter(rest, r)
    case List.empty => reverse(r)
  iter(List(t), List.empty)

Disclaimer: I know nothing about scala. :)