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