在Scala中有效实现Catamorphisms(Efficient implementation of Catamorphisms in Scala)

在Scala中有效实现Catamorphisms(Efficient implementation of Catamorphisms in Scala)

对于表示自然数的数据类型：

sealed trait Nat case object Z extends Nat case class S(pred: Nat) extends Nat

在Scala中，这是实现相应的catamorphism的基本方法：

def cata[A](z: A)(l: Nat)(f: A => A): A = l match { case Z => z case S(xs) => f( cata(z)(xs)(f) ) }

但是，由于对cata的递归调用不在尾部位置，因此很容易触发堆栈溢出。

有哪些替代实施方案可以避免这种情况？ 我宁愿不去F-algebras的路线，除非代码最终呈现的界面看起来非常简单。

编辑：看起来这可能是直接相关的： 是否可以使用continuation使foldRight尾递归？

For a datatype representing the natural numbers:

sealed trait Nat case object Z extends Nat case class S(pred: Nat) extends Nat

In Scala, here is an elementary way of implementing the corresponding catamorphism:

def cata[A](z: A)(l: Nat)(f: A => A): A = l match { case Z => z case S(xs) => f( cata(z)(xs)(f) ) }

However, since the recursive call to cata isn't in tail position, this can easily trigger a stack overflow.

What are alternative implementation options that will avoid this? I'd rather not go down the route of F-algebras unless the interface ultimately presented by the code can look pretty much as simple as the above.

EDIT: Looks like this might be directly relevant: Is it possible to use continuations to make foldRight tail recursive?

最满意答案

如果你在列表上实现了一个catamorphism，那么在Haskell中我们称之为foldr 。 我们知道foldr没有尾递归定义，但foldl有。 因此，如果你坚持使用尾部重复程序，那么正确的做法是反转list参数（在线性时间内递归递归），然后使用foldl代替foldr 。

您的示例使用更简单的自然数据类型（真正“高效”的实现将使用机器整数，但我们同意将其放在一边）。 你的一个自然数字的反转是什么？ 只是数字本身，因为我们可以把它想象成一个列表，每个节点都没有数据，所以我们无法分辨它何时被逆转！ 什么相当于foldl ？ 这是程序（原谅伪代码）

def cata(z, a, f) = { var x = a, y = z; while (x != Z) { y = f(y); x = pred(x) } return y }

或者作为Scala尾递归，

def cata[A](z: A)(a: Nat)(f: A => A): A = a match { case Z => z case S(b) => cata( f(z) )(b)(f) }

那会吗？

If you were implementing a catamorphism on lists, that would be what in Haskell we call a foldr. We know that foldr does not have a tail-recursive definition, but foldl does. So if you insist on a tail-recusive program, the right thing to do is reverse the list argument (tail-recursively, in linear time), then use a foldl in place of the foldr.

Your example uses the simpler data type of naturals (and a truly "efficient" implementation would use machine integers, but we'll agree to leave that aside). What is the reverse of one of your natural numbers? Just the number itself, because we can think of it as a list with no data in each node, so we can't tell the difference when it is reversed! And what's the equivalent of the foldl? It's the program (forgive the pseudocode)

def cata(z, a, f) = { var x = a, y = z; while (x != Z) { y = f(y); x = pred(x) } return y }

Or as a Scala tail-recursion,

def cata[A](z: A)(a: Nat)(f: A => A): A = a match { case Z => z case S(b) => cata( f(z) )(b)(f) }

Will that do?