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.a...@ifi.lmu.de
http://www2.tcs.ifi.lmu.de/~abel/
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
