haskell - 这个内存的斐波那契函数是如何工作的？

Question

在我正在做的函数式编程类(class)的当前练习作业中，我们必须制作一个给定函数的内存版本。为了解释内存，给出以下示例:

fiblist = [ fibm x | x <- [0..]]

fibm 0 = 0
fibm 1 = 1
fibm n = fiblist !! (n-1) + fiblist !! (n-2)

但我不完全理解这是如何工作的。

让我们调用 fibm 3 .

fibm 3
--> fiblist !! 2 + fibList 1
--> [fibm 0, fibm 1, fibm 2] !! 2 + [fibm 0, fibm 1] !! 1
--> fibm 2 + fibm 1
--> (fiblist !! 1 + fiblist 0) + 1
--> ([fibm 0, fibm 1] !! 1 + [fibm 0] !! 0) + 1
--> (fibm 1 + fibm 0) + 1
--> 1 + 0 + 1
--> 2

从其他问题/答案和谷歌搜索中，我了解到不知何故，评估的 fiblist 在调用之间共享。

这是否意味着，例如，对于 fiblist !! 2 + fiblist !! 1 ，列表值只计算一次 fiblist !! 2然后再用于 fiblist !! 1 ?

然后两个斐波那契数每次调用只计算一次，因此没有指数调用次数。但是 fiblist 中调用的“较低”级别呢？功能？他们如何从计算出的 fiblist 中受益？在原文 fibm称呼？

Answer 1

这里的关键部分是列表是惰性求值的，这意味着该元素直到第一次被请求时才被计算。然而，一旦它被评估，它就在那里供其他任何东西查找。因此，在您的示例中，您正确地说 fiblist !! 2 的值仅计算一次然后再用于fiblist !! 1 .

fiblist 函数的“较低级别”以相同的方式工作。第一次调用fiblist !! 1它将通过调用 fibm 1 进行评估，这只是 1，然后这个值将保留在列表中。当您尝试获得更高的斐波那契数时，fiblist将调用 fibm这将在 fiblist 的较低位置(可能已经评估)中查找这些值.