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

[Andrew Martin]

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 <victor at lopezjuan.com>
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
> Libraries at haskell.org
> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
>



-- 
-Andrew Thaddeus Martin
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/libraries/attachments/20171219/9211a6f9/attachment.html>