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

[Andrew Pennebaker]

>
> 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<https://github.com/mcandre/mcandre/tree/master/haskell/memfib>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.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/haskell-cafe/attachments/20120914/c4392372/attachment.htm>