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

[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

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
> Libraries at haskell.org
> 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

andreas.abel at gu.se
http://www.cse.chalmers.se/~abela/