How is this fibonacci-function memoized?
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)
Solution 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. :)
Solution 2:
I'm not entirely certain, but here's an educated guess:
The compiler assumes that fib n could be different on a different n and thus would need to recalculate the list each time. The bits inside the where statement could depend on n, after all. That is, in this case, the whole list of numbers is essentially a function of n.
The version without n can create the list once and wrap it in a function. The list cannot depend on the value of n passed in and this is easy to verify. The list is a constant that is then indexed into. It is, of course, a constant that is lazily evaluated, so your program does not try to get the whole (infinite) list immediately. Since it's a constant, it can be shared across the function calls.
It's memoized at all because the recursive call just has to look up a value in a list. Since the fib version creates the list once lazily, it just calculates enough to get the answer without doing redundant calculation. Here, "lazy" means that each entry in the list is a thunk (an unevaluated expression). When you do evaluate the thunk, it becomes a value, so accessing it next time does no repeat the computation. Since the list can be shared between calls, all the previous entries are already calculated by the time you need the next one.
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 non-strict, so a compliant compiler could potentially compile this code to not memoize. However, in practice, every reasonable compiler is going to be lazy.
For more information about why the second case works at all, read Understanding a recursively defined list (fibs in terms of zipWith).
Solution 3:
First, with ghc-7.4.2, compiled with -O2, the non-memoised version isn't so bad, the internal list of Fibonacci numbers is still memoised for each top-level call to the function. But it is not, and cannot reasonably, be memoised across different top-level calls. However, for the other version, the list is shared across calls.
That is due to the monomorphism restriction.
The first is bound by a simple pattern binding (only the name, no arguments), therefore by the monomorphism restriction it must get a monomorphic type. The inferred type is
fib :: (Num n) => Int -> n
and such a constraint gets defaulted (in the absence of a default declaration saying otherwise) to Integer, fixing the type as
fib :: Int -> Integer
Thus there's just one list (of type [Integer]) to memoise.
The second is defined with a function argument, thus it remains polymorphic, and if the internal lists were memoised across calls, one list would have to be memoised for each type in Num. That isn't practical.
Compile both versions with the monomorphism restriction disabled, or with identical type signatures, and both exhibit exactly the same behaviour. (That wasn't true for older compiler versions, I don't know which version first did it.)
Solution 4:
You don't need memoize function for Haskell. Only empirative programming language need that functions. However, Haskel is functional lang and...
So, this is example of very fast Fibonacci algorithm:
fib = zipWith (+) (0:(1:fib)) (1:fib)
zipWith is function from standard Prelude:
zipWith :: (a->b->c) -> [a]->[b]->[c]
zipWith op (n1:val1) (n2:val2) = (n1 + n2) : (zipWith op val1 val2)
zipWith _ _ _ = []
Test:
print $ take 100 fib
Output:
[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]
Time elapsed: 0.00018s