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

Question

我想将代码更改为尾递归，以免堆栈溢出 expression 是 Label 或 Tree 的 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 展示的那样以尾递归方式重写该函数，它会起作用。但我认为这通常会掩盖算法的意图，因为现在你必须摆弄一个通常是隐式的显式堆栈。

我会说最好将堆栈摆弄位分解成可重用的数据结构并使用它。

cats.Eval

类型就是这样一种数据结构。

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