这个记忆化的斐波那契函数是如何工作的？

Question

在我正在学习的函数式编程课程的当前练习任务中，我们必须制作给定函数的记忆化版本。为了解释记忆化，下面给出一个示例：

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函数的“较低”级别中怎样从原始fibm调用中计算出的fiblist受益？

- user42179

---

一个相关的问题，肯定已经在S.O上得到了答案-我现在正在查看-关于惰性求值。考虑if (f x) > 0 then f x else 0，其中f x是某个昂贵的函数调用。如果if条件为真，那么f x将被重复计算吗，还是值将被简单地重用？ - user42179

关于您相关的问题请参见此处。 - Nikita Volkov

啊，就在那儿。谢谢！ - user42179

顺便提一下，即使列表已经被评估过了，fiblist !! n 的时间复杂度也是 O(n)，我相信第一次计算 fibm n 会对每个 i < n 的 fiblist !! i 进行评估，这样的时间复杂度是 O(n^2)。你可以做得更好... - Itai Zukerman

一个“边缘重复”的相关问题：https://dev59.com/fGgu5IYBdhLWcg3wP01m。 - Will Ness

Answer 1

关键部分在于列表是惰性求值的，这意味着元素直到第一次请求时才被计算。但是一旦它被计算过，它就可以供其他任何东西查找。所以在你的例子中，你说的对，fiblist !! 2 的值只被计算一次，然后被重复使用在 fiblist !! 1 中。 fiblist 函数的 "较低层" 也是以同样的方式工作的。第一次调用 fiblist !! 1 时，将通过调用 fibm 1 进行评估，其结果只是 1，然后该值将保留在列表中。当你试图获取更高的斐波那契数时，fiblist 将调用 fibm，并查找 fiblist 中较低且可能已经计算过的位置上的值。

- Impredicative

Answer 2

让我们逐步了解评估过程。除了显示当前表达式外，我们还在内存中显示 fiblist 的当前评估状态。我用<expr>表示未评估的表达式（通常称为thunk），用>expr<表示正在评估的未评估表达式。你可以看到惰性评估的实际效果。列表仅在需要时进行评估，并且完成的子计算将被共享以供将来重复使用。

   Current expression                       Current evaluation state of fiblist

   fibm 3                                   <[ fibm x | x <- [0..] ]>

->   (simple expansion of the definition)

   fiblist !! (3-1) + fiblist !! (3-2)      <[ fibm x | x <- [0..] ]>

->   ((+) has to evaluate both its arguments to make progress, let's assume
     it starts with the left argument; (!!) traverses the list up to the given
     element and returns the element it finds)

   fibm 2 + fiblist !! (3-2)                <fibm 0> : <fibm 1> : >fibm 2< : <[ fibm x | x <- [3..] ]>

->   (simple expansion of the definition)

   (fiblist !! (2-1) + fiblist !! (2-2)) + fiblist !! (3-2)
                                            <fibm 0> : <fibm 1> : >fibm 2< : <[ fibm x | x <- [3..] ]>

->   (we again start with the first argument to (+),
     computing the result of (!!) does not cause any
     further evaluation of fiblist)

   (fibm 1 + fiblist !! (2-2)) + fiblist !! (3-2)
                                            <fibm 0> : >fibm 1< : >fibm 2< : <[ fibm x | x <- [3..] ]>

->   (expanding fibm 1 returns a result immediately;
     this concludes the computation of fibm 1,
     and the thunk is updated with the result)

   (1 + fiblist !! (2-2)) + fiblist !! (3-2)
                                            <fibm 0> : 1 : >fibm 2< : <[ fibm x | x <- [3..] ]>

->   (now we compute fiblist !! (2-2))

   (1 + fibm 0) + fiblist !! (3-2)          >fibm 0< : 1 : >fibm 2< : <[ fibm x | x <- [3..] ]>

->   (expanding fibm 0 returns 0 immediately, and the
     corresponding thunk can be updated)

   (1 + 0) + fiblist !! (3-2)               0 : 1 : >fibm 2< : <[fibm x | x <- [3..] ]>

->   (we can compute the (+), yielding the result of
     fibm 2; the corresponding thunk is updated)

   1 + fiblist !! (3-2)                     0 : 1 : 1 : <[fibm x | x <- [3..] ]>

->   (now the right argument of (+) has to be evaluated, but (!!)
     will return the already evaluated list element directly)

   1 + 1                                    0 : 1 : 1 : <[fibm x | x <- [3..] ]>

->   (arithmetic; note that as we called fibm 3 directly in the
     beginning, instead of fiblist !! 3, the list is unaffected
     by this final result)

   2                                        0 : 1 : 1 : <[fibm x | x <- [3..] ]>

作为全局常量（通常称为“常量适用形式”），fiblist的部分求值状态将持续存在，未来对fibm的调用将重复使用已经评估过的列表元素。然而，列表最终会变得越来越大，消耗越来越多的内存。

- kosmikus