这个memoized斐波纳契函数是如何工作的？

Question

在我正在做的功能编程课程的当前练习任务中，我们必须编写一个给定函数的记忆版本。解释memoization，给出以下例子：

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获益？

Answer 1

这里至关重要的部分是列表懒惰地评估，这意味着该元素直到第一次被请求才被计算。然而，一旦它被评估，它就可以在其他地方查找。所以在你的例子中，你说得对，fiblist !! 2的值只计算一次，然后再用于fiblist !! 1。

fiblist功能的“低级别”以相同的方式工作。我第一次打电话给fiblist !! 1，它将通过调用fibm 1进行评估，该值仅为1，这个值将保留在列表中。当您尝试获得更高的斐波纳契数时，fiblist将调用fibm，它将在fiblist的较低位置（可能已经评估过）中查找这些值。

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是一个全局变量（通常称为CAF为“常数应用形式”），列表中的部分评估状态将持续和未来的呼叫fibm将重用名单已经评价要素。尽管如此，这个列表最终会变得越来越大，消耗越来越多的内存。