[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
http://www.darcs.net
More information about the Haskell-Cafe
mailing list