Hi,
Ticket: http://hackage.haskell.org/trac/ghc/ticket/5242
Currently, IntMap.difference ma mb removes all the keys in mb from ma, where the elements of the two IntMaps can be of different types; the elements of mb are not used.
There is no efficient way to remove an IntSet of keys, however. These patches adds the IntMap.differenceKeysSet function—essentially a copy/paste of difference—that satisfies the following property:
prop_DiffKeysSet :: Map Int -> Map () -> Bool prop_DiffKeysSet t1 t2 = difference t1 t2 == differenceKeysSet t1 (keysSet t2)
Cons: Not so happy with the name. Code bloat.
another problem is that more methods could be overloaded for IntSets -- also union and intersect. Adding the variant only for difference seems quite arbitrary, but adding all is bloating the API. I liked the second idea with the fromSet :: (Key -> a) -> IntSet.IntSet -> IntMap a but I would not add the rewriting rules. The intermediate IntMap has to be constructed, but I think it is reasonable price for doing cross-structure operations and not extending the API. Instead we could make fromSet more efficient -- if the IntMap could access the internal representation of IntSet, the can implement fromSet just by adding values to each node. The strictness annotations are a bit harmful here -- if they were not there, only the parts of the structure needed for the following difference (union, intersect) would be constructed. BTW, seeing the IntSet representation in IntMap would allow us to define keysSet more efficient too. Currently if you want to do IntSet \\ IntMap, you can use IntSet.difference set (IntMap.keysSet map), with fromSet we could do IntMap \\ IntSet by IntMap.difference map (IntMap.fromSet (const ()) set), which seems nicely analogous. Cheers, Milan