5

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

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

我错过了什么？

4

2 回答 2

2

事实证明这毕竟不是我的问题。我ListT.fromList在一个大列表上使用 a ，这就是破坏堆栈的原因。切换到使用StreamT解决了这个问题。

于 2012-07-13T17:18:21.380 回答
2

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。

于 2012-07-13T08:06:53.370 回答