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/

That's what I got from profiling, for some reason the memoized version is awfully slow: Memoized version: total time = 143.74 secs (7187 ticks @ 20 ms) total alloc = 25,404,766,256 bytes (excludes profiling overheads) COST CENTRE MODULE %time %alloc memory Main 96.9 99.0 con2tag_State# Main 1.6 0.0 Non memoized version: total time = 6.02 secs (301 ticks @ 20 ms) total alloc = 990,958,296 bytes (excludes profiling overheads) COST CENTRE MODULE %time %alloc ??? Prob 61.1 73.1 f Main 10.3 17.8 con2tag_State# Main 7.6 0.0 sumProb Prob 6.6 1.5 tag2con_State# Main 3.3 1.9 con2tag_Out# Main 2.7 0.0 tag2con_Out# Main 2.3 1.9 sumProb Prob 2.0 3.0 stateTr Main 2.0 0.0 mul Prob 1.7 0.8

From: David Roundy To: haskell-cafe@haskell.org Subject: Re: [Haskell-cafe] Memoization Date: Fri, 7 Oct 2005 14:12:39 -0400

On Fri, Oct 07, 2005 at 06:08:48PM +0000, Gerd M wrote:

...

I still don't get it. I changed my code to structurally match your example (see below) but the result is still the same...

How are you timing your function? -- David Roundy _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

_________________________________________________________________ Express yourself instantly with MSN Messenger! Download today it's FREE! http://messenger.msn.click-url.com/go/onm00200471ave/direct/01/

As (memory) is a function, it cannot be memoized (the function can be, but not its result, which is what you're after). How can a funcion be memoized but not it's result (what does this mean)!? Since there are no side effects in Haskell why is it important that the array is a CAF? Or let's say it that way, why can't the results of a (pure) function be memoized since it always returns the same result for the same

This works, thanks a lot, you saved my day/night! :-) parameters? Regards

...

ff t s hmm@(HMM s0 sss sts) = f t s where f 1 s = s ??? sts s0 f t s = memory Map.! (t,s)

f' 1 s = s ??? sts s0 f' t s = sum [ (f (t-1) s') * (s ??? sts s') | s' <- sss ]

memory = Map.fromList [ ((t,s), f' t s) | t <- [1..100], s <- sss ]

...which is of course completely untested. Of course, the "memoizing fixed point combinator" Chris Okasaki posted a while ago would be far more elegant, I'm just too lazy to dig it up.

_________________________________________________________________ FREE pop-up blocking with the new MSN Toolbar - get it now! http://toolbar.msn.click-url.com/go/onm00200415ave/direct/01/

On 2005-10-07 at 22:42-0000 "Gerd M" wrote:

...

As (memory) is a function, it cannot be memoized (the function can be, but not its result, which is what you're after). How can a funcion be memoized but not it's result (what does this mean)!? Since there are no side effects in Haskell why is it important that the array is a CAF? Or let's say it that way, why can't the results of a (pure) function be memoized since it always returns the same result for the same parameters?

I'm a bit rusty on this, but here's an attempt at an explanation. This is an implementation issue; a matter of choice for the implementor. In a function like this:

f x = factorial 100 + x

"factorial 100" doesn't depend on x -- is a CAF -- so it can be lifted out and computed only once. Note that since the value of f doesn't depend on whether this is done, there's no /requirement/ that the compiler do it. In this:

g a = \ x -> factorial a + x

g 100 is equivalent to f, but here the factorial 100 isn't a constant (it depends on a), so the compiler would have to go to extra lengths (known as "full laziness") to ensure that the factorial was kept for each application of g. It's certainly possible for a compiler to do this, but the problem is that if the subexpression that gets retained is infinite, it takes up a lot of space, and there's no way for the programmer to say that it's no longer needed. So compilers tend not to do this. Jón -- Jón Fairbairn Jon.Fairbairn at cl.cam.ac.uk