Symmetric difference for Set and IntSet

classic Classic list List threaded Threaded
3 messages Options
Reply | Threaded
Open this post in threaded view
|

Symmetric difference for Set and IntSet

Andrew Lelechenko
Hi all,

I propose to add a new combining function to `Data.Set` and `Data.IntSet` with the following semantics (but better implementation):

symmetricDifference :: Set a -> Set a -> Set a
symmetricDifference x y = (x \\ y) <> (y \\ x)

The context is that Federico (CC'ed) is working on a GSoC project about faster factorisation algorithms in `arithmoi` (http://hackage.haskell.org/package/arithmoi), and the symmetric difference is a basic building block for sparse linear algebra over GF(2) field.

Best regards,
Andrew
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Symmetric difference for Set and IntSet

Haskell - Libraries mailing list
+1

Symmetric difference has previously briefly come up on the containers
issue tracker: https://github.com/haskell/containers/issues/162#issuecomment-222337552

David mentions the idea of a generalized merge API similarly to the
one for Map and IntMap there, which would be nice to have now. Not a
prerequisite for the addition though IMHO.

Am Mi., 17. Juni 2020 um 21:25 Uhr schrieb Andrew Lelechenko
<[hidden email]>:

>
> Hi all,
>
> I propose to add a new combining function to `Data.Set` and `Data.IntSet` with the following semantics (but better implementation):
>
> symmetricDifference :: Set a -> Set a -> Set a
> symmetricDifference x y = (x \\ y) <> (y \\ x)
>
> The context is that Federico (CC'ed) is working on a GSoC project about faster factorisation algorithms in `arithmoi` (http://hackage.haskell.org/package/arithmoi), and the symmetric difference is a basic building block for sparse linear algebra over GF(2) field.
>
> Best regards,
> Andrew
> _______________________________________________
> Libraries mailing list
> [hidden email]
> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Symmetric difference for Set and IntSet

Bardur Arantsson-2
In reply to this post by Andrew Lelechenko
On 17/06/2020 21.25, Andrew Lelechenko wrote:
> Hi all,
>
> I propose to add a new combining function to `Data.Set` and `Data.IntSet` with the following semantics (but better implementation):
>
> symmetricDifference :: Set a -> Set a -> Set a
> symmetricDifference x y = (x \\ y) <> (y \\ x)
>
> The context is that Federico (CC'ed) is working on a GSoC project about faster factorisation algorithms in `arithmoi` (http://hackage.haskell.org/package/arithmoi), and the symmetric difference is a basic building block for sparse linear algebra over GF(2) field.
>

+½.

I think it's probably going to be useful, but I would suggest an
algorithm which actually returns each of the terms here (as a tuple), i.e.

   The "added" bits
   The "removed" bits
   The "common" bits

This may not be *that* useful for sets per se, but I've lost count of
how often I've had to implement a similar thing for maps.

_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries