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

Question

我有一堆 Expr 类定义如下：

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

这还不够好，因为它是正常的递归。

我打算使用蹦床重构exec函数。

使用蹦床要求每次此函数调用其他内容时，调用都应处于尾部位置，以便在蹦床中翘曲。

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

有没有办法做到这一点？

Answer 1

你在这里走在蹦床的正确道路上。看看Cats或Scalaz的Trampoline实现(基于Free Monad(。或者你可以在scala.util.control.TailCalls包中使用vanilla Scala。由于所有这些都是Monads的设计，因此您可以执行以下操作：

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的调用保留了蹦床的属性，并且永远不会导致堆栈爆炸。