[Haskell-cafe] memoization
Chris Wong
chrisyco+haskell-cafe at gmail.com
Mon Jul 22 09:52:06 CEST 2013
> 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/
More information about the Haskell-Cafe
mailing list