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

Christian Maeder maeder at tzi.de
Thu Dec 29 07:42:29 EST 2005


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

main = print $ stats $ take 1000000 $ repeat 1


More information about the Haskell-Cafe mailing list