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.

Noted and reflected in the new version.

Thank you for taking the time to write out a detailed, practical analysis of the question. Yes, I should assume less and test more. I tried these out as requested, and came up with results demonstrating that Haskell, does not, as I mistakenly interpreted, automatically memoize all function calls. Which makes sense, otherwise memory would quickly run out.

I found some useful reference code on the Haskell Wiki and constructed my own memoized Fibonacci function using the MemoTrie library, which, fortunately, is builtin with Haskell Platform and therefore does not require the tutorial reader to install additional code.

The new version of the tutorial includes an ordinary recursive Fibonacci function (fib1.hs), and the same code but renamed to fib', memoized using the memo function from the MemoTrie library (fib2.hs), and exposed as fib. Unix time information provides real numbers for comparison: The memoized version is clearly much faster.

I rewrote the section, deleting the part that stated memoization was automatic, and added text describing how Haskell makes memoization easy.