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

Question

这是代码:

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

评估时,fibs是一个无限的Fibonacci数列表.我不明白的是列表是如何连接的.

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元素运行一步,这也就是时间的推移.

在时间的缺点中使价值出现的所有学科都没有在类型中表达.目前,程序员必须确保在需求出现时耗尽数据时,良好类型的程序不会出错.(我计划对此采取一些措施,但我会尽量不要离开这里.)

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