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.
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
