[Haskell-cafe] Memoization

[Udo Stenzel]

Gerd M wrote:
> I still don't get it. I changed my code to structurally match your example 
> (see below) but the result is still the same...
> 
> f 1 s     (HMM s0 _   sts)  =  s ??? sts s0
> f t s hmm = memory hmm Map.! (t,s)
> 
> memory hmm@(HMM s0 sss sts)
>             = Map.fromList [ ((t,s),f' t s hmm) | t <- [1..100], s <- sss ]
> 
> f' 1 s     (HMM s0 _   sts)  =  s ??? sts s0
> f' t s hmm@(HMM s0 sss sts)
>         = sum [ (f (t-1) s' hmm) * (s ??? sts s')  | s' <- sss ]

I have a hard time following your code, since it is incomplete, but I
think, you're not memoizing anything.  As (memory) is a function, it
cannot be memoized (the function can be, but not its result, which is
what you're after).  You want to memoize (memory hmm), but there's not
place where this could happen.  It is no CAF and it is no common
subexpression that could be pullen out of the recursion.  Try this:

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



Udo.
-- 
Basically my wife was immature.  I'd be at home in the bath and she'd
come in and sink my boats.
		-- Woody Allen
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 189 bytes
Desc: Digital signature
Url : http://www.haskell.org//pipermail/haskell-cafe/attachments/20051007/0fb4d69c/attachment-0001.bin