Haskell: Why does this work -- an example of memoization?

Question

Hi I am looking at this example from Memoization:

memoized_fib :: Int -> Integer
memoized_fib = (map fib [0 ..] !!)
    where fib 0 = 0
          fib 1 = 1
          fib n = memoized_fib (n-2) + memoized_fib (n-1)

I am just wondering why this even work, since for me if you call memoized_fib(n-2) then you are "creating" a new list and doing things with it and after your return from it the list containing partial result would be gone? So memorized_fib(n-1) won't benefit from it at all?

Answer 1

memoized_fib is a CAF, which is as good as a literal constant in avoiding creation of new stuff. No variables ⇒ no things to bind new stuff to ⇒ no creation of new stuff (in simplified terms).

Answer 2

I can explain missingno's observation, and it may help you understand the behaviour you are seeing. It's important to understand what the where clause desugars to.

The code you presented is

memoized_fib = (map fib [0 ..] !!)
    where fib = ...

which desugars to

memoized_fib = let fib = ...
               in \n -> map fib [0 ..] !! n

missingno presented the following, which looks like a simple eta expansion, but it's not!

memoized_fib n = map fib [0 ..] !! n
    where fib = ...

desugars to

memoized_fib = \n -> let fib = ...
                     in map fib [0 ..] !! n

In the former case you can see that the fib structure is shared between invocations of memoized_fib whereas in the latter casefib is reconstructed each time.

Answer 3

The code that you show depends on a given compiler's behaviour. Here's the desugaring like Tom Ellis suggested:

memoized_fib = 
    let   fib 0 = 0
          fib 1 = 1
          fib n = memoized_fib (n-2) + memoized_fib (n-1)
    in
       (map fib [0 ..] !!)

Nothing guarantees that the list map fib [0..] will be reused, i.e. "shared". Especially when you omit the type signature, like I did, making this a polymorphic definition.

Better make that list explicit, giving it a name:

memoized_fib n = 
    let   fib 0 = 0
          fib 1 = 1
          fib n = g (n-2) + g (n-1)
          g = (fibs !!)
          fibs = map fib [0 ..]
    in
       g n

This was discussed before.