这个记忆斐波那契函数是如何工作的？ [英] How does this memoized fibonacci function work?

问题描述

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

  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 
  

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

这是否意味着，例如， fiblist !! 2 + fiblist !! 1 ，列表值只为 fiblist计算一次！ 2 ，然后重新用于 fiblist !! 1 ？

然后这两个斐波纳契数字每次通话只计算一次，所以没有指数数量的通话。但是在 fiblist 函数中调用的较低级别如何？他们如何从原始 fibm 调用中计算的 fiblist 中受益？

fiblist只计算一次这些值！ 2 然后重新用于 fiblist !! 1 。

fiblist函数的'lower levels'以相同的方式工作。我第一次打电话给 fiblist !! 1 它将通过调用 fibm 1 来计算，该值仅为1，并且该值将保留在列表中。当你试图找到更高的斐波纳契数时， fiblist 将会调用 fibm ，这将查找更低的值 - 可能已经评估过 - fiblist 的位置。

In the current exercise assignment of the Functional Programming course I'm doing, we've got to make a memoized version of a given function. To explain memoization, the following example is given:

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

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

But I don't fully understand how this works.

Let's call 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

From other questions/answers and googling I learned that somehow, the evaluated fiblist is shared between calls.

Does this mean that, for example, for fiblist !! 2 + fiblist !! 1, the list values are only calculated once for fiblist !! 2 and then just reused for fiblist !! 1?

Then the two fibonacci numbers are calculated only once per call, so no exponential number of calls. But what about the "lower" levels of the call in the fiblist function? How do they benefit from the calculated fiblist in the original fibm call?

解决方案

The crucial part here is that the list is lazily evaluated, which means that the element isn't computed until the first time it's requested. Once it has been evaluated, however, it's there for anything else to look up. So in your example, you're right in saying that the values are only calculated once for the fiblist !! 2 and then reused for fiblist !! 1.

The 'lower levels' of the fiblist function work in the same way. The first time I call fiblist !! 1 it will be evaluated by calling fibm 1, which is just 1, and this value will then remain in the list. When you try to get up higher Fibonacci number, fiblist will call fibm which will look up those values in lower - and potentially already evaluated - positions of fiblist.

这篇关于这个记忆斐波那契函数是如何工作的？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！