[Haskell-cafe] strange stack overflow with Data.Map
jeanphilippe.bernardy at gmail.com
Thu Dec 29 10:24:02 EST 2005
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 ?
> 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.
More information about the Libraries