How does this memoized fibonacci function work?

Question

In the current exercise assignment of the Functional Programming course I'm doing, we've got to make a memoized version of a given function. To explain memoization, the following example is given:

fiblist = [ fibm x | x <- [0..]]

fibm 0 = 0
fibm 1 = 1
fibm n = fiblist !! (n-1) + fiblist !! (n-2)

But I don't fully understand how this works.

Let's call fibm 3.

fibm 3
--> fiblist !! 2 + fibList 1
--> [fibm 0, fibm 1, fibm 2] !! 2 + [fibm 0, fibm 1] !! 1
--> fibm 2 + fibm 1
--> (fiblist !! 1 + fiblist 0) + 1
--> ([fibm 0, fibm 1] !! 1 + [fibm 0] !! 0) + 1
--> (fibm 1 + fibm 0) + 1
--> 1 + 0 + 1
--> 2

From other questions/answers and googling I learned that somehow, the evaluated fiblist is shared between calls.

Does this mean that, for example, for fiblist !! 2 + fiblist !! 1, the list values are only calculated once for fiblist !! 2 and then just reused for fiblist !! 1?

Then the two fibonacci numbers are calculated only once per call, so no exponential number of calls. But what about the "lower" levels of the call in the fiblist function? How do they benefit from the calculated fiblist in the original fibm call?

A related question, which certainly has already been answered on S.O. - looking right now - is about lazy evaluation. Consider ``if (f x) > 0 then f x else 0`` where ``f x`` is some expensive function call. Will ``f x`` be recalculated if the if-condition is true, or will the value simply be reused? — user42179, Mar 21 '13 at 10:03
Concerning your related question [see this](http://stackoverflow.com/q/15084162/485115). — Nikita Volkov, Mar 21 '13 at 10:14
BTW, even if the list is already evaluated, `fiblist !! n` is going to be `O(n)`, and I believe that calculating `fibm n` the first time evaluates `fiblist !! i` for every `i < n`, which is `O(n^2)`. You could do better... — Itai Zukerman, Mar 21 '13 at 12:08
a **borderline duplicate** related question: http://stackoverflow.com/questions/11466284/how-is-this-fibonacci-function-memoized . — Will Ness, Mar 21 '13 at 21:37

score 8 · Accepted Answer · answered Mar 21 '13 at 10:03

The crucial part here is that the list is lazily evaluated, which means that the element isn't computed until the first time it's requested. Once it has been evaluated, however, it's there for anything else to look up. So in your example, you're right in saying that the values are only calculated once for the fiblist !! 2 and then reused for fiblist !! 1.

The 'lower levels' of the fiblist function work in the same way. The first time I call fiblist !! 1 it will be evaluated by calling fibm 1, which is just 1, and this value will then remain in the list. When you try to get up higher Fibonacci number, fiblist will call fibm which will look up those values in lower - and potentially already evaluated - positions of fiblist.

kosmikus · Answer 2 · 2013-03-23T09:32:57.507

Let's walk through the evaluation step by step. In addition to showing the current expression, we show the current state of evaluation of fiblist in memory. There, I write <expr> to denote an unevaluated expression (often called a thunk), and >expr< to denote an unevaluated expression that is currently under evaluation. You can see lazy evaluation in action. The list gets evaluated only as far as demanded, and subcomputations that complete will be shared for future reuse.

   Current expression                       Current evaluation state of fiblist

   fibm 3                                   <[ fibm x | x <- [0..] ]>

->   (simple expansion of the definition)

   fiblist !! (3-1) + fiblist !! (3-2)      <[ fibm x | x <- [0..] ]>

->   ((+) has to evaluate both its arguments to make progress, let's assume
     it starts with the left argument; (!!) traverses the list up to the given
     element and returns the element it finds)

   fibm 2 + fiblist !! (3-2)                <fibm 0> : <fibm 1> : >fibm 2< : <[ fibm x | x <- [3..] ]>

->   (simple expansion of the definition)

   (fiblist !! (2-1) + fiblist !! (2-2)) + fiblist !! (3-2)
                                            <fibm 0> : <fibm 1> : >fibm 2< : <[ fibm x | x <- [3..] ]>

->   (we again start with the first argument to (+),
     computing the result of (!!) does not cause any
     further evaluation of fiblist)

   (fibm 1 + fiblist !! (2-2)) + fiblist !! (3-2)
                                            <fibm 0> : >fibm 1< : >fibm 2< : <[ fibm x | x <- [3..] ]>

->   (expanding fibm 1 returns a result immediately;
     this concludes the computation of fibm 1,
     and the thunk is updated with the result)

   (1 + fiblist !! (2-2)) + fiblist !! (3-2)
                                            <fibm 0> : 1 : >fibm 2< : <[ fibm x | x <- [3..] ]>

->   (now we compute fiblist !! (2-2))

   (1 + fibm 0) + fiblist !! (3-2)          >fibm 0< : 1 : >fibm 2< : <[ fibm x | x <- [3..] ]>

->   (expanding fibm 0 returns 0 immediately, and the
     corresponding thunk can be updated)

   (1 + 0) + fiblist !! (3-2)               0 : 1 : >fibm 2< : <[fibm x | x <- [3..] ]>

->   (we can compute the (+), yielding the result of
     fibm 2; the corresponding thunk is updated)

   1 + fiblist !! (3-2)                     0 : 1 : 1 : <[fibm x | x <- [3..] ]>

->   (now the right argument of (+) has to be evaluated, but (!!)
     will return the already evaluated list element directly)

   1 + 1                                    0 : 1 : 1 : <[fibm x | x <- [3..] ]>

->   (arithmetic; note that as we called fibm 3 directly in the
     beginning, instead of fiblist !! 3, the list is unaffected
     by this final result)

   2                                        0 : 1 : 1 : <[fibm x | x <- [3..] ]>

As fiblist is a global constant (often called a CAF for "constant applicative form"), the partially evaluated state of the list will persist and future calls to fibm will reuse already evaluated elements of the list. The list will eventually grow larger and larger, consuming more and more memory, though.

How does this memoized fibonacci function work?

2 Answers2

Linked