我有一个 Expr 值，在 Scala 中有两个子 Expr，如何在尾部位置执行它？

Question

我有一堆 Expr class 定义如下：

sealed trait BoolExpr
sealed trait Value[T] {
  def get: T
}

final case class AndExpr(left: Expr, right: Expr) extends BoolExpr
final case class EqualsExpr[T](value: Value[T], expectedValue: T) extends BoolExpr

在构建了整个 BoolExpr 值之后，我将使用如下函数执行它：

def exec(expr: BoolExpr) = {
  expr match {
    case EqualsExpr(value, expectedValue) => value.get == expectedValue
    case AndExpr(left: Expr, right: Expr) => exec(left) && exec(right)
  }
}

这还不够好，因为它是一个普通的递归。

我打算使用 trampoline 重构 exec 函数。

使用 trampoline 要求每次此函数调用其他内容时，调用都应位于尾部位置，以便在 trampoline 中变形。

但我找不到将 exec(left) && exec(right) 部分重写为尾调用样式的方法。

有什么办法可以做到吗？

Answer 1

你在这里玩蹦床是对的。看看 Cats or Scalaz's Trampoline implementation (which are based on the Free Monad.) Or you can use vanilla Scala in the scala.util.control.TailCalls 包。由于所有这些都是设计的 Monad，您可以执行以下操作：

import util.control.TailCalls._

def exec(expr: BoolExpr) = expr match{
  case EqalsExpr(value, expectedValue) => done(value.get == expectedValue)
  case AndExpr(left, right) => exec(left).flatMap{
    l => exec(right).map(l && _)
  }
}

请注意，调用 map 和 flatMap 会保留 Trampoline 的属性，永远不会导致堆栈爆炸。

我有一个 Expr 值，在 Scala 中有两个子 Expr，如何在尾部位置执行它？

I have a Expr value that have two child Expr in Scala, how can I execute this in tail position?

recursion

scala

tail-recursion