(Fibonacci, memoization with a simple list)
Revision as of 20:02, 5 August 2007
Memoization is a technique for storing values of a function instead of recomputing them each time the function is called.
A classic example is the recursive computation of Fibonacci numbers.
The immediate implementation of Fibonacci numbers without memoization is horribly slow.Try
slow_fib :: Integer -> Integer slow_fib 1 = 1 slow_fib 2 = 1 slow_fib n = slow_fib (n-2) + slow_fib (n-1)
The memoized version is much faster.Try
memoized_fib :: Integer -> Integer memoized_fib = let fib' 0 = 0 fib' 1 = 1 fib' n = memoized_fib (n-2) + memoized_fib (n-1) in (map fib' [0 ..] !!)