[Haskell-cafe] memoization

Christopher Howard christopher.howard at frigidcode.com
Mon Jul 22 08:59:12 CEST 2013

When I previously asked about memoization, I got the impression that
memoization is not something that just happens magically in Haskell.
Yet, on a Haskell wiki page about Memoization
an example given is

    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 guess this works because, for example, I tried "memoized_fib 10000"
and the interpreter took three or four seconds to calculate. But every
subsequent call to "memoized_fib 10000" returns instantaneously (as does
"memoized_fib 10001").

Could someone explain the technical details of why this works? Why is
"map fib [0 ..]" not recalculated every time I call memoized_fib?
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/haskell-cafe/attachments/20130721/e3f101d5/attachment.htm>

More information about the Haskell-Cafe mailing list