Expand the Data.Set API

[Joachim Breitner]

Hi,


Am Donnerstag, den 05.03.2015, 17:59 -0500 schrieb David Feuer:
> 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.

+1

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

I’m doubtful about that one.

This is only needed if == is not „the right equality“, in which case a
Set might be the wrong data type. Do we want to advocate that style? 

Also, it will make everyone wonder „do I need insert or theOtherInsert“,
making the API a bit less concise and quick to grasp.

Since "s `union` singleton e" does the right thing with almost the right
performance, maybe that’s sufficient?

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

+1, possibly with the type
        a -> Set a -> Maybe (a, Set a)
to get the remaining set as well.

Greetings,
Joachim




-- 
Joachim “nomeata” Breitner
  mail at joachim-breitner.de • http://www.joachim-breitner.de/
  Jabber: nomeata at joachim-breitner.de  • GPG-Key: 0xF0FBF51F
  Debian Developer: nomeata at debian.org
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 819 bytes
Desc: This is a digitally signed message part
URL: <http://mail.haskell.org/pipermail/libraries/attachments/20150306/a9d1b2fc/attachment.sig>