# Memoization

### From HaskellWiki

(link to The Fibonacci sequence) |
(Memoizing fix point operator by Jon Fairbairn) |
||

Line 25: | Line 25: | ||

in (map fib [0 ..] !!) |
in (map fib [0 ..] !!) |
||

</haskell> |
</haskell> |
||

+ | |||

+ | |||

+ | == Memoizing fix point operator == |
||

+ | |||

+ | You can factor out the memoizing trick to a function, the memoizing fix point operator, |
||

+ | which we will call <hask>memoFix</hask> here. |
||

+ | |||

+ | <haskell> |
||

+ | fib :: (Int -> Integer) -> Int -> Integer |
||

+ | fib f 0 = 1 |
||

+ | fib f 1 = 1 |
||

+ | fib f n = f (n-1) + f (n-2) |
||

+ | |||

+ | fibonacci :: Int -> Integer |
||

+ | fibonacci = memoFix fib |
||

+ | |||

+ | </haskell> |
||

+ | |||

+ | I suppose if you want to "put it in a library", |
||

+ | you should just put <hask>fib</hask> in, |
||

+ | and allow the user to call <hask>memoFix fib</hask> to make a new version when necessary. |
||

+ | This allows the user e.g. to define the data structure used for memoization. |
||

+ | |||

+ | The memoising fixpoint operator works |
||

+ | by putting the result of the first call of the function |
||

+ | for each natural number into a data structure and |
||

+ | using that value for subsequent calls ;-) |
||

+ | |||

+ | <haskell> |
||

+ | memoFix :: ((Int -> Integer) -> (Int -> Integer)) -> (Int -> Integer) |
||

+ | memoFix f = mf |
||

+ | where memo = fmap (f mf) (naturals 1 0) |
||

+ | mf = (memo !!!) |
||

+ | </haskell> |
||

+ | |||

+ | A data structure with a node corresponding to each natural number to use as a memo. |
||

+ | |||

+ | <haskell> |
||

+ | data NaturalTree a = Node a (NaturalTree a) (NaturalTree a) |
||

+ | </haskell> |
||

+ | |||

+ | Map the nodes to the naturals in this order: |
||

+ | |||

+ | <code> |
||

+ | 0 |
||

+ | 1 2 |
||

+ | 3 5 4 6 |
||

+ | 7 ... |
||

+ | </code> |
||

+ | |||

+ | Look up the node for a particular number |
||

+ | |||

+ | <haskell> |
||

+ | Node a tl tr !!! 0 = a |
||

+ | Node a tl tr !!! n = |
||

+ | if odd n |
||

+ | then tl !!! top |
||

+ | else tr !!! (top-1) |
||

+ | where top = n `div` 2 |
||

+ | </haskell> |
||

+ | |||

+ | We surely want to be able to map on these things... |
||

+ | |||

+ | <haskell> |
||

+ | instance Functor NaturalTree where |
||

+ | fmap f (Node a tl tr) = Node (f a) (fmap f tl) (fmap f tr) |
||

+ | </haskell> |
||

+ | |||

+ | If only so that we can write cute, |
||

+ | but inefficient things like the below, |
||

+ | which is just a <hask>NaturalTree</hask> |
||

+ | such that <hask>naturals!!!n == n</hask>: |
||

+ | |||

+ | <haskell> |
||

+ | naturals = Node 0 (fmap ((+1).(*2)) naturals) (fmap ((*2).(+1)) naturals) |
||

+ | </haskell> |
||

+ | |||

+ | The following is probably more efficient |
||

+ | (and, having arguments won't hang around at top level, I think) |
||

+ | -- have I put more <hask>$!</hask>s than necessary? |
||

+ | |||

+ | <haskell> |
||

+ | naturals r n = |
||

+ | Node n |
||

+ | ((naturals $! r2) $! (n+r)) |
||

+ | ((naturals $! r2) $! (n+r2)) |
||

+ | where r2 = 2*r |
||

+ | </haskell> |
||

+ | |||

Line 30: | Line 119: | ||

* [http://www.haskell.org/pipermail/haskell-cafe/2007-February/022590.html Haskell-Cafe "speeding up fibonacci with memoizing"] |
* [http://www.haskell.org/pipermail/haskell-cafe/2007-February/022590.html Haskell-Cafe "speeding up fibonacci with memoizing"] |
||

+ | * [http://www.haskell.org/pipermail/haskell-cafe/2007-February/022865.html Haskell-Cafe "memoisation"] |
||

* http://programming.reddit.com/info/16ofr/comments |
* http://programming.reddit.com/info/16ofr/comments |

## Revision as of 21:12, 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 naive implementation of Fibonacci numbers without memoization is horribly slow.

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

## 1 Memoizing fix point operator

You can factor out the memoizing trick to a function, the memoizing fix point operator,

which we will callfib :: (Int -> Integer) -> Int -> Integer fib f 0 = 1 fib f 1 = 1 fib f n = f (n-1) + f (n-2) fibonacci :: Int -> Integer fibonacci = memoFix fib

I suppose if you want to "put it in a library",

you should just putThis allows the user e.g. to define the data structure used for memoization.

The memoising fixpoint operator works by putting the result of the first call of the function for each natural number into a data structure and using that value for subsequent calls ;-)

memoFix :: ((Int -> Integer) -> (Int -> Integer)) -> (Int -> Integer) memoFix f = mf where memo = fmap (f mf) (naturals 1 0) mf = (memo !!!)

A data structure with a node corresponding to each natural number to use as a memo.

data NaturalTree a = Node a (NaturalTree a) (NaturalTree a)

Map the nodes to the naturals in this order:

```
```

```
``` 0
1 2
3 5 4 6
7 ...

```
```

Look up the node for a particular number

Node a tl tr !!! 0 = a Node a tl tr !!! n = if odd n then tl !!! top else tr !!! (top-1) where top = n `div` 2

We surely want to be able to map on these things...

instance Functor NaturalTree where fmap f (Node a tl tr) = Node (f a) (fmap f tl) (fmap f tr)

If only so that we can write cute, but inefficient things like the below,

which is just anaturals = Node 0 (fmap ((+1).(*2)) naturals) (fmap ((*2).(+1)) naturals)

The following is probably more efficient (and, having arguments won't hang around at top level, I think)

-- have I put morenaturals r n = Node n ((naturals $! r2) $! (n+r)) ((naturals $! r2) $! (n+r2)) where r2 = 2*r