我正在尝试从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
。