On Friday 09 July 2010 00:10:24, Daniel Fischer wrote:

You can also use a library (e.g. http://hackage.haskell.org/package/data- memocombinators) to do the memoisation for you.

Well, actualy, I think http://hackage.haskell.org/package/MemoTrie would be the better choice for the moment, data-memocombinators doesn't seem to offer the functionality we need out of the box.

On Friday 09 July 2010 01:03:48, Luke Palmer wrote:

On Thu, Jul 8, 2010 at 4:23 PM, Daniel Fischer wrote:

...

On Friday 09 July 2010 00:10:24, Daniel Fischer wrote:

...

You can also use a library (e.g. http://hackage.haskell.org/package/data- memocombinators) to do the memoisation for you.

Well, actualy, I think http://hackage.haskell.org/package/MemoTrie would be the better choice for the moment, data-memocombinators doesn't seem to offer the functionality we need out of the box.

I'm interested to hear what functionality MemoTrie has that data-memocombinators does not. I wrote the latter in hopes that it would be strictly more powerful*.

It's probably my night-blindness, but I didn't see an immediate way to memoise a simple function on a short look at the docs, like memo :: (ConstraintOn a) => (a -> b) -> a -> b , which Data.MemoTrie provides (together with memo2 and memo3, which data- memocombinators provide too). Taking a closer look at the docs in daylight, I see data-mc provides that out of the box too, the stuff is just differently named (bool, char, integral, ...) - which I didn't expect. So you could take it as an indication that I'm visually impaired, or as an indication that the docs aren't as obvious as they could be. Cheers, Daniel

Luke

* Actually MemoTrie wasn't around when I wrote that, but I meant the combinatory technique should be strictly more powerful than a typeclass technique. And data-memocombinators has many primitives, so I'm still curious.

On 7/8/10 9:17 PM, Michael Mossey wrote:

Daniel Fischer wrote:

...

If f has the appropriate type and the base case is f 0 = 0,

module Memo where

import Data.Array

f :: (Integral a, Ord a, Ix a) => a -> a f n = memo ! n where memo = array (0,n) $ (0,0) : [(i, max i (memo!(i `quot` 2) + memo!(i `quot` 3) + memo!(i `quot` 4))) | i <- [1 .. n]]

is wasteful regarding space, but it calculates only the needed values and very simple.

Can someone explain to a beginner like me why this calculates only the needed values? The list comprehension draws from 1..n so I don't understand why all those values wouldn't be computed.

The second pair of each element of the list will remain unevaluated until demanded --- it's the beauty of being a lazy language. :-) Put another way, although it might look like the list contains values (and technically it does due to referential transparency), at a lower level what it actually contains are pairs such that the second element is represented not by number but rather by a function that can be called to obtain its value. Cheers, Greg

You're correct in pointing out that f uses memoization inside of itself to cache the intermediate values that it commutes, but those values don't get shared between invocations of f; thus, if you call f with the same value of n several times then the memo table might get reconstructed redundantly. (However, there are other strategies for memoization that are persistent across calls.) Cheers, Greg On 7/8/10 9:59 PM, Michael Mossey wrote:

Thanks, okay the next question is: how does the memoization work? Each call to memo seems to construct a new array, if the same f(n) is encountered several times in the recursive branching, it would be computed several times. Am I wrong? Thanks, Mike

Gregory Crosswhite wrote:

...

On 7/8/10 9:17 PM, Michael Mossey wrote:

...

Daniel Fischer wrote:

...

If f has the appropriate type and the base case is f 0 = 0,

module Memo where

import Data.Array

f :: (Integral a, Ord a, Ix a) => a -> a f n = memo ! n where memo = array (0,n) $ (0,0) : [(i, max i (memo!(i `quot` 2) + memo!(i `quot` 3) + memo!(i `quot` 4))) | i <- [1 .. n]]

is wasteful regarding space, but it calculates only the needed values and very simple.

Can someone explain to a beginner like me why this calculates only the needed values? The list comprehension draws from 1..n so I don't understand why all those values wouldn't be computed.

The second pair of each element of the list will remain unevaluated until demanded --- it's the beauty of being a lazy language. :-) Put another way, although it might look like the list contains values (and technically it does due to referential transparency), at a lower level what it actually contains are pairs such that the second element is represented not by number but rather by a function that can be called to obtain its value.

Cheers, Greg

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

---

Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

That actually doesn't work as long as memo is an array, since then it has fixed size; you have to also make memo an infinitely large data (but lazy) structure so that it can hold results for arbitrary n. One option for doing this of course is to make memo be an infinite list, but a more space and time efficient option is to use a trie like in MemoTrie. Cheers, Greg On 7/9/10 12:50 AM, Heinrich Apfelmus wrote:

Gregory Crosswhite wrote:

...

You're correct in pointing out that f uses memoization inside of itself to cache the intermediate values that it commutes, but those values don't get shared between invocations of f; thus, if you call f with the same value of n several times then the memo table might get reconstructed redundantly. (However, there are other strategies for memoization that are persistent across calls.)

It should be

f = \n -> memo ! n where memo = ..

so that memo is shared across multiple calls like f 1 , f 2 etc.

Regards, Heinrich Apfelmus

-- http://apfelmus.nfshost.com

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

Very true. I was executing the large Int-based examples on a 64 bit machine. You can of course flip over to Integer on either 32 or 64 bit machines and alleviate the problem with undetected overflow. Of course that doesn't help with negative initial inputs ;) I do agree It is still probably a good idea to either filter the negative case like you do here, or, since it is well defined, extend the scope of the memo table to the full Int range by explicitly memoizing negative vales as well. -Edward Kmett On Fri, Jul 9, 2010 at 11:51 AM, Mike Dillon wrote:

begin Edward Kmett quotation:

...

The result is considerably faster:

*Main> fastest_f 12380192300 67652175206

*Main> fastest_f 12793129379123 120695231674999

I just thought I'd point out that running with these particular values on a machine with a 32 bit Int will cause your machine to go deep into swap... Anything constant greater that maxBound is being wrapped back to the negative side, causing havoc to ensue. I changed the open version of "f" to look like this to exclude negative values:

f :: (Int -> Int) -> Int -> Int f mf 0 = 0 f mf n | n < 0 = error $ "Invalid n value: " ++ show n f mf n | otherwise = max n $ mf (div n 2) + mf (div n 3) + mf (div n 4)

-md