How is this fibonacci-function memoized?

这个斐波那契函数是通过什么机制制表的？

fib = (map fib' [0..] !!)
where fib' 1 = 1
fib' 2 = 1
fib' n = fib (n-2) + fib (n-1)

另外，为什么这个版本不是呢？

fib n = (map fib' [0..] !! n)
where fib' 1 = 1
fib' 2 = 1
fib' n = fib (n-2) + fib (n-1)
10092 次浏览
小开

我不是很确定，但我有一个合理的猜测:

编译器假设 fib n在不同的 n上可能不同，因此每次都需要重新计算列表。毕竟，where语句 可以中的位取决于 n。也就是说，在本例中，整个数字列表基本上是 n的函数。

版本 没有n可以创建一次列表并将其包装在函数中。列表 不能取决于传入的 n的值，这很容易验证。列表是一个常量，然后将其编入索引。当然，它是一个延迟计算的常量，因此您的程序不会尝试立即获取整个(无限)列表。因为它是一个常量，所以可以在函数调用之间共享它。

完全是制表的，因为递归调用只需要在列表中查找一个值。由于 fib版本只是懒惰地创建一次列表，所以它只需要进行足够的计算就可以得到答案，而不需要进行多余的计算。在这里，“惰性”意味着列表中的每个条目都是一个 thunk (一个未计算的表达式)。当您使用 做计算 thunk 时，它会变成一个值，因此下次访问它时不会重复计算。由于该列表可以在调用之间共享，所以在您需要下一个条目时，已经计算了以前的所有条目。

It's essentially a clever and low-rent form of dynamic programming based on GHC's lazy semantics. I think the standard only specifies that it has to be 不严格, so a compliant compiler could potentially compile this code to 没有 memoize. However, in practice, every reasonable compiler is going to be lazy.

有关为什么第二种情况会起作用的更多信息，请阅读 Understanding a recursively defined list (fibs in terms of zipWith)。

小开
最佳答案

The evaluation mechanism in Haskell is 需要: when a value is needed, it is calculated, and kept ready in case it is asked for again. If we define some list, xs=[0..] and later ask for its 100th element, xs!!99, the 100th slot in the list gets "fleshed out", holding the number 99 now, ready for next access.

That is what that trick, "going-through-a-list", is exploiting. In normal doubly-recursve Fibonacci definition, fib n = fib (n-1) + fib (n-2), the function itself gets called, twice from the top, causing the exponential explosion. But with that trick, we set out a list for the interim results, and go "through the list":

fib n = (xs!!(n-1)) + (xs!!(n-2)) where xs = 0:1:map fib [2..]

诀窍在于创建该列表，并且在对 fib的调用之间不使该列表消失(通过垃圾收集)。最简单的方法实现这一点，是 姓名的列表。“只要你说出它的名字，它就会留下来。”

第一个版本定义了一个单态常量，第二个版本定义了一个多态函数。一个多态函数不能对它可能需要服务的不同类型使用相同的内部列表，所以 不要分享，即不使用制表。

在第一个版本中，编译器就是 慷慨，取出常量子表达式(map fib' [0..]) ，使其成为一个单独的可共享实体，但它没有任何义务这样做。实际上，在某些情况下，我们不希望它自动为我们做到这一点。

(编辑:)考虑这些重写:

fib1 = f                     fib2 n = f n                 fib3 n = f n
where                        where                        where
f i = xs !! i                f i = xs !! i                f i = xs !! i
xs = map fib' [0..]          xs = map fib' [0..]          xs = map fib' [0..]
fib' 1 = 1                   fib' 1 = 1                   fib' 1 = 1
fib' 2 = 1                   fib' 2 = 1                   fib' 2 = 1
fib' i=fib1(i-2)+fib1(i-1)   fib' i=fib2(i-2)+fib2(i-1)   fib' i=f(i-2)+f(i-1)

So the real story seems to be about the nested scope definitions. There is no outer scope with the 1st definition, and the 3rd is careful not to call the outer-scope fib3, but the same-level f.

每次对 fib2的新调用似乎都会重新创建它的嵌套定义，因为其中任何一个 可以(理论上)在 n的值上都有不同的 看情况定义(感谢 Vitus 和 Tikhon 指出这一点)。第一个定义不需要依赖于 n，第三个定义有依赖关系，但是每个单独的对 fib3的调用都会调用到 f，而 f会小心翼翼地只从相同级别的范围内调用定义，这些定义是对 fib3的特定调用的内部调用，所以对于 fib3的调用，会重用相同的 xs(即共享)。

但是没有什么可以阻止编译器识别以上任何版本中的内部定义实际上是外部 n绑定的 独立，以执行 Lambda 举重，最终导致完全制表(多态定义除外)。实际上，当使用单态类型声明和使用 -O2标志编译时，所有三个版本都会发生这种情况。使用多态类型声明，fib3显示本地共享，而 fib2根本不共享。

最终，取决于一个编译器，使用的编译器优化，以及你如何测试它(在 GHCI 加载文件，编译与否，使用-O2，或独立) ，以及它是否得到一个单态或多态类型的行为可能会完全改变-是否表现出本地(每次调用)共享(即每次调用的线性时间) ，制表(即第一次调用的线性时间，以及后续调用相同或更小的参数为0的时间) ，或根本不共享(EXPTIME)。

简短的回答是，这是一个编译器的东西。 :)

小开

首先，对于用 -O2编译的 ghc-7.4.2，非制表的版本并没有那么糟糕，对于每个对函数的顶级调用，斐波那契数字的内部列表仍然制表。但是，不同级别的电话会议并没有、也不可能合理地记录这些信息。但是，对于另一个版本，该列表是跨调用共享的。

That is due to the monomorphism restriction.

第一个是由一个简单的模式绑定(只有名称，没有参数) ，因此由单态限制它必须得到一个单态类型。推断的类型是

fib :: (Num n) => Int -> n

而这样的约束将默认为 Integer(在没有默认声明的情况下) ，将类型固定为

fib :: Int -> Integer

因此只有一个列表([Integer]类型)需要记录。

第二个是用函数参数定义的，因此它仍然是多态的，如果内部列表是跨调用制表的，则必须为 Num中的每种类型制表一个列表。这不现实。

在禁用单态限制或使用相同的类型签名的情况下编译两个版本，两个版本的行为完全相同。(对于较老的编译器版本，情况并非如此，我不知道是哪个版本首先这样做的。)

小开

You don't need memoize function for Haskell. Only empirative programming language need that functions. However, Haskel is functional lang and...

这是一个快速斐波那契算法的例子:

fib = zipWith (+) (0:(1:fib)) (1:fib)

ZipWith 的功能来自标准序曲:

zipWith :: (a->b->c) -> [a]->[b]->[c]
zipWith op (n1:val1) (n2:val2) = (n1 + n2) : (zipWith op val1 val2)
zipWith _ _ _ = []

测试:

print $ take 100 fib

产出:

[1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946,17711,28657,46368,75025,121393,196418,317811,514229,832040,1346269,2178309,3524578,5702887,9227465,14930352,24157817,39088169,63245986,102334155,165580141,267914296,433494437,701408733,1134903170,1836311903,2971215073,4807526976,7778742049,12586269025,20365011074,32951280099,53316291173,86267571272,139583862445,225851433717,365435296162,591286729879,956722026041,1548008755920,2504730781961,4052739537881,6557470319842,10610209857723,17167680177565,27777890035288,44945570212853,72723460248141,117669030460994,190392490709135,308061521170129,498454011879264,806515533049393,1304969544928657,2111485077978050,3416454622906707,5527939700884757,8944394323791464,14472334024676221,23416728348467685,37889062373143906,61305790721611591,99194853094755497,160500643816367088,259695496911122585,420196140727489673,679891637638612258,1100087778366101931,1779979416004714189,2880067194370816120,4660046610375530309,7540113804746346429,12200160415121876738,19740274219868223167,31940434634990099905,51680708854858323072,83621143489848422977,135301852344706746049,218922995834555169026,354224848179261915075,573147844013817084101]

时间流逝: 0.00018秒


提交答案