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
where
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 noobiness.
_______________________________________________ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell
