Memoization
Jump to navigation
Jump to search
The printable version is no longer supported and may have rendering errors. Please update your browser bookmarks and please use the default browser print function instead.
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 naive implementation of Fibonacci numbers without memoization is horribly slow.
Try slow_fib 30, not too much higher than that and it hangs.
slow_fib :: Int -> Integer
slow_fib 0 = 0
slow_fib 1 = 1
slow_fib n = slow_fib (n-2) + slow_fib (n-1)
The memoized version is much faster.
Try memoized_fib 10000.
memoized_fib :: Int -> Integer
memoized_fib =
let fib 0 = 0
fib 1 = 1
fib n = memoized_fib (n-2) + memoized_fib (n-1)
in (map fib [0 ..] !!)