[Haskell-cafe] Memoization

[Gerd M]

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/