Re: [Haskell-cafe] strange stack overflow with Data.Map

On Thu, Dec 29, 2005 at 04:24:02PM +0100, Jean-Philippe Bernardy wrote:

On 12/29/05, David Roundy wrote:

...

On Thu, Dec 29, 2005 at 01:42:29PM +0100, Christian Maeder wrote:

...

...

...

stats elems = foldl add_elem Map.empty elems add_elem m x = Map.insertWith (+) x 1 m

...

main = print $ stats $ take 1000000 $ repeat 1

This program has a space leak and runs out of stack space. I'm guessing that I'm being bit here by an unnatural amount of laziness in Map.insertWith, but I can't see how to fix this. :( I'm sure it's something elementary...

David Roundy wrote: try:

stats = foldl' add_elem Map.empty add_elem m x = myinsertWith (+) x 1 m

myinsertWith f k v m = case Map.lookup k m of Nothing -> Map.insert k v m Just w -> let r = f v w in r `seq` Map.insert k r m

Thanks, that does it! I had tried something like that, but without the foldl', and had tried foldl', but without the myinsertWith. The reason I didn't spend much time using this implementation is that for large maps, it will take twice as long as Map.insertWith, so I assumed (incorrectly) that Map.insertWith should be written so that it behaves in a non-leaky manner.

I'm not sure I understand this ... Do you say that the leaky program is faster than the non-leaky one ?

No, what I mean is that Map.insertWith only traverses the Map once, while myinsertWith has to traverse it twice, so for a large map, each call to myinsertWith will take twice as long as Map.insertWith. Or to put it a different way, if myinsertWith were part of the Map module, it could be twice as fast.

...

Should the Map modules have an additional Map.insertWith' that behaves strictly, or might it be the case that you always want strict behavior when using insertWith?

IMO, there is always a possibility for needing the lazy version. I also have to say that making a strict version for each "...With" does not fill my heart with joy. :) Such cases call for cheapness analysis, or optimistic evaluation, or some other kind of solution implemented at the compiler level, IMHO.

I agree, there is a possibility for wanting the lazy version. If you only want to provite one insertWith, I suppose you'd want to figure out whether the lazy or strict version is more commonly needed (or "safer"), and make people wanting the other version implement it themselves. In my opinion, the strict version seems nicer, largely because HNF is cheap for most "large" computations I do, so strictness wouldn't cost much. On the subject of excessive functions, what are the uses of insertWithKey? It seems like anything you do with insertWithKey you could just as efficiently do with insertWith... it seems pretty trivial to write insertWithKey f k x = insertWith (f k) k x There may be a use to all the WithKey variants, but I'd much rather have strict varients... -- David Roundy http://www.darcs.net