Milan Straka
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