Expand the Data.Set API

Herbert Valerio Riedel hvr at gnu.org
Fri Mar 6 11:43:57 UTC 2015

On 2015-03-05 at 23:59:23 +0100, David Feuer wrote:
> There are a few rather conspicuously missing features:


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

Maybe (2) and (3) can be combined, c.f.


there's related tickets in unordered-containers too:


(even though those are for associative arrays, it'd be good if we could
come up with a coherent story for these operations rather than ending up
with subtly differently named/typed operations -- assuming it makes
sense to find a uniform scheme)


More information about the Libraries mailing list