Scala中catamorphisms的高效实现

Question

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

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

在Scala中，这是一种实现相应范畴折叠的基本方法：

  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的方法。

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

- NietzscheanAI

---

不应该这样发表评论，但是算了吧..."有趣的问题"。期待回应。 - WestCoastProjects

Answer 1

如果你在列表上实现一个catamorphism，那在Haskell中我们称之为foldr。我们知道foldr没有尾递归定义，但是foldl有。所以如果你坚持要一个尾递归程序，正确的做法是反转列表参数（在线性时间内进行尾递归），然后使用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)    
  } 

那样可以吗？

- Mike Spivey

Answer 2

是的，这正是论文《左边是小丑，右边是小丑：数据结构解析》中的激励性例子（更新、更好但非免费版本在此http://dl.acm.org/citation.cfm?id=1328474）。

基本思想是将递归函数转换为循环，因此需要找出一种数据结构来跟踪过程的状态，即：

1. 到目前为止你已经计算了什么
2. 还有什么要做。

这个状态的类型取决于你正在对其进行折叠的类型的结构，在折叠的任何时刻，你都处于树的某个节点，并且需要记住“剩余部分”的树结构。该论文展示了如何机械地计算该状态类型。如果你对列表执行此操作，则需要跟踪的状态为：

1. 在所有先前值上运行的操作。
2. 要处理的元素列表。

这正是 foldl 所跟踪的内容, 所以说 foldl 和 foldr 可以拥有相同的类型，这有点巧合。

- Max New