Proposal: IntMap.differenceKeysSet for removing an IntSet of keys

[Milan Straka]

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