Scala n-arity树尾递归评估

Question

我有一个树结构，比二叉树结构更通用

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]

如您所见，它可以有任意数量的分支。

我正在尝试使评估方法成为尾递归的，但我做不到。

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)))
}

如何手动保存堆栈？

Answer 1

如果每个 Node 可以容纳不同的 op 那么，不，我不认为尾递归是可能的。

另一方面，如果您可以将所有 Leaf.value 提供给一个 op，那么这可能是可能的。

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))
  }
}

我无法编译它，因为我没有 Terminal 和 Function 的定义，但它应该是解决问题的一种方法的合理概述。

Answer 2

实际上这是可能的，使用深度优先搜索。

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))
}

Scala n-arity树尾递归评估

scala n-arity tree tail recursive evaluation

tree

recursion

scala

tail-recursion