Expand the Data.Set API

David Feuer david.feuer at gmail.com
Thu Mar 5 22:59:23 UTC 2015

There are a few rather conspicuously missing features:

1. A way to take the intersection of a list of sets. This shouldn't
really be a big deal, and it already exists for unions, but the
intersection version should probably sort the sets by size before
folding, or otherwise try to do something smart.

2. A way to insert an element if an == one is not already present
(insert replaces an existing one with a new one). Currently, as far as
I can tell, this can only be done using either

  if e `member` s then s else insert e s
which potentially descends the tree twice for no reason


  s `union` singleton e

which is documented as being O(|s|+1), although I wouldn't be shocked
if the documentation were too pessimistic in this case.

3. A way to delete an element and simultaneously find out whether it
was in the set.

David Feuer

More information about the Libraries mailing list