scala n-arity tree tail recursive evaluation

Question

I have a Tree structure, which is more general than a binary tree structure

sealed trait Tree[+A]

case class Leaf[A](value: Terminal[A]) extends Tree[A]
case class Node[A](op: Function[A], branches: Tree[A]*) extends Tree[A]

As you see, it can have a arbitrary number of branches.

I'm trying to make an evaluation method to be tail recursive but i'm not being able to do it.

def evaluateTree[A](tree: Tree[A]): A = tree match {
  case Leaf(terminal) => terminal.value
  case Node(op: Function[A],  args @ _*) => op.operator((for (i <- args) yield evaluateTree(i)))
}

How can i save the stack manually?

Answer 1

Actually it was possible, using deep first search.

def evaluateTree[A](tree: Tree[A]): A = {
  @tailrec
  def evaluateWhile[C](l: List[Function[C]], arguments: List[List[C]], n_args: List[Int], f: Int => Boolean, acc: C): (List[Function[C]], List[List[C]], List[Int]) =
    n_args match {
      case h :: t if f(h) =>
        evaluateWhile(l.tail, arguments.tail, n_args.tail, f, l.head.operator(arguments.head ::: List(acc)))
      case h :: t  =>
        (l, (List(acc) ::: arguments.head) :: arguments.tail,  List(n_args.head - 1) ::: n_args.tail)
      case _ =>
        (l, List(acc) :: arguments, n_args)
    }
  @tailrec
  def DFS(toVisit: List[Tree[A]], visited: List[String] = Nil, operators: List[Function[A]] = Nil, arguments: List[List[A]] = Nil, n_args: List[Int] = Nil, debug: Int = 0): A = toVisit match {
    case Leaf(id, terminal) :: tail if !visited.contains(id) => {
      val (operators_to_pass, args_to_pass, n_args_to_pass) =
        evaluateWhile[A](operators, arguments, n_args, x => x == 1, terminal.value)
      DFS(toVisit.tail, visited ::: List(id), operators_to_pass, args_to_pass, n_args_to_pass, debug + 1)
    }
    case Node(id, op, args @_*) :: tail if !visited.contains(id) => {
      DFS(args.toList ::: toVisit.tail, visited ::: List(id), op :: operators, List(Nil) ::: arguments, List(args.length ) ::: n_args, debug + 1)
    }
    case _ => arguments.flatten.head
  }
  DFS(List(tree))
}

Answer 2

If each Node can hold a different op then, no, I don't think tail recursion is possible.

If, on the other hand, you can feed all the Leaf.values to a single op then it might be possible.

def evaluateTree[A](tree: Tree[A]): A = {
  @tailrec
  def allValues(branches: Seq[Tree[A]], acc: Seq[A] = Seq()): Seq[A] =
    if (branches.length < 1) acc
    else branches.head match {
      case Leaf(term) => allValues(branches.tail, term.value +: acc)
      case Node(_, args: Seq[Tree[A]]) => allValues(branches.tail ++ args, acc)
    }

  tree match {
    case Leaf(terminal) => terminal.value
    case Node(op: Function[A], args: Seq[Tree[A]]) => op.operator(allValues(args))
  }
}

I can't compile this as I don't have definitions for Terminal and Function, but it should be a reasonable outline of one approach to the problem.