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                                                        
  • 14
    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 7:51
  • 1
    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 8:24

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

  • 4
    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 1fib' 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
  • 1
    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: hpaste.org/71406
    – Vitus
    Jul 13 '12 at 15:12
  • 1
    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
  • 1
    @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 6 '14 at 22:03
  • 1
    @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 7 '18 at 7:22

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. Jul 13 '12 at 23:19

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 6 '14 at 21:16
  • 1
    @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. Jan 6 '14 at 21:35

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 op (n1:val1) (n2:val2) = (n1 + n2) : (zipWith op val1 val2)
zipWith _ _ _ = []


print $ take 100 fib



Time elapsed: 0.00018s


Your Answer

