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

[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

Post by Víctor López Juan
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
- 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].
- 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.
- 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
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

[Joachim Breitner]

Hi,

Post by Andreas Abel
+1 for "disjoint".

+1

Post by Andreas Abel
I think "overlaps" falls below the Fairbairn threshold.

✓

Post by Andreas Abel
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

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

✓

Cheers,
Joachim

[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

Post by Joachim Breitner
Hi,

Post by Andreas Abel
+1 for "disjoint".

+1

Post by Andreas Abel
I think "overlaps" falls below the Fairbairn threshold.

✓

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

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

Post by Andreas Abel
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
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

[Henning Thielemann]

Post by Víctor López Juan
(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'.

[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 <

Post by Henning Thielemann

Post by Víctor López Juan
(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
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

[Andreas Abel]

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.

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
(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
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
<http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries>
_______________________________________________
Libraries mailing list
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

[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.

Post by Andreas Abel
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.

Post by 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 <
(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
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
<http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries>
_______________________________________________
Libraries mailing list
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
http://www.cse.chalmers.se/~abela/
_______________________________________________
Libraries mailing list
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

[Andrew Martin]

I'm +1 on disjoint and -1 on overlaps since someone can just write `not
(disjoint x y)`.

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
- 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].
- 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.
- 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
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries