(more links to Haskell Cafe)
(distinction between recursive and non-recursive case)
Revision as of 21:36, 5 August 2007
Memoization is a technique for storing values of a function instead of recomputing them each time the function is called.
1 Memoization of arbitrary functions
You need type classes to get a reasonable type for the function you want
memoize :: Memoizable a => (a->b) -> (a->b)
Now, how to implement something like this? Of course, one needs a finite map that stores values b for keys of type a. It turns out that such a map can be constructed recursively based on the structure of a:
Map () b := b Map (Either a a') b := (Map a b, Map a' b) Map (a,a') b := Map a (Map a' b)
Here, Map a b is the type of a finite map from keys a to values b. Its construction is based on the following laws for functions
() -> b =~= b (a + a') -> b =~= (a -> b) x (a' -> b) -- = case analysis (a x a') -> b =~= a -> (a' -> b) -- = currying
For further and detailed explanations, see
2 Memoization of recursively defined functions
Things become more complicated if the function is recursively defined and it shall used memoized calls to itself. A classic example is the recursive computation of Fibonacci numbers.
The naive implementation of Fibonacci numbers without memoization is horribly slow.Try
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 :: 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 ..] !!)
3 Memoizing fix point operator
You can factor out the memoizing trick to a function, the memoizing fix point operator,which we will call
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
I suppose if you want to "put it in a library",you should just put
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 ;-)
In general it is
memoFix :: ((a -> b) -> (a -> b)) -> a -> b memoFix f = let mf = memoize (f mf) in mf
Here we use a special tree as memoizing data structure.
memoFix :: ((Int -> Integer) -> (Int -> Integer)) -> (Int -> Integer) memoFix f = let memo = fmap (f mf) (naturals 1 0) mf = (memo !!!) in mf
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 a
naturals = 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 more
naturals r n = Node n ((naturals $! r2) $! (n+r)) ((naturals $! r2) $! (n+r2)) where r2 = 2*r