3

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

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 代数的路线。

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

4

2 回答 2

1

如果你在列表上实现变态，这就是我们在 Haskell 中所说的 a foldr。我们知道它foldr没有尾递归定义，但是foldl有。因此，如果您坚持使用尾递归程序，正确的做法是反转列表参数（尾递归，线性时间），然后使用 afoldl代替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)    
  }

会这样吗？

于 2017-01-30T22:37:11.510 回答
0

是的，这正是我左边的小丑，右边的小丑（剖析数据结构）（更新，更好，但非免费版本在这里http://dl.acm.org/citation. cfm?id=1328474）。

基本思想是你想把你的递归函数变成一个循环，所以你需要找出一个跟踪过程状态的数据结构，即

  1. 到目前为止你计算的
  2. 你剩下要做的事。

这种状态的类型取决于你正在折叠的类型的结构，在折叠中的任何一点你都在树的某个节点处，你需要记住“树的其余部分”的树结构. 该论文展示了如何机械地计算该状态类型。如果您对列表执行此操作，您会得到需要跟踪的状态是

  1. 该操作对所有先前的值运行。
  2. 剩下要处理的元素列表。

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

于 2017-01-31T17:29:25.437 回答