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.
Which version of the Haskell Platform are you using? I tried running your memoized Fibonacci function that uses the MemoTrie library on Windows XP with Service Pack 3, and received the following error message:
$>./runhaskell fib2
fib2.hs:3:7: Could not find module `Data.Memotrie': Use -v to see a list of the files searched for.
My version is as follows:
$>./ghci -v GHCi, version 6.12.3: http://www.haskell.org/ghc/ :? for help Glasgow Haskell Compiler, Version 6.12.3, for Haskell 98, stage 2 booted by GHC version 6.10.4 Using binary package database: C:\PROGRA~1\HASKEL~1\201020~1.0\lib\package.conf. d\package.cache hiding package base-3.0.3.2 to avoid conflict with later version base-4.2.0.2 wired-in package ghc-prim mapped to ghc-prim-0.2.0.0-2feb0cb38f65a4827135ada88c3 4f3ef wired-in package integer-gmp mapped to integer-gmp-0.2.0.1-72436e28c79d056c87cc0 d2d2f9f3773 wired-in package base mapped to base-4.2.0.2-0d1804f62045e52b2e806996d84f5318 wired-in package rts mapped to builtin_rts wired-in package haskell98 mapped to haskell98-1.0.1.1-b5196101fd7a8c42a8d53bd80 33d6765 wired-in package template-haskell mapped to template-haskell-2.4.0.1-401621dedd4 a5f07bfd8630247358bf5 wired-in package dph-seq mapped to dph-seq-0.4.0-be069f0bb710922a6ddd4ed2b91e3a6 c wired-in package dph-par mapped to dph-par-0.4.0-b31a0ce10b7c92126978fcc929077ad 6 Hsc static flags: -static Loading package ghc-prim ... linking ... done. Loading package integer-gmp ... linking ... done. Loading package base ... linking ... done. Loading package ffi-1.0 ... linking ... done.
For reference, my code is as follows:
#!"c:/Program Files/Haskell Platform/2010.2.0.0/bin/" runhaskell
import Data.Memotrie (memo)
fib :: Int -> Int fib = memo fib' where fib' :: Int -> Int fib' 0 = 0 fib' 1 = 1 fib' n = fib' (n - 1) + fib' (n - 2)
main :: IO () main = do putStrLn (show (fib 30))
Thank you. -- Benjamin L. Russell -- Benjamin L. Russell / DekuDekuplex at Yahoo dot com http://dekudekuplex.wordpress.com/ Translator/Interpreter / Mobile: +011 81 90-6526-1406 "Furuike ya, kawazu tobikomu mizu no oto." -- Matsuo Basho^