haskell - 使用 fix 递归生成斐波那契数列 - 这个例子是如何工作的？

Question

大家早上好!

Stackoverflow，作为它的兔子洞，引导我修复(包含在 Data.Fuction 中的那个)，因为我已经在这个过程中通过一些更常见的 Haskell 库，并且由于 fix 似乎是一个研究主题，所以我开始阅读它，首先是在 Haskell Wiki ( https://en.m.wikibooks.org/wiki/Haskell/Fix_and_recursion ) 上，然后在这篇文章 ( https://www.vex.net/~trebla/haskell/fix.xhtml ) 中，由相关主题的评论建议。

在后者中，作者给出了四个递归示例，然后经过几次迭代将它们转换为适合与 fix 一起使用的形式。我了解思考过程，也了解最终结果。我还得出结论，前两个函数(zeroes 和 fibs)是发散计算的例子，因为它们不会终止，而另外两个(factorial 和 mapeven) 收敛到某个不动点。

真正让我感到困惑的是第二个函数的工作方式，fibs。

我很清楚 zeroes 是如何工作的，因为 fix f = let x = f x in x。因此，ghci 知道它必须计算 0:x，将显示 0 然后尝试计算出 x 是什么，结果是再次成为 0:x，因此它将显示 0，然后再次尝试计算 x 是什么，无穷无尽。换句话说，它从 0:x 到 0:(0:x) 再到 0:(0:(0:x)) 等等，追逐自己的尾部。

在 fibs 的情况下，递归似乎有点倒退。函数是0:scanl (+) 1 x，其实就是0:scanl (+) 1 (0:scanl (+) 1 x)。那么ghci应该做什么呢？首先，显示0，因为这是给定的，然后计算scanl 的结果是什么。好吧，对于第一个简单的元素，它应该是已经为 scanl 提供的累加器或 1。但随后它应该真正计算出 x 实际上是什么，以便继续计算，而 x 是 0:scanl (+) 1 x，这当然是一个以 0 开头的列表，因此第一个 scanl 会将它的 1 与 0 相加，并给出 1 作为计算的第三个元素，然后将 1 与嵌套 scanl 函数的 acc 相加，再次 1，因此，2 成为第四个元素该计算链。但是第二个 scanl 应该真正计算出 x 是什么，结果又是 0:scanl (+) 1 x，所以第五个元素不应该该列表的再次为 2，这是第二个 scanl 函数的累加器值，加上 0，作为新评估的第一个元素x？这个计算究竟是如何继续输出斐波那契数列的？在我看来它应该永远卡在那里(比如，说 fix id)，因为它应该首先计算 x 是什么。

如果有人能对这个(每一个双关语)做出正面或反面的解释，并以一种对我们其他人都有意义的方式进行解释，我将非常感激。

谢谢!

Answer 1

理解 Haskell 程序的评估方式的一个好方法是重写。 Haskell 程序由方程式 组成，这些方程式用于展开主要表达式并实现进一步的简化。这里的相关方程来自于fix和scanl的定义。

x = 0 : scanl (+) 1 x

scanl (+) n (y : ys) = n : scanl (+) (n + y) ys

我们要计算 x。从展开 x 开始

x = 0 : scanl (+) 1 x                           -- (1)
  = 0 : scanl (+) 1 (0 : scanl (+) 1 x)

这让我们可以使用 scanl 方程，其中 y = 0 和 ys = scanl (+) 1 x。

x = 0 : 1 : scanl (+) (1 + 0) (scanl (+) 1 x)
  = 0 : 1 : scanl (+) 1 (scanl (+) 1 x)         -- (2)

接下来我们需要展开 scanl (+) 1 x，如果我们看上面，我们已经完成了这项工作，从标记为 (1) 的那些推导出以下等式> 和 (2)

scanl (+) 1 x = 1 : scanl (+) 1 (scanl (+) 1 x)

这让我们无需重复展开最近出现的 scanl (+) 1 x 的工作。

x = 0 : 1 : scanl (+) 1 (1 : scanl (+) 1 (scanl (+) 1 x)))

展开扫一扫:

x = 0 : 1 : 1 : scanl (+) (1 + 1) (scanl (+) 1 (scanl (+) 1 x))
  = 0 : 1 : 1 : scanl (+) 2 (scanl (+) 1 (scanl (+) 1 x))         -- (3)

同样，我们要展开scanl (+) 1 (scanl (+) 1 x)，我们之前已经见过(在(2)中) ，结果可以在最后一个等式 (3) 中读取。

x = 0 : 1 : 1 : scanl (+) 2 (1 : scanl (+) 2 (scanl (+) 1 (scanl (+) 1 x)))
  = 0 : 1 : 1 : 2 : scanl (+) 3 (scanl (+) 2 (scanl (+) 1 (scanl (+) 1)))

现在我们可以看到累加器 3 出现了。

---

我试图变得聪明，避免做已经以某种形式完成的工作。一种更系统的方法是为每个新表达式关联一个变量。事实上，这与 GHC 中惰性求值的实现方式非常接近:每个变量都是一个内存位置，其中包含未求值的表达式或应用于变量的构造函数。

x = 0 : scanl (+) 1 x

命名列表的尾部。

x = 0 : x1
x1 = scanl (+) 1 x

替换和简化

x1 = scanl (+) 1 (0 : x1)
   = 0 : scanl (+) 1 x1

命名列表的尾部

x1 = 0 : x2
x2 = scanl (+) 1 x1

等等

x2 = scanl (+) 1 (0 : x2)
   = 1 : scanl (+) 1 x2
   = 1 : x3
x3 = scanl (+) 1 x2
   = scanl (+) 1 (1 : x3)
   = 1 : scanl (+) 2 x3
   = 1 : x4
x4 = 2 : x5
x5 = 3 : x6
x6 = 5 : x7
x7 = ...