我正在尝试从Scala中的Data Types ala Carte编写foldTerm函数。这是到目前为止我得到的

def foldTerm[F[+_], A, B](e: Free[F, A], pure: A ⇒ B, imp: F[B] ⇒ B)(implicit F: Functor[F]): B =
  e.resume match {
    case Right(a) ⇒ pure(a)
    case Left(x)  ⇒ imp(F.map(x)(foldTerm(_, pure, imp)))
}

这可行,但是由于Scala无法正确优化尾递归,因此会导致SOE。我尝试用Trampoline修复它,但是到目前为止还没有任何运气。我觉得我应该可以使用Free上的现有方法来做到这一点,但是我的所有尝试都以失败告终。

我想念什么?

最佳答案

Scala可以正确消除尾部递归调用。但是您的方法不是尾递归。您可以使用@annotaion.tailrec批注进行检查。

@annotation.tailrec
def foldTerm[F[+_], A, B](e: Free[F, A], pure: A ⇒ B, imp: F[B] ⇒ B)(implicit F: Functor[F]): B =
  e.resume match {
    case Right(a) ⇒ pure(a)
    case Left(x)  ⇒ imp(F.map(x)(foldTerm(_, pure, imp)))
}

<console>:19: error: could not optimize @tailrec annotated method foldTerm: it contains a recursive call not in tail position
           case Left(x)  ⇒ imp(F.map(x)(foldTerm(_, pure, imp)))

您在这里的最后一个电话是imp而不是foldTerm

10-07 15:59
查看更多