8

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

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 在呼叫之间共享。

这是否意味着，例如 for fiblist !! 2 + fiblist !! 1，列表值只计算一次 for fiblist !! 2，然后再重复使用 for fiblist !! 1？

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

4

2 回答 2

8

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

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

于 2013-03-21T10:03:39.577 回答
5

让我们逐步完成评估。除了显示当前表达式之外，我们还显示了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将重用列表中已评估的元素。不过，列表最终会变得越来越大，消耗越来越多的内存。

于 2013-03-21T11:06:48.630 回答