2 ms·
It isn't memoizing anything here. If it were memoizing, do you think it would take 0.48 seconds? Laziness is not the same thing as memoization of function arg
by SamReidHughes 19y ago
It isn't memoizing anything here. If it were memoizing, do you think it would take 0.48 seconds? Laziness is not the same thing as memoization of function arguments.
- dfranke 19y agoOkay, apparently I didn't quite think this one through. I wasn't claiming that GHC memoizes values, but it does memoize thunks. I thought this algorithm would be getting some benefit from that, but having inserted some trace statements, I was apparently wrong. Here's a version that really is memoized: import Control.Parallel import Control.Monad import Text.Printf cutoff = 35 fibs = [ fib n | n <- [0..] ] fib' :: Int -> Integer fib' 0 = 0 fib' 1 = 1 fib' n = fibs !! (n-1) + fibs !! (n-2) fib :: Int -> Integer fib n | n < cutoff = fib' n | otherwise = r `par` (l `seq` l + r) where l = fibs !! (n-1) r = fibs !! (n-2) main = forM_ [0..45] $ \i -> printf "n=%d => %d\n" i (fib i)