gerd_m1977 at hotmail.com
Fri Oct 7 14:08:48 EDT 2005
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)
>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!
More information about the Haskell-Cafe