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 |
+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 |
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: -Andrew Thaddeus Martin
_______________________________________________ Libraries mailing list [hidden email] http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries |
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 |
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 |
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 |
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:
_______________________________________________ Libraries mailing list [hidden email] http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries |
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 |
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. _______________________________________________ Libraries mailing list [hidden email] http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries |
Free forum by Nabble | Edit this page |