> 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.fa...@gmail.com w: http://lfairy.github.io/ _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe