How is this fibonacci-function memoized?

Question

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)

Slightly unrelatedly, `fib 0` doesn't terminate: you probably want the base cases for `fib'` to be `fib' 0 = 0` and `fib' 1 = 1`. — huon, Jul 13 '12 at 07:51
Note that the first version could be made more concise: `fibs = 1:1:zipWith (+) fibs (tail fibs)` and `fib = (fibs !!)`. — Bastian, Aug 19 '12 at 08:24

score 98 · Accepted Answer · edited May 23 '17 at 11:53

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

Just to fix a little detail: the second version doesn't get any sharing mainly because the local function `fib'` is redefined for every `n` and thus `fib'` in `fib 1` ≠ `fib'` in `fib 2`, which also implies the lists are different. Even if you do fix the type to be monomorphic, it still exhibits this behaviour. — Vitus, Jul 13 '12 at 13:18
`where` clauses introduce sharing much like `let` expressions, but they tend to hide problems such as this one. Rewriting it a bit more explicitly, you get this: http://hpaste.org/71406 — Vitus, Jul 13 '12 at 15:12
@Vitus thanks. my new three re-writes also clarify things for me. but in theory GHC could have looked at the actual definiton of every internal definiton for `fib2` (using the names as in my answer), recognized those that do not in fact depend on `n`, and create an efficient code for them (here, all of them) ... — Will Ness, Jul 13 '12 at 15:46
Yes, indeed. But GHC is conservative with these kinds of optimizations because they can quite easily introduce space leaks. — Vitus, Jul 13 '12 at 16:01
Another interesting point about your rewrite: if you give them monomorphic type (i.e. `Int -> Integer`), then `fib2` runs in exponential time, `fib1` and `fib3` both run in linear time but `fib1` is also memoized - again because for `fib3` the local definitions are redefined for every `n`. — Vitus, Jul 13 '12 at 16:09
Is there a way with GHC to declare (with a pragma) the programmers intent that a certain value be shared via the CAF/lambda-lifting process, to get statically checked evidence for use in big-O performance reasoning? Something akin to INLINE. If not, is such a feature possible in principle? — misterbee, Jan 06 '14 at 21:20
@misterbee That's a question for implementors. I'm not qualified to answer, sorry. I just show here a general principle of naming an entity. — Will Ness, Jan 06 '14 at 21:25
@misterbee But indeed it would be nice to have some kind of assurance from the compiler; some kind of control over the memory residency of a specific entity. Sometimes we want sharing, sometimes we want to prevent it. I imagine/hope it should be possible... — Will Ness, Jan 06 '14 at 22:03
"and there are actually cases where we don't want it to do that for us automatically" what's an example of one of these cases? — Eliza Brandt, Dec 07 '18 at 07:12
@ElizaBrandt what I meant was that sometimes we want to recalculate something heavy so it is not retained for us in memory -- i.e. the cost of recalculation is lower than the cost of huge memory retention. one example is powerset creation: in `pwr (x:xs) = pwr xs ++ map (x:) pwr xs ; pwr [] = [[]]` we do want `pwr xs` to be calculated independently, twice, so it can be garbage collected on the fly as it is being produced and consumed. — Will Ness, Dec 07 '18 at 07:22
@ElizaBrandt another example is shown and explained [here](https://stackoverflow.com/q/13894417/849891). — Will Ness, Dec 10 '18 at 08:08
[see also](https://wiki.haskell.org/Memoization#Memoising_CAFS). — Will Ness, Feb 21 '20 at 20:47
@WillNess, I apologize for the maybe stupid and apparently unrelated question, but do I understand correctly that `map fib [bignum,bignum]` costs twice as much as `fig bignum` and, if it costs the same is because of an optimization that has nothing to do with your answer? — Enlico, Jul 30 '22 at 07:46
Slighly rewording: if I have a program that takes an integer from input, passes it to `fib`, takes another integer from input, and passes it to `fib` too, am I correct to say that, even if the user enters twice the same input, the two calls to `fib` are totally duplicated work? Like, if the compiler would optimize that, that would be another memoization that has nothing to do with what you've explained, right? — Enlico, Jul 30 '22 at 07:50

score 24 · Answer 2 · edited May 23 '17 at 11:46

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

did you mean "`fib' n` could be different on a different `n`" perhaps? — Will Ness, Jul 13 '12 at 15:33
I think I wasn't very clear: what I meant was that everything inside `fib`, including `fib'`, could be different on every different `n`. I think the original example is a little bit confusing because `fib'` also depends on its own `n` which shadows the other `n`. — Tikhon Jelvis, Jul 13 '12 at 23:19

score 20 · Answer 3 · answered Jul 13 '12 at 08:47

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

Why is it impractical to memoize a list for each type? In principle, could GHC create a dictionary (much like for calling type class-constrained functions) to contain partially computed lists for each Num type encounterd during runtime? — misterbee, Jan 06 '14 at 21:16
@misterbee In principle, it could, but if the programme calls `fib 1000000` on a lot of types, that eats a ton of memory. To avoid that, one would need a heuristic which lists to throw out of the cache when it grows too large. And such a memoisation strategy would also apply to other functions or values, presumably, so the compiler would have to deal with a potentially great number of things to memoise for potentially many types. I think it would be possible to implement (partial) polymorphic memoisation with a reasonably good heuristic, but I doubt it would be worthwhile. — Daniel Fischer, Jan 06 '14 at 21:35

Валерий Кобзарь · Answer 4 · 2015-04-24T06:11:28.757

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

How is this fibonacci-function memoized?

4 Answers4

Linked