On 10/7/05, Gerd M
Hello, 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 ]
I would use an array, which has O(1) lookup... Instead of changing your code, I'll give a bit more well-known example (partially because I'm in a bit of a rush :-)). Here's a fib function memoized for the first 100 n (using a general approach with arrays, instead of the zipWith thing) import Data.Array fib 0 = 1 fib 1 = 1 fib n | n <= 100 = fibarr!n | otherwise = fib' n fibarr = listArray (2,100) [ fib' x | x <- [2..100]] fib' n = fib (n-1) + fib (n-2) The array is lazy in its elements (but not its indices) so the array of 100 fibs won't actually be computed until you request a fib (then all fibs < n will be computed). So basically, define an array which contains the value of the function at each entry, make sure you use the array in defining these elements if your function is recursive (top-level, it doesn't change the correctness but if you define it in a local scope your implementation probably won't save the entries in the array between calls which kinda ruins the point of memoization!). /S -- Sebastian Sylvan +46(0)736-818655 UIN: 44640862