PROPOSAL: Add `disjoint` method to `Data.IntSet`

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

PROPOSAL: Add `disjoint` method to `Data.IntSet`

Víctor López Juan
Proposal:

Add a method disjoint :: IntSet → IntSet → Bool,
to Data.IntSet, such that
prop> disjoint a b ≡ null (intersection a b)

Alternatively or additionally, add a method
overlaps :: IntSet -> IntSet -> Bool
such that
prop> a `overlaps` b ≡ not.null$ intersection a b

Rationale:

- I have found it useful to have such a method when keeping track of the
set of free-variables in a term. I believe that there can be more use
cases.

- There are already similar specialized implementations in the library.
For example, isSubsetOf :: IntSet -> IntSet -> Bool is such that
prop> a `isSubsetOf` b ≡ (a == (a `intersection` b)).

- Having `disjoint`, the user can also check whether two sets overlap
with `(not.).disjoint`. This is shorter and more self-explaining than
(not.null$ intersection).

- A specialized implementation of `disjoint` (vs. (null.).intersection)
can shortcircuit as soon as the sets overlap on one element. This leads
to significant speed-ups; for example, 23× when checking that the sets
{1,2,3…,2¹²} and {2,4,6,…,2¹²} are not disjoint [1].

Discussion:

I would like to get some comments on this proposal. In particular:

- Should any of these methods be added?
- Should both `overlaps` and `disjoint` be added?
- If only one of them is added, which one should it be?

I hope a decision about the proposal can be reached before 2018-01-09.

See also:
- Proposed patch [2]
- Previous discussion [3]

[1] https://github.com/haskell/containers/pull/377#issuecomment-352585171
[2] https://github.com/haskell/containers/pull/377/files
[3] https://github.com/haskell/containers/pull/377
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: PROPOSAL: Add `disjoint` method to `Data.IntSet`

Andreas Abel
+1 for "disjoint".

I think "overlaps" falls below the Fairbairn threshold.  I always
wondered why there is a "notMember" function in the Set interface,
saving us 3 key presses.

One thing to consider: Data.Set should then also be equipped with a
function "disjoint", to keep interfaces in sync.

Best,
Andreas

On 19.12.2017 12:04, Víctor López Juan wrote:

> Proposal:
>
> Add a method disjoint :: IntSet → IntSet → Bool,
> to Data.IntSet, such that
> prop> disjoint a b ≡ null (intersection a b)
>
> Alternatively or additionally, add a method
> overlaps :: IntSet -> IntSet -> Bool
> such that
> prop> a `overlaps` b ≡ not.null$ intersection a b
>
> Rationale:
>
> - I have found it useful to have such a method when keeping track of the
> set of free-variables in a term. I believe that there can be more use
> cases.
>
> - There are already similar specialized implementations in the library.
> For example, isSubsetOf :: IntSet -> IntSet -> Bool is such that
> prop> a `isSubsetOf` b ≡ (a == (a `intersection` b)).
>
> - Having `disjoint`, the user can also check whether two sets overlap
> with `(not.).disjoint`. This is shorter and more self-explaining than
> (not.null$ intersection).
>
> - A specialized implementation of `disjoint` (vs. (null.).intersection)
> can shortcircuit as soon as the sets overlap on one element. This leads
> to significant speed-ups; for example, 23× when checking that the sets
> {1,2,3…,2¹²} and {2,4,6,…,2¹²} are not disjoint [1].
>
> Discussion:
>
> I would like to get some comments on this proposal. In particular:
>
> - Should any of these methods be added?
> - Should both `overlaps` and `disjoint` be added?
> - If only one of them is added, which one should it be?
>
> I hope a decision about the proposal can be reached before 2018-01-09.
>
> See also:
> - Proposed patch [2]
> - Previous discussion [3]
>
> [1] https://github.com/haskell/containers/pull/377#issuecomment-352585171
> [2] https://github.com/haskell/containers/pull/377/files
> [3] https://github.com/haskell/containers/pull/377
> _______________________________________________
> Libraries mailing list
> [hidden email]
> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
>


--
Andreas Abel  <><      Du bist der geliebte Mensch.

Department of Computer Science and Engineering
Chalmers and Gothenburg University, Sweden

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

Re: PROPOSAL: Add `disjoint` method to `Data.IntSet`

Andrew Martin
In reply to this post by Víctor López Juan
I'm +1 on disjoint and -1 on overlaps since someone can just write `not (disjoint x y)`.

On Tue, Dec 19, 2017 at 6:04 AM, Víctor López Juan <[hidden email]> wrote:
Proposal:

Add a method disjoint :: IntSet → IntSet → Bool,
to Data.IntSet, such that
prop> disjoint a b ≡ null (intersection a b)

Alternatively or additionally, add a method
overlaps :: IntSet -> IntSet -> Bool
such that
prop> a `overlaps` b ≡ not.null$ intersection a b

Rationale:

- I have found it useful to have such a method when keeping track of the
set of free-variables in a term. I believe that there can be more use
cases.

- There are already similar specialized implementations in the library.
For example, isSubsetOf :: IntSet -> IntSet -> Bool is such that
prop> a `isSubsetOf` b ≡ (a == (a `intersection` b)).

- Having `disjoint`, the user can also check whether two sets overlap
with `(not.).disjoint`. This is shorter and more self-explaining than
(not.null$ intersection).

- A specialized implementation of `disjoint` (vs. (null.).intersection)
can shortcircuit as soon as the sets overlap on one element. This leads
to significant speed-ups; for example, 23× when checking that the sets
{1,2,3…,2¹²} and {2,4,6,…,2¹²} are not disjoint [1].

Discussion:

I would like to get some comments on this proposal. In particular:

- Should any of these methods be added?
- Should both `overlaps` and `disjoint` be added?
- If only one of them is added, which one should it be?

I hope a decision about the proposal can be reached before 2018-01-09.

See also:
- Proposed patch [2]
- Previous discussion [3]

[1] https://github.com/haskell/containers/pull/377#issuecomment-352585171
[2] https://github.com/haskell/containers/pull/377/files
[3] https://github.com/haskell/containers/pull/377
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries



--
-Andrew Thaddeus Martin

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

Re: PROPOSAL: Add `disjoint` method to `Data.IntSet`

Joachim Breitner-2
In reply to this post by Andreas Abel
Hi,

Am Dienstag, den 19.12.2017, 13:44 +0100 schrieb Andreas Abel:
> +1 for "disjoint".


+1

> I think "overlaps" falls below the Fairbairn threshold.



>  I always
> wondered why there is a "notMember" function in the Set interface,
> saving us 3 key presses.

Probably because of use like this:

   filter (`notMember` seen) todo            -- pretty

vs.

   filter (not . (`member` seen)) todo       -- too many parenthesis.

Of course

   filter (\x -> not (x `member` seen)) todo -- is also ok

And I will refrain from pointing out that with the idea of no-white-
space-means-higher-precedence[1] would allow

   filter (not . `member`seen) todo          -- too many parenthesis.


[1] https://www.joachim-breitner.de/blog/730-Less_parentheses

>  One thing to consider: Data.Set should then also be equipped with a
> function "disjoint", to keep interfaces in sync.



Cheers,
Joachim
--
Joachim Breitner
  [hidden email]
  http://www.joachim-breitner.de/

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

signature.asc (849 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: PROPOSAL: Add `disjoint` method to `Data.IntSet`

Víctor López Juan
I'm thinking that `disjoint` is already a negation:
(dis- (not) + joint (united)). When composing with `not`, the user gets
a double negation `not (disjoint x y)`. There is a then a small mental
effort required to go from "not disjoint" to "overlapping".

If we are going to have only one of the two properties, I would rather
have the positive one (`overlaps`) as primitive. Then `disjoint` would
be written "not (overlaps x y)", which reads quite easily.
(Or even "not (x `overlaps` y)").

— Víctor

Den 2017-12-19 kl. 16:01, skrev Joachim Breitner:

> Hi,
>
> Am Dienstag, den 19.12.2017, 13:44 +0100 schrieb Andreas Abel:
>> +1 for "disjoint".
>
>
> +1
>
>> I think "overlaps" falls below the Fairbairn threshold.
>
> ✓
>
>>  I always
>> wondered why there is a "notMember" function in the Set interface,
>> saving us 3 key presses.
>
> Probably because of use like this:
>
>    filter (`notMember` seen) todo            -- pretty
>
> vs.
>
>    filter (not . (`member` seen)) todo       -- too many parenthesis.
>
> Of course
>
>    filter (\x -> not (x `member` seen)) todo -- is also ok
>
> And I will refrain from pointing out that with the idea of no-white-
> space-means-higher-precedence[1] would allow
>
>    filter (not . `member`seen) todo          -- too many parenthesis.
>
>
> [1] https://www.joachim-breitner.de/blog/730-Less_parentheses
>
>>  One thing to consider: Data.Set should then also be equipped with a
>> function "disjoint", to keep interfaces in sync.
>
> ✓
>
> Cheers,
> Joachim
>
>
>
> _______________________________________________
> 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

signature.asc (849 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: PROPOSAL: Add `disjoint` method to `Data.IntSet`

Henning Thielemann

On Tue, 19 Dec 2017, Víctor López Juan wrote:

> I'm thinking that `disjoint` is already a negation:
> (dis- (not) + joint (united)). When composing with `not`, the user gets
> a double negation `not (disjoint x y)`. There is a then a small mental
> effort required to go from "not disjoint" to "overlapping".
>
> If we are going to have only one of the two properties, I would rather
> have the positive one (`overlaps`) as primitive. Then `disjoint` would
> be written "not (overlaps x y)", which reads quite easily.
> (Or even "not (x `overlaps` y)").

I also dislike double negation and think that 'disjoint' is one. I'd
prefer to see both 'overlap' and 'disjoint'.
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: PROPOSAL: Add `disjoint` method to `Data.IntSet`

Tikhon Jelvis
In practice, I hear people talking about "disjoint" sets all the time—it comes up a lot more often than "overlapping" or "not overlapping". It might have a negative in the name semantically, but it's used as an atomic word in practice. (That is, when people say "disjoint" they're *thinking* "disjoint" as opposed to "not joint" or "not overlapping".)

I'm in favor of naming functions with common usage in mind, and I think "disjoint" is the word people use most often in this context.

On Tue, Dec 19, 2017 at 7:44 AM, Henning Thielemann <[hidden email]> wrote:

On Tue, 19 Dec 2017, Víctor López Juan wrote:

I'm thinking that `disjoint` is already a negation:
(dis- (not) + joint (united)). When composing with `not`, the user gets
a double negation `not (disjoint x y)`. There is a then a small mental
effort required to go from "not disjoint" to "overlapping".

If we are going to have only one of the two properties, I would rather
have the positive one (`overlaps`) as primitive. Then `disjoint` would
be written "not (overlaps x y)", which reads quite easily.
(Or even "not (x `overlaps` y)").

I also dislike double negation and think that 'disjoint' is one. I'd prefer to see both 'overlap' and 'disjoint'.
_______________________________________________
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: PROPOSAL: Add `disjoint` method to `Data.IntSet`

Andreas Abel-2
I am thinking along the lines of Tikhon.

Sets "overlap" is a rather uncommon term.  [If we were all
constructivists, the situation would be different.  Constructively,
"overlap" is certainly the primitive notion, and "disjoint" only its
negation.]

We can't introduce a positive term for everything.  For instance, we all
use

   not . null

rather than having predicates like "isCons", "inhabited" etc.

On 19.12.2017 19:01, Tikhon Jelvis wrote:

> In practice, I hear people talking about "disjoint" sets all the time—it
> comes up a lot more often than "overlapping" or "not overlapping". It
> might have a negative in the name semantically, but it's used as an
> atomic word in practice. (That is, when people say "disjoint" they're
> *thinking* "disjoint" as opposed to "not joint" or "not overlapping".)
>
> I'm in favor of naming functions with common usage in mind, and I think
> "disjoint" is the word people use most often in this context.
>
> On Tue, Dec 19, 2017 at 7:44 AM, Henning Thielemann
> <[hidden email] <mailto:[hidden email]>>
> wrote:
>
>
>     On Tue, 19 Dec 2017, Víctor López Juan wrote:
>
>         I'm thinking that `disjoint` is already a negation:
>         (dis- (not) + joint (united)). When composing with `not`, the
>         user gets
>         a double negation `not (disjoint x y)`. There is a then a small
>         mental
>         effort required to go from "not disjoint" to "overlapping".
>
>         If we are going to have only one of the two properties, I would
>         rather
>         have the positive one (`overlaps`) as primitive. Then `disjoint`
>         would
>         be written "not (overlaps x y)", which reads quite easily.
>         (Or even "not (x `overlaps` y)").
>
>
>     I also dislike double negation and think that 'disjoint' is one. I'd
>     prefer to see both 'overlap' and 'disjoint'.
>     _______________________________________________
>     Libraries mailing list
>     [hidden email] <mailto:[hidden email]>
>     http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
>     <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  <><      Du bist der geliebte Mensch.

Department of Computer Science and Engineering
Chalmers and Gothenburg University, Sweden

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

Re: PROPOSAL: Add `disjoint` method to `Data.IntSet`

David Feuer
Would all constructivists actually say so? I'd think there could be some who think that

disjoint :: (s, t : Set a) -> x : a -> Either (Not (elem x s)) (Not (elem x t))

in which case being disjoint is a stronger property than just not overlapping. But of course,
none of this is really relevant to Haskell.


On Dec 19, 2017 6:46 PM, "Andreas Abel" <[hidden email]> wrote:
I am thinking along the lines of Tikhon.

Sets "overlap" is a rather uncommon term.  [If we were all constructivists, the situation would be different.  Constructively, "overlap" is certainly the primitive notion, and "disjoint" only its negation.]

We can't introduce a positive term for everything.  For instance, we all use

  not . null

rather than having predicates like "isCons", "inhabited" etc.

On 19.12.2017 19:01, Tikhon Jelvis wrote:
In practice, I hear people talking about "disjoint" sets all the time—it comes up a lot more often than "overlapping" or "not overlapping". It might have a negative in the name semantically, but it's used as an atomic word in practice. (That is, when people say "disjoint" they're *thinking* "disjoint" as opposed to "not joint" or "not overlapping".)

I'm in favor of naming functions with common usage in mind, and I think "disjoint" is the word people use most often in this context.

On Tue, Dec 19, 2017 at 7:44 AM, Henning Thielemann <[hidden email] <mailto:[hidden email]>> wrote:


    On Tue, 19 Dec 2017, Víctor López Juan wrote:

        I'm thinking that `disjoint` is already a negation:
        (dis- (not) + joint (united)). When composing with `not`, the
        user gets
        a double negation `not (disjoint x y)`. There is a then a small
        mental
        effort required to go from "not disjoint" to "overlapping".

        If we are going to have only one of the two properties, I would
        rather
        have the positive one (`overlaps`) as primitive. Then `disjoint`
        would
        be written "not (overlaps x y)", which reads quite easily.
        (Or even "not (x `overlaps` y)").


    I also dislike double negation and think that 'disjoint' is one. I'd
    prefer to see both 'overlap' and 'disjoint'.
    _______________________________________________
    Libraries mailing list
    [hidden email] <mailto:[hidden email]>
    http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
    <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  <><      Du bist der geliebte Mensch.

Department of Computer Science and Engineering
Chalmers and Gothenburg University, Sweden

[hidden email]
http://www.cse.chalmers.se/~abela/
_______________________________________________
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