containers: symmetricDifference for Set and HashSet

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
5 messages Options
Reply | Threaded
Open this post in threaded view
|

containers: symmetricDifference for Set and HashSet

Ben Franksen
Would it make sense to add a function like the following to containers:

  symmetricDifference :: Set a -> Set a -> (Set a, Set a, Set a)
  symmetricDifference a b = (a \\ b, a `intersection` b, b \\ a)

with the idea that this can be implemented more efficiently as a
primitive than the above specification? (And similarly for HashSet.)

If this is the case, then perhaps difference and intersection could be
defined in terms of this new primitive:

  difference a b = let (r, _, _) = symmetricDifference in r
  intersection a b = let (_, r, _) = symmetricDifference in r

*if* it turns out that this does not degrade performance.

Cheers
Ben

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

Re: containers: symmetricDifference for Set and HashSet

David Feuer
This has been raised before. I'm going to try to look at implementation within the next week or so.

On Tue, Dec 1, 2020, 4:17 AM Ben Franksen <[hidden email]> wrote:
Would it make sense to add a function like the following to containers:

  symmetricDifference :: Set a -> Set a -> (Set a, Set a, Set a)
  symmetricDifference a b = (a \\ b, a `intersection` b, b \\ a)

with the idea that this can be implemented more efficiently as a
primitive than the above specification? (And similarly for HashSet.)

If this is the case, then perhaps difference and intersection could be
defined in terms of this new primitive:

  difference a b = let (r, _, _) = symmetricDifference in r
  intersection a b = let (_, r, _) = symmetricDifference in r

*if* it turns out that this does not degrade performance.

Cheers
Ben

_______________________________________________
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: containers: symmetricDifference for Set and HashSet

Haskell - Libraries mailing list
A few months ago we briefly discussed a function with a slightly different type:

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

See https://mail.haskell.org/pipermail/libraries/2020-June/030632.html.

Am Di., 1. Dez. 2020 um 10:19 Uhr schrieb David Feuer <[hidden email]>:

>
> This has been raised before. I'm going to try to look at implementation within the next week or so.
>
> On Tue, Dec 1, 2020, 4:17 AM Ben Franksen <[hidden email]> wrote:
>>
>> Would it make sense to add a function like the following to containers:
>>
>>   symmetricDifference :: Set a -> Set a -> (Set a, Set a, Set a)
>>   symmetricDifference a b = (a \\ b, a `intersection` b, b \\ a)
>>
>> with the idea that this can be implemented more efficiently as a
>> primitive than the above specification? (And similarly for HashSet.)
>>
>> If this is the case, then perhaps difference and intersection could be
>> defined in terms of this new primitive:
>>
>>   difference a b = let (r, _, _) = symmetricDifference in r
>>   intersection a b = let (_, r, _) = symmetricDifference in r
>>
>> *if* it turns out that this does not degrade performance.
>>
>> Cheers
>> Ben
>>
>> _______________________________________________
>> 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
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: containers: symmetricDifference for Set and HashSet

Ben Franksen
In reply to this post by David Feuer
Thanks David!

I wasn't aware this has been discussed before, though I should have
expected it, given that the idea seems pretty obvious.

BTW, something similar may be possible for Map and HashMap by adding an
extra parameter that tells it how to combine values in the intersection.

Cheers
Ben

Am 01.12.20 um 10:18 schrieb David Feuer:

> This has been raised before. I'm going to try to look at implementation
> within the next week or so.
>
> On Tue, Dec 1, 2020, 4:17 AM Ben Franksen <[hidden email]> wrote:
>
>> Would it make sense to add a function like the following to containers:
>>
>>   symmetricDifference :: Set a -> Set a -> (Set a, Set a, Set a)
>>   symmetricDifference a b = (a \\ b, a `intersection` b, b \\ a)
>>
>> with the idea that this can be implemented more efficiently as a
>> primitive than the above specification? (And similarly for HashSet.)
>>
>> If this is the case, then perhaps difference and intersection could be
>> defined in terms of this new primitive:
>>
>>   difference a b = let (r, _, _) = symmetricDifference in r
>>   intersection a b = let (_, r, _) = symmetricDifference in r
>>
>> *if* it turns out that this does not degrade performance.
>>
>> Cheers
>> Ben
>>
>> _______________________________________________
>> 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
>


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

Re: containers: symmetricDifference for Set and HashSet

Andreas Abel
In reply to this post by Ben Franksen
 >    symmetricDifference :: Set a -> Set a -> (Set a, Set a, Set a)

Since projections from a 3-tuples are not in base (why?, one could
wonder), I plea for a telling result name that helps confusing these
three outputs.  Something like

data SymmetricDifference = SymmetricDifference
   { symDiffLeft   :: Set a
   , symDiffCommon :: Set a
   , symDiffRight  :: Set a
   }

(Also fixing the problem of absent projections.)

On 2020-12-01 10:16, Ben Franksen wrote:

> Would it make sense to add a function like the following to containers:
>
>    symmetricDifference :: Set a -> Set a -> (Set a, Set a, Set a)
>    symmetricDifference a b = (a \\ b, a `intersection` b, b \\ a)
>
> with the idea that this can be implemented more efficiently as a
> primitive than the above specification? (And similarly for HashSet.)
>
> If this is the case, then perhaps difference and intersection could be
> defined in terms of this new primitive:
>
>    difference a b = let (r, _, _) = symmetricDifference in r
>    intersection a b = let (_, r, _) = symmetricDifference in r
>
> *if* it turns out that this does not degrade performance.
>
> Cheers
> Ben
>
> _______________________________________________
> 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