在Scala中制作递归代码，尾部递归

Question

我想将代码更改为尾部递归，以免溢出堆栈表达式是标签或树的ADT

def combine[A](expression: Expression, runners: List[Runner[A]]): Runner[A] = {
val labelToHashmap = runners.map(runner=> (runner.label.get, runner)).toMap
def reduceExpression(e: Expression): Runner[A] = {
e match {
case Label(_, value) => labelToHashmap(value)
case Tree(_, operation, left, right) =>
operation match {
case AND =>  reduceExpression(left).and(reduceExpression(right))
case OR => reduceExpression(left).or(reduceExpression(right))
}
}
}
reduceExpression(expression)
}

如何将上面的代码转换为尾部递归代码？

Answer 1

您可以像Kolmar所展示的那样，以尾部递归的方式重写函数，它就会起作用。但我认为这通常会掩盖算法的意图，因为现在你必须摆弄一个通常是隐式的显式堆栈。

我想说，最好将堆栈中的篡改比特考虑到可重复使用的数据结构中并使用它。CCD_ 1类型就是这样一种数据结构。

import cats.Eval
import cats.syntax.all._
def combine[A](
expression: Expression,
runners: List[Runner[A]]
): Runner[A] = {
val labelToHashmap = runners.fproductLeft(_.label.get).toMap
def reduceExpression(e: Expression): Eval[Runner[A]] =
Eval.now(e).flatMap {
case Label(_, value) => labelToHashmap(value)
case Tree(_, operation, left, right) =>
operation match {
case AND =>
(
reduceExpression(left),
reduceExpression(right)
).mapN(_ and _)
case OR =>
(
reduceExpression(left),
reduceExpression(right)
).mapN(_ or _)
}
}
reduceExpression(expression).value
}

正如您所看到的，这基本上保留了直接递归实现的逻辑，但由于Eval的value方法的实现方式，它仍然是堆栈安全的。

另请查看文档：https://typelevel.org/cats/datatypes/eval.html

Answer 2

正如@JörgWMittag所评论的，要处理具有尾部递归的树，必须转换计算，最直接的方法是模拟调用堆栈并将其传递给递归调用：

def combine[A](expression: Expression, runners: List[Runner[A]]): Runner[A] = {
val labelToRunner = runners.map(runner => (runner.label.get, runner)).toMap

sealed trait Element
case class Op(operation: Operation) extends Element
case class Expr(expression: Expression) extends Element
case class Result(runner: Runner[A]) extends Element
@tailrec
def reduce(stack: List[Element]): Runner[A] = {
def expand(expression: Expression): List[Element] = expression match {
case Label(_, value) =>
List(Result(labelToRunner(value)))
case Tree(_, operation, left, right)=>
List(Expr(left), Expr(right), Op(operation))
}
stack match {
case List(Result(runner)) => runner
case Expr(expression) :: rest =>
reduce(expand(expression) ::: rest)
case (left @ Result(_)) :: Expr(expression) :: rest =>
// The subtree we are processing is put on the top of the stack
// Thus when the operation is applied the elements are in reverse order
reduce(expand(expression) ::: left :: rest)
case Result(right) :: Result(left) :: Op(operation) :: rest =>
val combined = operation match {
case AND => left.and(right)
case OR => left.or(right)
}
reduce(Result(combined) :: rest)
}
}
reduce(List(Expr(expression)))
}

打印出该函数的跟踪，看看它是如何首先扩展表达式、将简单表达式转换为结果以及应用操作的，这很有趣。例如，这里是带有数字标签的模拟运行器上的一些表达式的堆栈：

Expr(((1 AND (2 OR 3)) OR 4) AND ((5 OR 6) AND 7))
Expr((1 AND (2 OR 3)) OR 4), Expr((5 OR 6) AND 7), Op(AND)
Expr(1 AND (2 OR 3)), Expr(4), Op(OR), Expr((5 OR 6) AND 7), Op(AND)
Expr(1), Expr(2 OR 3), Op(AND), Expr(4), Op(OR), Expr((5 OR 6) AND 7), Op(AND)
Result(1), Expr(2 OR 3), Op(AND), Expr(4), Op(OR), Expr((5 OR 6) AND 7), Op(AND)
Expr(2), Expr(3), Op(OR), Result(1), Op(AND), Expr(4), Op(OR), Expr((5 OR 6) AND 7), Op(AND)
Result(2), Expr(3), Op(OR), Result(1), Op(AND), Expr(4), Op(OR), Expr((5 OR 6) AND 7), Op(AND)
Result(3), Result(2), Op(OR), Result(1), Op(AND), Expr(4), Op(OR), Expr((5 OR 6) AND 7), Op(AND)
Result(2 OR 3), Result(1), Op(AND), Expr(4), Op(OR), Expr((5 OR 6) AND 7), Op(AND)
Result(1 AND (2 OR 3)), Expr(4), Op(OR), Expr((5 OR 6) AND 7), Op(AND)
Result(4), Result(1 AND (2 OR 3)), Op(OR), Expr((5 OR 6) AND 7), Op(AND)
Result((1 AND (2 OR 3)) OR 4), Expr((5 OR 6) AND 7), Op(AND)
Expr(5 OR 6), Expr(7), Op(AND), Result((1 AND (2 OR 3)) OR 4), Op(AND)
Expr(5), Expr(6), Op(OR), Expr(7), Op(AND), Result((1 AND (2 OR 3)) OR 4), Op(AND)
Result(5), Expr(6), Op(OR), Expr(7), Op(AND), Result((1 AND (2 OR 3)) OR 4), Op(AND)
Result(6), Result(5), Op(OR), Expr(7), Op(AND), Result((1 AND (2 OR 3)) OR 4), Op(AND)
Result(5 OR 6), Expr(7), Op(AND), Result((1 AND (2 OR 3)) OR 4), Op(AND)
Result(7), Result(5 OR 6), Op(AND), Result((1 AND (2 OR 3)) OR 4), Op(AND)
Result((5 OR 6) AND 7), Result((1 AND (2 OR 3)) OR 4), Op(AND)
Result(((1 AND (2 OR 3)) OR 4) AND ((5 OR 6) AND 7))