[Haskell-cafe] memoization

[Chris Wong]

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

--
Chris Wong, fixpoint conjurer
  e: lambda.fairy at gmail.com
  w: http://lfairy.github.io/