haskell - 有人可以解释这个懒惰的斐波那契解决方案吗？

Question

这是代码:

fibs = 0 : 1 : zipWith (+) fibs (drop 1 fibs)

计算时， fibs 是一个无限的斐波那契数列。我不明白的是列表是如何连接的。
zipWith 返回一个列表，所以压缩 fibs 会产生这个:

0 : 1 : [1] : [1,2] : [1,2,3]

因为 0 : 1 : zipWith (+) [0,1] [1] 产生 [1] 和 zipWith (+) [0,1,1] [1,1] 产生 [1,2] 等)。

但是，当我运行代码时，我得到了正确的结果。

我在这里不明白什么？

Answer 1

你的“因为”并没有讲述整个故事。您正在截断“到目前为止的故事”中的列表并急切地评估，然后想知道其余部分来自哪里。这并不能完全掌握真正发生的事情，所以这是个好问题。

定义时计算什么

fibs = 0 : 1 : zipWith (+) fibs (drop 1 fibs)

?很少。一旦您开始使用列表，计算就会开始。延迟计算仅在需要时发生。

什么叫需求？你会问“你是 [] 还是 x : xs ？”如果是后者，你就可以处理这些碎片。

当我们问 fibs 的问题时，我们得到了

fibs = x0 : xs0
x0  = 0
xs0 = 1 : zipWith (+) fibs (drop 1 fibs)

但这意味着(替换 fibs 然后 x0 )

xs0 = 1 : zipWith (+) (0 : xs0) (drop 1 (0 : xs0))

当我们再次询问时，我们明白了

xs0 = x1 : xs1
x1  = 1
xs1 = zipWith (+) (0 : xs0) (drop 1 (0 : xs0))

所以

xs1 = zipWith (+) (0 : 1 : xs1) (drop 1 (0 : 1 : xs1))

但现在它变得有趣了，因为我们必须做一些工作。只需足够的工作来回答这个问题，介意吗？当我们查看 xs1 时，我们会强制 zipWith ，这会强制 drop 。

xs1 = zipWith (+) (0 : 1 : xs1) (drop 1 (0 : 1 : xs1))
    = zipWith (+) (0 : 1 : xs1) (1 : xs1)
    = (0 + 1) : zipWith (+) (1 : xs1) xs1

所以

xs1 = x2 : xs2
x2  = 0 + 1 = 1
xs2 = zipWith (+) (1 : xs1) xs1
    = zipWith (+) (1 : 1 : xs2) (1 : xs2)

看？我们一直认为我们仍然知道一个压缩列表的前两个元素，以及另一个的第一个元素。这意味着我们将能够提供下一个输出并刷新我们的“缓冲区”。当我们查看 xs2 时，我们得到

xs2 = zipWith (+) (1 : 1 : xs2) (1 : xs2)
    = (1 + 1) : zipWith (1 : xs2) xs2
xs2 = x3 : xs3
x3  = 1 + 1 = 2
xs3 = zipWith (1 : xs2) xs2
    = zipWith (1 : 2 : xs3) (2 : xs3)

我们很高兴再次去!

每次我们请求下一个元素时，我们也会远离 zipWith 耗尽元素，这也恰逢其时。

使值(value)观在关键时刻显现出来的任何学科都没有在类型中表达出来。目前，程序员需要确保类型良好的程序不会在提出需求时因数据耗尽而出错。 (我计划为此做点什么，但我会尽量不要在这里跑题。)

关键是懒惰的“按需”计算意味着我们不必将列表截断为我们在流程开始时可以看到的元素。我们只需要知道我们总是可以采取下一步行动。