Memoization
From HaskellWiki
(Difference between revisions)
(Fibonacci, memoization with a simple list) |
(same base case) |
||
| Line 9: | Line 9: | ||
<haskell> | <haskell> | ||
slow_fib :: Integer -> Integer | slow_fib :: Integer -> Integer | ||
| + | slow_fib 0 = 0 | ||
slow_fib 1 = 1 | slow_fib 1 = 1 | ||
| - | |||
slow_fib n = slow_fib (n-2) + slow_fib (n-1) | slow_fib n = slow_fib (n-2) + slow_fib (n-1) | ||
</haskell> | </haskell> | ||
| Line 20: | Line 20: | ||
memoized_fib :: Integer -> Integer | memoized_fib :: Integer -> Integer | ||
memoized_fib = | memoized_fib = | ||
| - | let fib | + | let fib 0 = 0 |
| - | fib | + | fib 1 = 1 |
| - | fib | + | fib n = memoized_fib (n-2) + memoized_fib (n-1) |
| - | in (map fib | + | in (map fib [0 ..] !!) |
</haskell> | </haskell> | ||
Revision as of 20:09, 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.
Tryslow_fib 30
slow_fib :: Integer -> 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.
Trymemoized_fib 10000
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 ..] !!)
