On 12-09-14 05:18 PM, Andrew Pennebaker wrote:
One thing I want to double check is that Haskell does, in fact, automatically memoize all pure function calls. Is this true?
A simple back-of-envelope calculation that immediately raises doubts: 2 seconds on a 2 GHz computer is 4x10^9 clock cycles, or something between 10^9 to 4x10^9 steps. This sounds more like 2^30 recursive calls to fib, not 30. Even with interpreter inefficiency. A simple experiment to nail the coffin: Experiment #1: fib :: Int -> Int fib 0 = 0 fib 1 = 1 fib n = fib (n - 1) + fib (n - 2) main :: IO () main = mapM_ (print . fib) (replicate 10 30) Null hypothesis: fibs are memoized, therefore the first printing takes 2 seconds, the remaining 9 printings are free. Alternative hypothesis: fibs are not memoized, therefore every printing takes 2 seconds. Observation: ______________________ Which hypothesis to reject: _______ A few advanced experiments to mess with your mind: Experiment #2: fib :: Int -> Int fib 0 = 0 fib 1 = 1 fib n = fib (n - 1) + fib (n - 2) main :: IO () main = let y = fib 30 in mapM_ print (replicate 10 y) Question: Is anything memoized here? Which thing? Experiment #3: fib :: Int -> Int fib 0 = 0 fib 1 = 1 fib n = fib (n - 1) + fib (n - 2) main :: IO () main = mapM_ print (replicate 10 (fib 30)) Question: is this like #1? or is this like #2? Experiment #4: fib :: Int -> Int fib n = mem !! n mem :: [Int] mem = map aux [0..] -- remark: even [Int] is not a very efficient data structure for this aux 0 = 0 aux 1 = 1 aux n = mem!!(n-1) + mem!!(n-2) main :: IO () main = mapM_ (print . fib) (replicate 10 30) Question: How fast is this compared to #1? Why? Final remark: Evil geniuses should use the scientific method, not the opinionative method.