[Haskell-cafe] Memoization

Gerd M gerd_m1977 at hotmail.com
Fri Oct 7 18:42:53 EDT 2005

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 


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

FREE pop-up blocking with the new MSN Toolbar - get it now! 

More information about the Haskell-Cafe mailing list