Proposal: IntMap.differenceKeysSet for removing an IntSet of keys

[Liyang HU]

Milan Straka <fox <at> ucw.cz> writes:
> > Ticket: http://hackage.haskell.org/trac/ghc/ticket/5242
> 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.

For intersection, sure. I can see plausible use-cases for this too.
Patch 0007.

For union, where would it get a value from, if a key was found in
the set but not the map? Take a function to generate the value from
the key like fromSet? Given union is left-biased in its effect but
not in its type, I'm going to need separate versions to handle the
two ways a map and a set can be combined. Not sure I want to go down
this route, especially as I can't think of a good use-case.

> 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.

I don't understand your reasoning behind not adding the rewrite rules.
Simply don't export differenceKeysSet, as patch 0005 does.

> 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.

Right. I factored "data IntSet" out to a separate module so that
this was possible. This takes its time complexity from O(n*min(n,W))
down to O(n), I believe.

> 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.

Done both! Patch 0006.

Cheers,
/Liyang