这斐波那契功能如何memoized？(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)                    

Answer 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. :)

Answer 2:

我不能完全肯定，但这里是一个受过教育的猜测：

编译器假定fib n可能是在不同的不同的n ，因此需要在每次重新计算清单。 里面的位where语句可能取决于n ，毕竟。 也就是说，在这种情况下，数字的整个列表本质的功能n 。

没有版本n可以一次创建列表和功能包裹。 该列表可以不依赖于价值n在过去，这是很容易验证。 该列表是一个常数，然后将其索引到。 当然，那是懒洋洋地评估，让你的程序不试图立即得到整个（无限）列表中的常数。 因为它是一个常数，它可以在整个函数调用共享。

它的，因为在所有的递归调用只是要查找值列表中memoized。 由于fib版本创建列表一旦懒洋洋地，这才算够得到的答案没有做多余的计算。 这里，“懒惰”是指列表中的每个条目是一个thunk（一个未计算的表达式）。 当你做评估形实转换，就变成了价值，所以下一次访问它并没有重复计算。 由于名单可以调用之间共享，所有以前的条目已经被你所需要的下一个时间来计算。

它本质上是基于GHC的懒惰语义动态规划的聪明和廉租形式。 我认为标准只规定了它必须是不严格的 ，所以兼容的编译器可能编译这段代码不 memoize的。 然而，在实践中，每一个合理的编译器将是懒惰。

有关为什么第二种情况在所有工作的更多信息，请阅读理解一个递归定义的列表（zipWith方面避免信口开河） 。

Answer 3:

首先，GHC-7.4.2，编译-O2 ，非memoised版本并没有那么糟糕，斐波那契数的内部名单还在memoised每个顶级调用该函数。 但它不是，且不能合理，在不同的顶级调用来memoised。 然而，对于其它版本，该列表在调用共享。

这是由于单态的限制。

首先是通过简单的模式绑定（只有名称，没有参数）的约束，因此由单态的限制，必须获得一个单态类型。 推断类型

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

和这样的限制被默认（在不存在默认声明否则说的），以Integer ，固定类型

fib :: Int -> Integer

因此，这里有一个列表（类型[Integer] ）来memoise。

第二与函数参数所定义，从而其保持多晶型，并且如果该内部列表被在调用memoised，一个列表将必须memoised在每个类型Num 。 这是不实际的。

编译两个版本禁用，或具有相同类型签名单态的限制，都表现出完全一样的行为。 （这是在旧的编译器版本真的，我不知道哪个版本首先做到了。）

Answer 4:

你不需要Haskell的memoize的功能。 只有empirative编程语言需要这种功能。 然而，哈斯克尔是功能郎...

所以，这是例子非常快的斐波那契算法：

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.00018s

文章来源: How is this fibonacci-function memoized?