[Haskell-cafe] memoization

[Andreas Abel]

On 22.07.2013 09:52, Chris Wong wrote:
>> 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)
>>
>
> [.. snipped ..]
>
>> Could someone explain the technical details of why this works? Why is "map
>> fib [0 ..]" not recalculated every time I call memoized_fib?
>
> A binding is memoized if, ignoring everything after the equals sign,
> it looks like a constant.
>
> In other words, these are memoized:
>
>      x = 2
>
>      Just x = blah
>
>      (x, y) = blah
>
>      f = \x -> x + 1
>      -- f = ...
>
> and these are not:
>
>      f x = x + 1
>
>      f (Just x, y) = x + y
>
> If you remove the right-hand side of memoized_fib, you get:
>
>      memoized_fib = ...
>
> This looks like a constant. So the value (map fib [0..] !!) is memoized.
>
> If you change that line to
>
>      memoized_fib x = map fib [0..] !! x
>
> GHC no longer memoizes it, and it runs much more slowly.

True, but the essential thing to be memoized is not memoized_fib, which 
is a function, but the subexpression

   map fib [0..]

which is an infinite list, i.e., a value.

The rule must be like "in

   let x = e

if e is purely applicative, then its subexpressions are memoized."
For instance, the following is also not memoizing:

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

In general, I would not trust such compiler magic, but just let-bind 
anything I want memoized myself:

memoized_fib :: Int -> Integer
memoized_fib x = fibs !! x
     where fibs  = map fib [0..]   -- lazily computed infinite list
           fib 0 = 0
           fib 1 = 1
           fib n = memoized_fib (n-2) + memoized_fib (n-1)

The eta-expansions do not matter.

Cheers,
Andreas

-- 
Andreas Abel  <><      Du bist der geliebte Mensch.

Theoretical Computer Science, University of Munich
Oettingenstr. 67, D-80538 Munich, GERMANY

andreas.abel at ifi.lmu.de
http://www2.tcs.ifi.lmu.de/~abel/