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

Question

这是代码：

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

计算时，fibs 是斐波那契数列的无限列表。我不明白的是列表是如何连接的。

zipWith returns 一个列表，所以压缩 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

您的 "Because" 并没有说明全部情况。您正在截断 "the story so far" 处的列表并急切地进行评估，然后想知道其余部分来自何处。不太了解到底发生了什么，问得好。

定义时计算的内容

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

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

有什么需求？你可以问 "are you [] or 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)

看到了吗？我们坚持认为我们仍然知道一个压缩列表的前两个元素，以及另一个的第一个元素。这意味着我们将能够提供下一个输出和刷新我们的 "buffer"。当我们查看 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 运行个元素中进一步移动一步，这也是一样的，只是在关键时刻。

None 使价值在紧要关头出现的纪律体现在类型中。目前，程序员需要确保在提出需求时，类型良好的程序不会因运行数据不足而出错。（我计划为此做点什么，但我会尽量不离题。）

关键是惰性，"on demand" 计算意味着我们不必将列表截断为我们在进程启动时可以看到的元素。我们只需要知道我们总能迈出下一步。

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

Can someone explain this lazy Fibonacci solution?

haskell

stream

lazy-evaluation

fibonacci

lazy-sequences