# Memoization

### From HaskellWiki

(Difference between revisions)

(same base case) |
(Int type for list indexes) |
||

Line 8: | Line 8: | ||

Try <hask>slow_fib 30</hask>, not too much higher than that and it hangs. |
Try <hask>slow_fib 30</hask>, not too much higher than that and it hangs. |
||

<haskell> |
<haskell> |
||

− | slow_fib :: Integer -> Integer |
+ | slow_fib :: Int -> Integer |

slow_fib 0 = 0 |
slow_fib 0 = 0 |
||

slow_fib 1 = 1 |
slow_fib 1 = 1 |
||

Line 18: | Line 18: | ||

<haskell> |
<haskell> |
||

− | memoized_fib :: Integer -> Integer |
+ | memoized_fib :: Int -> Integer |

memoized_fib = |
memoized_fib = |
||

let fib 0 = 0 |
let fib 0 = 0 |

## Revision as of 20:10, 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 :: 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.

Trymemoized_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 ..] !!)