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

[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

[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

[Ben Franksen]

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

[Andreas Abel]

 >    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