[Haskell] combining IntMaps

Scherrer, Chad Chad.Scherrer at pnl.gov
Tue Jul 19 23:05:21 EDT 2005

I'm using the (IntMap Int) type to implement functions (Int -> Int), by
treating non-keys as values that map to zero. I'd like to be able to add
two of these pointwise, and delete the key from the resulting map when
the sum of the values is zero. My specification is

addMaps :: IntMap Int -> IntMap Int -> IntMap Int
addMaps m = IntMap.filter (/= 0) . IntMap.unionWith (+) m

But I'm not really happy with this because it traverses both maps for
the union, and then traverses the result to get rid of all the zeros.
(This function is a performance bottleneck in my current code).

I thought I could do something like

addMaps' :: IntMap Int -> IntMap Int -> IntMap Int
addMaps' = IntMap.foldWithKey f
    f k x = IntMap.update (maybeAdd x) k
    maybeAdd x v = let s = v + x in if s == 0 then Nothing else Just s

But this is no good, because IntMap.update only affects those keys where
lookup succeeds, so
IntMap.update (maybeAdd 3) 8 IntMap.empty
returns IntMap.empty, rather than a map with 8 -> 3 as I had hoped.

What would you suggest to help addMaps run faster? Do I need to pry open
the IntMap implementation to do better?

Thanks so much,
Chad Scherrer

PS - I mistakenly crosslisted this to the GHC users list, because I
didn't realize how the mailing lists were set up. Please excuse my
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org//pipermail/haskell/attachments/20050719/e15ebbe9/attachment-0001.htm

More information about the Haskell mailing list