haskell - 理解 Haskell 中的直接自引用

Question

我刚开始学习 Haskell 几个小时，试图理解这是什么 The Fibonacci sequence做:

fibs = 0 : 1 : next fibs
  where
    next (a : t@(b:_)) = (a+b) : next t

next 函数对我来说很奇怪，它最终会得到一些“无效”的输入，就像一开始它是这样的:

next (0:1) = (0+1) : next [1]

但是 next ([1]) 不可操作，因为 t@(b:_) 没有输入。那么 next 是如何工作的呢？

我的下一个困惑是 fib 本身，因为它被认为是斐波那契数列，我假设它会在之后得到 fibs = 0 : 1 : 1 : next fibs第一步，但随后我们需要计算 next([0, 1, 1]) 女巫给出 (0+1): next([1, 1]) == 1 : next([1, 1])，我们得到了初始元素1，所以在next([0, 1, 1])中，第一个列表的值(在下一个 fibs 中)将为 1，但将此 1 附加到原始 fib，我们得到 0 : 1 : 1 : 1，这不是 Fibonacci 序列。

我想我误解了一些东西，那么它实际上是如何工作的呢？

Answer 1

定义递归定义结果的标准方法是从 undefined 开始近似这样的值，然后从那里展开递归，如下所示:

-- A function describing the recursion
f x = 0 : 1 : next x

fibs0 = undefined
fibs1 = f fibs0 = 0 : 1 : next undefined 
      -- next requires at least 2 elements
      = 0 : 1 : undefined
fibs2 = f fibs1 = 0 : 1 : next fibs1
      = 0 : 1 : next (0 : 1 : undefined)
      = 0 : 1 : 1 : next (1 : undefined)
      -- next requires at least 2 elements
      = 0 : 1 : 1 : undefined
fibs3 = f fibs2 = 0 : 1 : next fibs2
      = 0 : 1 : next (0 : 1 : 1 : undefined)
      = 0 : 1 : 1 : next (1 : 1 : undefined)
      = 0 : 1 : 1 : 2 : next (1 : undefined)
      -- next requires at least 2 elements
      = 0 : 1 : 1 : 2 : undefined
fibs4 = f fibs3 = 0 : 1 : next fibs3
      = 0 : 1 : next (0 : 1 : 1 : 2 : undefined)
      ...

如果我们继续前进，我们将接近“极限”的完整序列，逐步接近它。这种非正式论证可以通过 Kleene 不动点定理得到正式证明。