PROPOSAL: Add `disjoint` method to `Data.IntSet`
Víctor López Juan
victor at lopezjuan.com
Tue Dec 19 11:04:33 UTC 2017
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
More information about the Libraries
mailing list