<div dir="ltr">I'm +1 on disjoint and -1 on overlaps since someone can just write `not (disjoint x y)`.</div><div class="gmail_extra"><br><div class="gmail_quote">On Tue, Dec 19, 2017 at 6:04 AM, Víctor López Juan <span dir="ltr"><<a href="mailto:victor@lopezjuan.com" target="_blank">victor@lopezjuan.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">Proposal:<br>
<br>
Add a method disjoint :: IntSet → IntSet → Bool,<br>
to Data.IntSet, such that<br>
prop> disjoint a b ≡ null (intersection a b)<br>
<br>
Alternatively or additionally, add a method<br>
overlaps :: IntSet -> IntSet -> Bool<br>
such that<br>
prop> a `overlaps` b ≡ not.null$ intersection a b<br>
<br>
Rationale:<br>
<br>
- I have found it useful to have such a method when keeping track of the<br>
set of free-variables in a term. I believe that there can be more use<br>
cases.<br>
<br>
- There are already similar specialized implementations in the library.<br>
For example, isSubsetOf :: IntSet -> IntSet -> Bool is such that<br>
prop> a `isSubsetOf` b ≡ (a == (a `intersection` b)).<br>
<br>
- Having `disjoint`, the user can also check whether two sets overlap<br>
with `(not.).disjoint`. This is shorter and more self-explaining than<br>
(not.null$ intersection).<br>
<br>
- A specialized implementation of `disjoint` (vs. (null.).intersection)<br>
can shortcircuit as soon as the sets overlap on one element. This leads<br>
to significant speed-ups; for example, 23× when checking that the sets<br>
{1,2,3…,2¹²} and {2,4,6,…,2¹²} are not disjoint [1].<br>
<br>
Discussion:<br>
<br>
I would like to get some comments on this proposal. In particular:<br>
<br>
- Should any of these methods be added?<br>
- Should both `overlaps` and `disjoint` be added?<br>
- If only one of them is added, which one should it be?<br>
<br>
I hope a decision about the proposal can be reached before 2018-01-09.<br>
<br>
See also:<br>
- Proposed patch [2]<br>
- Previous discussion [3]<br>
<br>
[1] <a href="https://github.com/haskell/containers/pull/377#issuecomment-352585171" rel="noreferrer" target="_blank">https://github.com/haskell/<wbr>containers/pull/377#<wbr>issuecomment-352585171</a><br>
[2] <a href="https://github.com/haskell/containers/pull/377/files" rel="noreferrer" target="_blank">https://github.com/haskell/<wbr>containers/pull/377/files</a><br>
[3] <a href="https://github.com/haskell/containers/pull/377" rel="noreferrer" target="_blank">https://github.com/haskell/<wbr>containers/pull/377</a><br>
______________________________<wbr>_________________<br>
Libraries mailing list<br>
<a href="mailto:Libraries@haskell.org">Libraries@haskell.org</a><br>
<a href="http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries" rel="noreferrer" target="_blank">http://mail.haskell.org/cgi-<wbr>bin/mailman/listinfo/libraries</a><br>
</blockquote></div><br><br clear="all"><div><br></div>-- <br><div class="gmail_signature" data-smartmail="gmail_signature">-Andrew Thaddeus Martin</div>
</div>