On 2/18/07, Thomas Hartman
-- versus, try memoized_fibs !! 10000 memoized_fibs = map memoized_fib [1..] memoized_fib = ((map fib' [0 ..]) !!) where fib' 0 = 0 fib' 1 = 1 fib' n = memoized_fib (n - 1) + memoized_fib (n - 2)
How about this: zip_fibs = 0 : 1 : [x+y | ~(x,y) <- zip zip_fibs (tail zip_fibs)] zip_fib = (!!) zip_fibs A naïve performance test: ---------------------------------------------------------------- module Main (main) where import System (getArgs) zip_fibs = 0 : 1 : [x+y | ~(x,y) <- zip zip_fibs (tail zip_fibs)] zip_fib = (!!) zip_fibs memoized_fibs = map memoized_fib [1..] memoized_fib = ((map fib' [0 ..]) !!) where fib' 0 = 0 fib' 1 = 1 fib' n = memoized_fib (n - 1) + memoized_fib (n - 2) main = do [func,arg] <- getArgs let n = read arg case func of "zip_fib" -> do putStrLn $ "Using 'zip_fib' to calculate fib of " ++ arg putStrLn $ " -> " ++ show (zip_fib n) "memoized_fib" -> do putStrLn $ "Using 'memoized_fib' to calculate fib of " ++ arg putStrLn $ " -> " ++ show (memoized_fibs !! n) ---------------------------------------------------------------- $ rm *.o $ ghc --version The Glorious Glasgow Haskell Compilation System, version 6.4.2 $ ghc -O fib.hs $ time ./a.out zip_fib 20000 Using 'zip_fib' to calculate fib of 20000 -> 25311623237323612422[...]39857683971213093125 real 0m0.140s user 0m0.106s sys 0m0.001s $ time ./a.out memoized_fib 20000 Using 'memoized_fib' to calculate fib of 20000 -> 25311623237323612422[...]39857683971213093125 real 0m30.787s user 0m29.509s sys 0m0.156s $ time ./a.out zip_fib 200000 Using 'zip_fib' to calculate fib of 200000 -> 15085683557988938992[...]52246259408175853125 real 0m24.790s user 0m23.649s sys 0m0.159s No, I *won't* try './a.out memoized_fib 200000' ;-). -- Felipe.