<div class="gmail_quote"><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div class="im">Experiment #4:</div>
<br>
fib :: Int -&gt; Int<br>
fib n = mem !! n<br>
<br>
mem :: [Int]<br>
mem = map aux [0..]<br>
-- remark: even [Int] is not a very efficient data structure for this<br>
<br>
aux 0 = 0<br>
aux 1 = 1<br>
aux n = mem!!(n-1) + mem!!(n-2)<br>
<br>
main :: IO ()<br>
main = mapM_ (print . fib) (replicate 10 30)<br>
<br>
Question: How fast is this compared to #1? Why?<br> </blockquote><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
Final remark: Evil geniuses should use the scientific method, not the opinionative method.</blockquote><div> </div><div>Noted and reflected in the new version.</div><div><br></div><div>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 <a href="https://github.com/mcandre/mcandre/tree/master/haskell/memfib">tried these out</a> 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.</div>

<div><br></div><div>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.</div>

<div><br></div><div>The new version of the tutorial includes an ordinary recursive Fibonacci function (fib1.hs), and the same code but renamed to <font face="&#39;courier new&#39;, monospace">fib&#39;</font>, memoized using the <font face="&#39;courier new&#39;, monospace">memo</font> function from the MemoTrie library (fib2.hs), and exposed as <font face="&#39;courier new&#39;, monospace">fib</font>. Unix time information provides real numbers for comparison: The memoized version is clearly much faster.</div>

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