Re: Symmetric difference for Set and IntSet

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

Re: Symmetric difference for Set and IntSet

Andrew Lelechenko
On 18 Jun 2020, at 23:42, Bardur Arantsson <[hidden email]> wrote:
> 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.


This is probably orthogonal to my proposal here, because it does not improve the performance of symmetricDifference. Maps are more flexible in this aspect, because there are merge tactics, which allow to encode any set operation.

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

David Feuer
Map merges can do even more, because they work with arbitrary Applicative functors. So a functor like

    data Triple a = Triple a a a
    instance Applicative Triple where
      pure a = Triple a a a
      liftA2 f (Triple x y z) (Triple p q r) = Triple (f x p) (f y q) (f z r)

can be used to calculate union, intersection, *and* symmetric difference all in one go. I should just bite the bullet and implement that for sets.

On Fri, Jun 26, 2020, 1:16 PM Andrew Lelechenko <[hidden email]> wrote:
On 18 Jun 2020, at 23:42, Bardur Arantsson <[hidden email]> wrote:
> 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.


This is probably orthogonal to my proposal here, because it does not improve the performance of symmetricDifference. Maps are more flexible in this aspect, because there are merge tactics, which allow to encode any set operation.

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

Haskell - Libraries mailing list
I have opened https://github.com/haskell/containers/issues/732 to
track this idea.

Am Fr., 26. Juni 2020 um 19:27 Uhr schrieb David Feuer <[hidden email]>:

>
> Map merges can do even more, because they work with arbitrary Applicative functors. So a functor like
>
>     data Triple a = Triple a a a
>     instance Applicative Triple where
>       pure a = Triple a a a
>       liftA2 f (Triple x y z) (Triple p q r) = Triple (f x p) (f y q) (f z r)
>
> can be used to calculate union, intersection, *and* symmetric difference all in one go. I should just bite the bullet and implement that for sets.
>
> On Fri, Jun 26, 2020, 1:16 PM Andrew Lelechenko <[hidden email]> wrote:
>>
>> On 18 Jun 2020, at 23:42, Bardur Arantsson <[hidden email]> wrote:
>> > 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.
>>
>>
>> This is probably orthogonal to my proposal here, because it does not improve the performance of symmetricDifference. Maps are more flexible in this aspect, because there are merge tactics, which allow to encode any set operation.
>>
>> 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
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries