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

[David Roundy]

On Thu, Dec 29, 2005 at 04:24:02PM +0100, Jean-Philippe Bernardy wrote:
> On 12/29/05, David Roundy <droundy at abridgegame.org> wrote:
> > On Thu, Dec 29, 2005 at 01:42:29PM +0100, Christian Maeder wrote:
> > > David Roundy 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...
> > > 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