[Haskell-cafe] Memoization

[Cale Gibbard]

There are too many issues with memoisation to make it completely
automatic. There are however, ways to construct tools to turn
functions into memoising functions selectively.

This paper should be useful to you:
http://research.microsoft.com/Users/simonpj/Papers/weak.htm
It contains a number of implementations of functions which produce
memoized  variants of other functions, with varying semantics. The
methods use unsafePerformIO to create a memo table in an IORef and
pass back a modified version of the function which does a bit of IO
when evaluated to do a lookup in the table and check if there is a
cached result already, and if not, write the IORef back with a
modified memo table and return the value of the function.

The easiest way to memoise a single function however, is simply to
declare a top level value with a bunch of results of the function, and
if it's recursive, make that function use those values of course. You
can use a Map if the input type is in Ord and you don't mind the
log(n) lookup time, or an Array, which works if the input type is in
Ix. Remember when you do this that fromList/array are not going to
force the elements of the list you pass to be computed, so you're safe
to make a list of values of your function and apply fromList or array
to it, and then only when you look in the Map or Array will your
function actually be evaluated.  :)

 - Cale

On 07/10/05, Gerd M <gerd_m1977 at hotmail.com> wrote:
> This works, thanks a lot, you saved my day/night! :-)
>
> >As (memory) is a function, it
> >cannot be memoized (the function can be, but not its result, which is
> >what you're after).
> How can a funcion be memoized but not it's result (what does this mean)!?
> Since there are no side effects in Haskell why is it important that the
> array is a CAF? Or let's say it that way, why can't the results of a (pure)
> function be memoized since it always returns the same result for the same
> parameters?
>
> Regards
>
>
> > > ff t s hmm@(HMM s0 sss sts) = f t s
> > >   where
> > >     f 1 s  =  s ??? sts s0
> > >     f t s  =  memory Map.! (t,s)
> > >
> > >     f' 1 s  =  s ??? sts s0
> > >     f' t s  =  sum [ (f (t-1) s') * (s ??? sts s')  | s' <- sss ]
> > >
> > >     memory  =  Map.fromList [ ((t,s), f' t s) | t <- [1..100], s <- sss ]
> >
> >...which is of course completely untested.  Of course, the "memoizing
> >fixed point combinator" Chris Okasaki posted a while ago would be far
> >more elegant, I'm just too lazy to dig it up.
> >
>
>