Scala 中 Catamorphisms 的高效实现

Question

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

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 的路线，除非代码最终呈现的界面看起来和上面的一样简单。

编辑：看起来这可能直接相关：Is it possible to use continuations to make foldRight tail recursive?

Answer 1

如果您要在列表上实现变形，那将是我们在 Haskell 中所说的 foldr。我们知道 foldr 没有 tail-recursive 定义，但是 foldl 有。所以如果你坚持使用 tail-recusive 程序，正确的做法是反转列表参数（tail-recursively，线性时间），然后使用 foldl 代替 foldr.

您的示例使用更简单的自然数数据类型（真正的 "efficient" 实现将使用机器整数，但我们同意将其搁置一旁）。你的一个自然数的倒数是多少？只是数字本身，因为我们可以把它看成是一个列表，每个节点都没有数据，所以倒过来是分不出来的！ foldl 相当于什么？就是程序（原谅伪代码）

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

或者作为 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)    
  }

这样行吗？

Answer 2

是的，这正是论文中的激励示例我左边的小丑，右边的小丑（剖析数据结构）（已更新，更好，但 non-free 版本在这里 http://dl.acm.org/citation.cfm?id=1328474）。

基本思想是你想把你的递归函数变成一个循环，所以你需要弄清楚一个数据结构来跟踪过程的状态，也就是

你到目前为止的计算结果
你还有什么事要做。

这个状态的类型取决于你正在折叠的类型的结构，在折叠的任何一点你都在树的某个节点，你需要记住 "the rest of the tree"。本文展示了如何机械地计算该状态类型。如果您对列表执行此操作，您会发现需要跟踪的状态是

对所有先前值的操作运行。
待处理的元素列表。

这正是 foldl 跟踪的内容，因此 foldl 和 foldr 可以被赋予相同的类型是一种巧合。

Scala 中 Catamorphisms 的高效实现

Efficient implementation of Catamorphisms in Scala

scala

algebraic-data-types

category-theory

catamorphism

recursion-schemes