[Haskell-cafe] Memoization

Gerd M 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)
>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! 

More information about the Haskell-Cafe mailing list