这种fibonacci功能如何记忆？ [英] How is this fibonacci-function memoized?
问题描述
$ b
fib =（map fib'[0 ..] !! 这是什么机制是这个斐波那契函数memoized？ ）
其中fib'1 = 1
fib'2 = 1
fib'n = fib（n-2）+ fib（n-1）
在相关说明中，为什么这个版本不是？
fib n =（map fib'[0 ..] !! n）
其中fib'1 = 1
fib'2 = 1
fib'n = fib （n-2）+ fib（n-1）
解决方案 Haskell中的评估机制是 by-need ：当需要一个值时，它会被计算出来，并在需要的时候保持就绪状态再来一次。如果我们定义一些列表， xs = [0 ..] 并稍后请求它的第100个元素， xs !! 99 ，列表中的第100个插槽变得充实，现在持有数字 99 ，准备下次访问。
这就是利用掠过列表的招数。在普通的双重递归斐波那契定义中，函数本身被调用，从顶部两次调用，导致函数本身被调用，指数爆炸。但是有了这个诀窍，我们为中期业绩列出了一份清单，并且通过清单：
fib n = （xs !!（n-1））+（xs !!（n-2））其中xs = 0：1：map fib [2 ..]
诀窍是使该列表得到创建，并使该列表不会在（code> fib）调用之间消失（通过垃圾回收） 。实现这一目标的最简单方法是将该列表命名为 。 您的第一个版本定义了一个单形常量，第二个定义了一个多态函数。一个多态函数不能为它可能需要服务的不同类型使用相同的内部列表，所以没有共享，即没有记忆。 $ b
在第一个版本中，编译器对我们来说是大方的，取出那个常量子表达式（ map fib'[ 0 ..] ）并将其设为一个单独的可共享实体，但它没有任何义务这样做。 ，实际上有些情况我们不希望它自动为我们做。
（<考虑这些重写：
fib1 = f fib2 n = fn fib3 n = fn
where where
fi = xs !!我f i = xs !!我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 。
每次新的 fib2 调用似乎都会重新创建其嵌套定义，因为它们中的任何一个 （理论上）根据 n 的值的不同来定义（感谢Vitus和Tikhon指出了这一点）。在第一个定义中，没有 n 依赖于第三个定义，并且第三个定义存在依赖关系，但是每次调用 fib3 调用 f ，它只需调用同一级作用域的定义，在> fib3 ，所以相同的 xs 被重用（即共享）用于调用 fib3 。
但是没有任何东西阻止编译器认识到上面任何版本的内部定义实际上是独立于外部 n c $ c>绑定，毕竟执行 lambda解除，导致完整记忆（除了多态定义）。实际上，当使用单形类型声明并使用-O2标志进行编译时，所有三个版本都会发生这种情况。使用多态类型声明时，根本不共享。 fib3 显示本地共享，
最终，取决于编译器，使用的编译器优化，以及如何测试（在GHCI中加载文件，编译与否，使用-O2还是独立，还是独立），以及它是单态还是多态类型，行为可能会完全改变 - 无论它展示本地（每次调用）共享（即每次调用的线性时间），记忆（即第一次调用时的线性时间，以及0时间开启后续的调用具有相同或更小的参数），或根本没有共享（指数时间）。
简短的回答是，这是一个编译器。 ：）
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)
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.
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..]
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.
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. and there are actually cases where we don't want it to do that for us automatically.
(edit:) Consider these re-writes:
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.
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.
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.
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. :)
这篇关于这种fibonacci功能如何记忆？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
