这个memoized fibonacci函数如何工作？

Question

在我正在进行的功能编程课程的当前练习作业中,我们必须制作一个给定函数的memoized版本.为了解释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函数中调用的"较低"级别怎么样？他们如何受益fiblist于原始fibm电话中的计算？

Answer 1

这里的关键部分是列表被懒惰地评估,这意味着元素直到它第一次被请求时才被计算.然而,一旦进行了评估,就可以查找其他任何内容了.所以在你的例子中,你是正确的说,这些值只计算一次fiblist !! 2,然后重复使用fiblist !! 1.

fiblist功能的"较低级别"以相同的方式工作.我第一次调用fiblist !! 1它时将通过调用来评估fibm 1,它只是1,然后该值将保留在列表中.当你试图获得更高的斐波纳契数时,fiblist将调用fibm哪个将在更低的 - 并且可能已经评估 - 的位置查找这些值fiblist.

Answer 2

让我们一步一步地完成评估.除了显示当前表达式外,我们还显示了fiblist内存中的当前评估状态.在那里,我写作<expr>表示一个未>expr<评估的表达(通常称为thunk),并表示目前正在评估的未评估表达.你可以看到懒惰的评估.只有在需要时才会对列表进行评估,并且将共享完成的子计算以供将来重用.

   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将重用已经评估的列表元素.不过,该列表最终会变得越来越大,消耗的内存越来越多.