在Scala中的'Data types ala Carte'中编写foldTerm

Question

我正在尝试foldTerm从Scala中的数据类型ala Carte编写函数.这是我到目前为止所得到的

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但我的所有尝试都以失败告终.

我错过了什么？

Answer 1

Scala可以正确消除尾递归调用。但你的方法不是尾递归。你可以通过注释来检查一下@annotaion.tailrec。

\n\n

@annotation.tailrec\ndef foldTerm[F[+_], A, B](e: Free[F, A], pure: A \xe2\x87\x92 B, imp: F[B] \xe2\x87\x92 B)(implicit F: Functor[F]): B =\n  e.resume match { \n    case Right(a) \xe2\x87\x92 pure(a)\n    case Left(x)  \xe2\x87\x92 imp(F.map(x)(foldTerm(_, pure, imp)))\n}\n\n<console>:19: error: could not optimize @tailrec annotated method foldTerm: it contains a recursive call not in tail position\n           case Left(x)  \xe2\x87\x92 imp(F.map(x)(foldTerm(_, pure, imp)))\n

\n\n

您最后一次来电是imp，而不是foldTerm。

\n