问题描述
这个斐波那契函数是通过什么机制记忆的?
By what mechanism is this fibonacci-function memoized?
fib = (map fib' [0..] !!)
where fib' 1 = 1
fib' 2 = 1
fib' n = fib (n-2) + fib (n-1)
在相关说明中，为什么这个版本没有?
And on a related note, why is this version not?
fib n = (map fib' [0..] !! n)
where fib' 1 = 1
fib' 2 = 1
fib' n = fib (n-2) + fib (n-1)
推荐答案
Haskell 中的求值机制是按需:当需要一个值时，计算它，并准备好以防万一再次被要求.如果我们定义了一个列表，xs=[0..] 然后请求它的第 100 个元素，xs!!99，列表中的第 100 个槽被充实""，现在持有数字99，准备下次访问.
The evaluation mechanism in Haskell is by-need: 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.
这就是遍历列表"所利用的技巧.在正常的双递归斐波那契定义中，fib n = fib (n-1) + fib (n-2)，函数本身被调用，从顶部开始两次，导致指数爆炸.但是通过这个技巧，我们为中期结果列出了一个列表，然后浏览列表":
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 的调用之间不会消失(通过垃圾收集的方式).实现此目的的最简单方法是命名该列表.如果你说出它的名字，它就会留下来."
The trick is to cause that list to get created, and cause that list not to go away (by way of garbage collection) between calls to fib. The easiest way to achieve this, is to name that list. "If you name it, it will stay."
您的第一个版本定义了一个单态常量，第二个版本定义了一个多态函数.多态函数不能为它可能需要提供服务的不同类型使用相同的内部列表，因此没有共享，即没有记忆.
Your first version defines a monomorphic constant, and second defines a polymorphic function. A polymorphic function can't use the same internal list for different types it might need to serve, so no sharing, i.e. no memoization.
在第一个版本中，编译器对我们慷慨，去掉了那个常量子表达式 (map fib' [0..]) 并使它成为一个单独的可共享的实体，但它没有任何义务这样做.
With the first version, compiler is being generous with us, taking out that constant subexpression (map fib' [0..]) and making it a separate shareable entity, but it's not under any obligation to do so.
()考虑这些重写:
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)
所以真正的故事似乎是关于嵌套作用域定义的.第一个定义没有外部作用域，第三个注意不要调用外部作用域fib3，而是同级f.
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小心地只调用来自相同级别范围的定义，在此特定的 fib3 调用内部，因此相同的 xs 被重用(即共享)用于 fib3 的调用代码>fib3.
Each new invocation of fib2 seems to create its nested definitions anew because any of them could (in theory) be defined differently depending on the value of n (thanks to Vitus and Tikhon for pointing that out). With the first defintion there's no n to depend on, and with the third there is a dependency, but each separate call to fib3 calls into f which is careful to only call definitions from same-level scope, internal to this specific invocation of fib3, so the same xs gets reused (i.e. shared) for that invocation of fib3.
但没有什么能阻止编译器识别上述任何版本中的内部定义实际上独立外部n绑定，以执行lambda 提升 毕竟，导致完全记忆(除了多态定义).事实上，这正是使用单态类型声明并使用 -O2 标志编译时所有三个版本发生的情况.使用多态类型声明，fib3 表现出本地共享，而 fib2 根本没有共享.
But nothing precludes the compiler from recognizing that the internal definitions in any of the versions above are in fact independent of the outer n binding, to perform the lambda lifting after all, resulting in full memoization (except for the polymorphic definitions). In fact that's exactly what happens with all three versions when declared with monomorphic types and compiled with -O2 flag. With polymorphic type declarations, fib3 exhibits local sharing and fib2 no sharing at all.
最终，取决于编译器和使用的编译器优化，以及你如何测试它(在 GHCI 中加载文件，编译与否，是否使用 -O2 或独立)，以及它是否获得单态或多态类型行为可能会完全改变——它是否表现出本地(每次调用)共享(即每次调用的线性时间)、记忆(即第一次调用的线性时间，以及具有相同或更小的参数的后续调用的 0 时间)，或者不共享完全(指数时间).
Ultimately, depending on a compiler, and compiler optimizations used, and how you test it (loading files in GHCI, compiled or not, with -O2 or not, or standalone), and whether it gets a monomorphic or a polymorphic type the behaviour might change completely - whether it exhibits local (per-call) sharing (i.e. linear time on each call), memoization (i.e. linear time on first call, and 0 time on subsequent calls with same or smaller argument), or no sharing at all (exponential time).
简短的回答是，这是编译器的事情.:)
Short answer is, it's a compiler thing. :)
这篇关于这个斐波那契函数是如何记忆的?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！