# Memoization

### From HaskellWiki

(Difference between revisions)

(short explanation) |
(Fibonacci, memoization with a simple list) |
||

Line 2: | Line 2: | ||

'''Memoization''' is a technique for storing values of a function instead of recomputing them each time the function is called. |
'''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 number]]s. |
||

+ | |||

+ | The immediate implementation of Fibonacci numbers without memoization is horribly slow. |
||

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

+ | <haskell> |
||

+ | slow_fib :: Integer -> Integer |
||

+ | slow_fib 1 = 1 |
||

+ | slow_fib 2 = 1 |
||

+ | slow_fib n = slow_fib (n-2) + slow_fib (n-1) |
||

+ | </haskell> |
||

+ | |||

+ | The memoized version is much faster. |
||

+ | Try <hask>memoized_fib 10000</hask>. |
||

+ | |||

+ | <haskell> |
||

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

+ | </haskell> |
||

+ | |||

== See also == |
== See also == |

## 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.

Tryslow_fib 30

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.

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