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 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!).
_________________________________________________________________ Express yourself instantly with MSN Messenger! Download today it's FREE! http://messenger.msn.click-url.com/go/onm00200471ave/direct/01/