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

David Roundy droundy at abridgegame.org
Thu Dec 29 09:56:02 EST 2005

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.

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?
David Roundy

More information about the Libraries mailing list