[Haskell-cafe] Memoization

Gerd M gerd_m1977 at hotmail.com
Fri Oct 7 07:51:20 EDT 2005

I'm trying to use Data.Map to memoize computations. Unfortunately this 
didn't improve the runtime of f at all, so there must be something wrong 
with my implementation. Thanks in advance!

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, 
s/=s0 ]

f' 1 s     (HMM s0 _   sts)  =  s ??? sts s0
f' t s hmm@(HMM s0 sss sts)
        = sum [ (memory hmm)Map.!(t-1,s') * (s ??? sts s')  | s' <- sss, s' 
/= s0 ]

Express yourself instantly with MSN Messenger! Download today it's FREE! 

More information about the Haskell-Cafe mailing list