Personal tools


From HaskellWiki

(Difference between revisions)
Jump to: navigation, search
m (Memoising CAFS: Fixed link)
m (Memoization with recursion: slight clarification for newer Haskellers)
Line 57: Line 57:
memoized_fib :: Int -> Integer
memoized_fib :: Int -> Integer
memoized_fib =
memoized_fib x = map fib [0 ..] !! x
   let fib 0 = 0
   where fib 0 = 0
      fib 1 = 1
        fib 1 = 1
      fib n = memoized_fib (n-2) + memoized_fib (n-1)
  in  (map fib [0 ..] !!)

Revision as of 22:19, 17 January 2012

Memoization is a technique for storing values of a function instead of recomputing them each time the function is called.


1 Memoization without recursion

You can just write a memoization function using a data structure that is suitable for your application. We don't go into the details of this case. If you want a general solution for several types,

you need a type class, say
memoize :: Memoizable a => (a->b) -> (a->b)

Now, how to implement something like this? Of course, one needs a finite

map that stores values
for keys of type
. It turns out that such a map can be constructed recursively based on the structure of
  Map ()            b  := b
  Map (Either a a') b  := (Map a b, Map a' b)
  Map (a,a')        b  := Map a (Map a' b)
Map a b
is the type of a finite map from keys
to values

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 with recursion

Things become more complicated if the function is recursively defined and it should use 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.

slow_fib 30
, not too much higher than that and it hangs.
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.

memoized_fib 10000
memoized_fib :: Int -> Integer
   where fib 0 = 0
         fib 1 = 1

2.1 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
in, and allow the user to call
memoFix fib
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 ;-)

In general it is

memoFix :: ((a -> b) -> (a -> b)) -> a -> b
memoFix f =
   let mf = memoize (f mf) in mf

3 Efficient tree data structure for maps from Int to somewhere

Here we present a special tree data type (data-inttrie) which is useful as memoizing data structure e.g. for the Fibonacci function.

memoizeInt :: (Int -> a) -> (Int -> a)
memoizeInt f = (fmap f (naturals 1 0) !!!)

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:

   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
such that
naturals!!!n == n
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
s than necessary?
naturals r n =
   Node n
     ((naturals $! r2) $! (n+r))
     ((naturals $! r2) $! (n+r2))
        where r2 = 2*r

4 Memoising CAFS

Note: This is migrated from the old wiki.


The MemoisingCafs idiom also supports recursion.

Consider, for example:

wonderous :: Integer -> Integer
wonderous 1 = 0
wonderous x
  | even x    = 1 + wonderous (x `div` 2)



wonderous2 :: Integer -> Integer
wonderous2 x
  | x <= maxMemo = memoArray ! x
  | otherwise    = wonderous2' x
        maxMemo = 100
        memoArray = array (1,maxMemo)
        wonderous2' 1 = 0
        wonderous2' x
          | even x    = 1 + wonderous2 (x `div` 2)


type MemoTable a = [(Integer, BinTree a)]
wonderous3 :: Integer -> Integer
wonderous3 x
  = searchMemoTable x memoTable
        memoTable :: MemoTable Integer
        memoTable = buildMemoTable 1 5
        buildMemoTable n i
                nextn = n + 2^i
                buildMemoTable' base 0
                    = Leaf (wonderous3' base)
                buildMemoTable' base i
                    = Node (base + midSize)
                           (buildMemoTable' base (i-1))
                        midSize = 2 ^ (i-1)
        searchMemoTable x ((x',tree):ms)
            | x < x'    = searchMemoTree x tree
            | otherwise = searchMemoTable x ms
        searchMemoTree x (Leaf y) = y
        searchMemoTree x (Node mid l r)
            | x < mid   = searchMemoTree x l
            | otherwise = searchMemoTree x r
        wonderous3' 1 = 0
        wonderous3' x
          | even x    = 1 + wonderous3 (x `div` 2)


-- AndrewBromage

5 Memoizing polymorphic functions

What about memoizing polymorphic functions defined with polymorphic recursion? How can such functions be memoized? The caching data structures used in memoization typically handle only one type of argument at a time. For instance, one can have finite maps of differing types, but each concrete finite map holds just one type of key and one type of value.

See the discussion on *Memoizing polymorphic functions*, part one and part two.

6 See also