[Haskell-cafe] Tutorial: Haskell for the Evil Genius

[Albert Y. C. Lai]

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.