<div dir="ltr">On Fri, Oct 13, 2017 at 4:52 PM, Christopher Whidden <span dir="ltr"><<a href="mailto:christopher.whidden@gmail.com" target="_blank">christopher.whidden@gmail.com</a>></span> wrote:<br><div class="gmail_extra"><div class="gmail_quote"><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div style="word-wrap:break-word;line-break:after-white-space">Using the term “lexicographically” implies to me that the Element type must conform to Comparable, as would be required for a total order. The Sequence method you mention, lexicographicallyPrecedes(_:), does have this constraint, whereas the method in question for elementsEqual(_:) / lexicographicallyEquals(_:) only has the constraint that the Element is Equatable. As an example, an array of simple enums has no default lexicographical ordering but is still able to use this method because enums (without associated values) are Equatable by default:<div><br></div><div><div style="margin:0px;font-stretch:normal;line-height:normal;font-family:Menlo;background-color:rgb(255,255,255)"><span style="color:rgb(186,45,162)"><b>enum</b></span> Foo {</div><div style="margin:0px;font-stretch:normal;line-height:normal;font-family:Menlo;background-color:rgb(255,255,255)"> <span style="color:rgb(186,45,162)"><b>case</b></span> bar</div><div style="margin:0px;font-stretch:normal;line-height:normal;font-family:Menlo;background-color:rgb(255,255,255)"> <span style="color:rgb(186,45,162)"><b>case</b></span> baz</div><div style="margin:0px;font-stretch:normal;line-height:normal;font-family:Menlo;background-color:rgb(255,255,255)">}</div><div style="margin:0px;font-stretch:normal;line-height:normal;background-color:rgb(255,255,255);min-height:14px"><br></div><div style="margin:0px;font-stretch:normal;line-height:normal;font-family:Menlo;background-color:rgb(255,255,255)"><span style="color:rgb(186,45,162)"><b>let</b></span> f1 = [<span style="color:rgb(79,129,135)">Foo</span>.<span style="color:rgb(49,89,93)">bar</span>, <span style="color:rgb(79,129,135)">Foo</span>.<span style="color:rgb(49,89,93)">baz</span>]</div><div style="margin:0px;font-stretch:normal;line-height:normal;font-family:Menlo;background-color:rgb(255,255,255)"><span style="color:rgb(186,45,162)"><b>let</b></span> f2 = [<span style="color:rgb(79,129,135)">Foo</span>.<span style="color:rgb(49,89,93)">baz</span>, <span style="color:rgb(79,129,135)">Foo</span>.<span style="color:rgb(49,89,93)">bar</span>]</div><div style="margin:0px;font-stretch:normal;line-height:normal;background-color:rgb(255,255,255);min-height:14px"><br></div><div style="margin:0px;font-stretch:normal;line-height:normal;font-family:Menlo;color:rgb(62,30,129);background-color:rgb(255,255,255)"><span style="color:rgb(79,129,135)">f1</span><span style="color:rgb(0,0,0)">.</span>elementsEqual<span style="color:rgb(0,0,0)">(</span><span style="color:rgb(79,129,135)">f2</span><span style="color:rgb(0,0,0)">) //false</span></div><div style="margin:0px;font-stretch:normal;line-height:normal;font-family:Menlo;color:rgb(62,30,129);background-color:rgb(255,255,255)"><div style="margin:0px;font-stretch:normal;line-height:normal"><span style="color:rgb(79,129,135)">f1</span><span style="color:rgb(0,0,0)">.</span>elementsEqual<span style="color:rgb(0,0,0)">(</span><span style="color:rgb(79,129,135)">f2</span><span style="color:rgb(0,0,0)">.</span>reversed<span style="color:rgb(0,0,0)">()<wbr>) //true</span></div></div><div><br></div><div>I also share Jonathan’s concerns that some programmers may misinterpret [lexicographically][Equals] to mean [sorted in lexicographical order][compare sequence equality], which is not what the method in question does.</div><div><br></div><div>Xiaodi, I think you are right that Sequence.sequentiallyEquals is to close to "==" to use, but I think we have to find something better here.</div><div><br></div><div>I’ll recommend that we use the name <i>Sequence.<wbr>iterativelyEquals(_:)</i> since this describes the body of the method concisely. A rough abbreviation of this algorithm is:</div><div><br></div><div>1. Iterate over elements in two sequences</div><div><span class="m_1477040427581921272Apple-tab-span" style="white-space:pre-wrap"> </span>a. Compare elements for equality</div><div><br></div><div>“iterativelyEquals" concisely describes this.</div></div></div></blockquote><div><br></div><div>That's an intriguing alternative. The key quality to be communicated, practically speaking, is that if two instances `x` and `y` compare `true` with `elementsEqual`, then `for i in x { ... }` and `for i in y { ... }` should be substitutable (if the elements of `x` and `y` are not consumed on the first iteration), because the semantics of `Equatable` demand that "equivalence means substitutability." This would be captured by something like the name you suggest, or to be even more explicit:</div><div><br></div><div>```</div><div>x.substitutesForThePurposesOfIteratedAccess(for: y)</div><div>```</div><div><br></div><div>This is intentionally unwieldy to attract others to try to do better :) But I think it captures the meaning we are going for here.</div><div><br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div style="word-wrap:break-word;line-break:after-white-space"><div><br><blockquote type="cite"><div><div class="h5"><div>On Oct 12, 2017, at 6:24 PM, Xiaodi Wu via swift-evolution <<a href="mailto:swift-evolution@swift.org" target="_blank">swift-evolution@swift.org</a>> wrote:</div><br class="m_1477040427581921272Apple-interchange-newline"></div></div><div><div><div class="h5"><div dir="ltr"><h1>Rename <code>Sequence.elementsEqual</code></h1>
<ul><li>Proposal: <a href="https://gist.github.com/xwu/NNNN-rename-elements-equal.md" target="_blank">SE-NNNN</a></li><li>Authors: <a href="https://github.com/xwu" target="_blank">Xiaodi Wu</a></li><li>Review Manager: TBD</li><li>Status: <strong>Awaiting review</strong></li></ul><h2><a href="https://gist.github.com/xwu/1f0ef4e18a7f321f22ca65a2f56772f6#introduction" class="m_1477040427581921272gmail-anchor" id="m_1477040427581921272gmail-user-content-introduction" target="_blank"></a>Introduction</h2><p>The current behavior of <code>Sequence.elementsEqual</code> is
potentially confusing to users given its name. Having surveyed the
alternative solutions to this problem, it is proposed that the method be
renamed to <code>Sequence.<wbr>lexicographicallyEquals</code>.</p>
<h2><a href="https://gist.github.com/xwu/1f0ef4e18a7f321f22ca65a2f56772f6#motivation" class="m_1477040427581921272gmail-anchor" id="m_1477040427581921272gmail-user-content-motivation" target="_blank"></a>Motivation</h2><p><a href="https://twitter.com/olebegemann/status/916291785185529857" target="_blank">As outlined by Ole Begemann</a>, use of <code>Sequence.elementsEqual(_:)</code> can lead to surprising results if the sequences compared are unordered:</p>
<div class="m_1477040427581921272gmail-highlight m_1477040427581921272gmail-highlight-source-swift"><pre><span class="m_1477040427581921272gmail-pl-k">var</span> set1<span class="m_1477040427581921272gmail-pl-k">:</span> <span class="m_1477040427581921272gmail-pl-c1">Set</span><span class="m_1477040427581921272gmail-pl-k"><</span><span class="m_1477040427581921272gmail-pl-c1">Int</span><span class="m_1477040427581921272gmail-pl-k">></span> <span class="m_1477040427581921272gmail-pl-k">=</span> <span class="m_1477040427581921272gmail-pl-c1">Set</span>(<span class="m_1477040427581921272gmail-pl-c1">1</span><span class="m_1477040427581921272gmail-pl-k">...</span><span class="m_1477040427581921272gmail-pl-c1">5</span>)
<span class="m_1477040427581921272gmail-pl-k">var</span> set2<span class="m_1477040427581921272gmail-pl-k">:</span> <span class="m_1477040427581921272gmail-pl-c1">Set</span><span class="m_1477040427581921272gmail-pl-k"><</span><span class="m_1477040427581921272gmail-pl-c1">Int</span><span class="m_1477040427581921272gmail-pl-k">></span> <span class="m_1477040427581921272gmail-pl-k">=</span> <span class="m_1477040427581921272gmail-pl-c1">Set</span>((<span class="m_1477040427581921272gmail-pl-c1">1</span><span class="m_1477040427581921272gmail-pl-k">...</span><span class="m_1477040427581921272gmail-pl-c1">5</span>).<span class="m_1477040427581921272gmail-pl-c1">reversed</span>())
set1 <span class="m_1477040427581921272gmail-pl-k">==</span> set2 <span class="m_1477040427581921272gmail-pl-c"><span class="m_1477040427581921272gmail-pl-c">//</span> true</span>
<span class="m_1477040427581921272gmail-pl-c"></span>set1.<span class="m_1477040427581921272gmail-pl-c1">elementsEqual</span>(set2) <span class="m_1477040427581921272gmail-pl-c"><span class="m_1477040427581921272gmail-pl-c">//</span> false</span></pre></div><p>This result does reflect the <strong>intended and documented</strong> behavior of the <code>elementsEqual(_:)</code> method, which performs a <strong>lexicographical</strong> elementwise comparison. That is, the method first compares <code>set1.first</code> to <code>set2.first</code>, then (if the two elements compare equal) compares the next element stored internally in <code>set1</code> to the next element stored internally in <code>set2</code>, and so on.</p><p>In almost all circumstances where a set is compared to another set,
or a dictionary is compared to another dictionary, users should use <code>==</code> instead of <code>elementsEqual(_:)</code>.</p>
<h2><a href="https://gist.github.com/xwu/1f0ef4e18a7f321f22ca65a2f56772f6#proposed-solution" class="m_1477040427581921272gmail-anchor" id="m_1477040427581921272gmail-user-content-proposed-solution" target="_blank"></a>Proposed solution</h2><p>The proposed solution is the result of an iterative process of reasoning, presented here:</p><p>The first and most obvious solution is to remove the <code>elementsEqual(_:)</code> method altogether in favor of <code>==</code>. This prevents its misuse. However, because <code>elementsEqual(_:)</code> is a generic method on <code>Sequence</code>, we can use it to compare an instance of <code>UnsafeBufferPointer<Int></code> to an instance of <code>[Int]</code>. This is a useful and non-redundant feature which would be eliminated if the method is removed altogether.</p><p><a href="https://github.com/apple/swift/pull/12318" target="_blank">A second solution</a> is to create overloads that forbid the use of the <code>elementsEqual(_:)</code>
method specifically in non-generic code. This would prevent misuse in
non-generic code; however, it would also forbid legitimate mixed-type
comparisons in non-generic code while failing to prevent misuse in
generic code. The solution also creates a difference in the behavior of
generic and non-generic code calling the same method, which is
potentially confusing, without solving the problem completely.</p><p>A third solution is to dramatically overhaul the protocol hierarchy
for Swift sequences and collections so that unordered collections no
longer have members such as <code>first</code> and <code>elementsEqual(_:)</code>.
However, this would be a colossal and source-breaking undertaking, and
it is unlikely to be satisfactory in addressing all the axes of
differences among sequence and collection types:</p>
<ul><li>Finite versus infinite</li><li>Single-pass versus multi-pass</li><li>Ordered versus unordered</li><li>Lazy versus eager</li><li>Forward/bidirectional/random-<wbr>access</li></ul><p>A fourth solution is proposed here. It is predicated on the following observation:</p><p><em>Another method similar to <code>elementsEqual(_:)</code> already exists on <code>Sequence</code> named <code>lexicographicallyPrecedes(_:)</code>. Like <code>first</code>, <code>elementsEqual(_:)</code>, <code>drop(while:)</code>,
and others, it relies on the internal order of elements in a manner
that is not completely suitable for an unordered collection. However,
like <code>first</code> and unlike <code>elementsEqual(_:)</code>, this fact is called out in the name of the method; unsurprisingly, like <code>first</code> and unlike <code>elementsEqual(_:)</code>, there is no evidence that <code>lexicographicallyPrecedes(_:)</code> has been a pitfall for users.</em></p><p>This observation suggests that a major reason for confusion over <code>elementsEqual(_:)</code> stems from its name. So, <strong>it is proposed that <code>elementsEqual(_:)</code> should be renamed to <code>lexicographicallyEquals(_:)</code></strong>.
The function will remain somewhat of a poor fit for unordered
collections, but no more so than many other methods that cannot
trivially be removed from the API of unordered collections (as discussed
above). The key is that, with such a renaming, the behavior of this
method will no longer be confusing.</p>
<h2><a href="https://gist.github.com/xwu/1f0ef4e18a7f321f22ca65a2f56772f6#detailed-design" class="m_1477040427581921272gmail-anchor" id="m_1477040427581921272gmail-user-content-detailed-design" target="_blank"></a>Detailed design</h2>
<div class="m_1477040427581921272gmail-highlight m_1477040427581921272gmail-highlight-source-swift"><pre><span class="m_1477040427581921272gmail-pl-k">extension</span> <span class="m_1477040427581921272gmail-pl-en"><span class="m_1477040427581921272gmail-pl-c1">Sequence</span></span> <span class="m_1477040427581921272gmail-pl-k">where</span> <span class="m_1477040427581921272gmail-pl-c1">Element</span> <span class="m_1477040427581921272gmail-pl-k">:</span> <span class="m_1477040427581921272gmail-pl-e"><span class="m_1477040427581921272gmail-pl-c1">Equatable</span></span> {
<span class="m_1477040427581921272gmail-pl-k">@available</span>(<span class="m_1477040427581921272gmail-pl-k">*</span>, <span class="m_1477040427581921272gmail-pl-k">deprecated</span>, <span class="m_1477040427581921272gmail-pl-k">message</span>: <span class="m_1477040427581921272gmail-pl-s"><span class="m_1477040427581921272gmail-pl-pds">"</span>Use '==' if possible to compare two sequences of the same type, or use 'lexicographicallyEquals' to compare two ordered sequences.<span class="m_1477040427581921272gmail-pl-pds">"</span></span>)
<span class="m_1477040427581921272gmail-pl-k">public</span> <span class="m_1477040427581921272gmail-pl-k">func</span> <span class="m_1477040427581921272gmail-pl-en">elementsEqual</span><<span class="m_1477040427581921272gmail-pl-c1">Other</span> : <span class="m_1477040427581921272gmail-pl-e"><span class="m_1477040427581921272gmail-pl-c1">Sequence</span></span>>(
<span class="m_1477040427581921272gmail-pl-en">_</span> <span class="m_1477040427581921272gmail-pl-smi">other</span>: Other
) <span class="m_1477040427581921272gmail-pl-k">-></span> <span class="m_1477040427581921272gmail-pl-c1">Bool</span> <span class="m_1477040427581921272gmail-pl-k">where</span> Other.<span class="m_1477040427581921272gmail-pl-c1">Element</span> <span class="m_1477040427581921272gmail-pl-k">==</span> <span class="m_1477040427581921272gmail-pl-c1">Element</span> {
<span class="m_1477040427581921272gmail-pl-k">return</span> <span class="m_1477040427581921272gmail-pl-c1">lexicographicallyEquals</span>(other)
}
<span class="m_1477040427581921272gmail-pl-k">public</span> <span class="m_1477040427581921272gmail-pl-k">func</span> <span class="m_1477040427581921272gmail-pl-en">lexicographicallyEquals</span><<span class="m_1477040427581921272gmail-pl-c1">Other</span> : <span class="m_1477040427581921272gmail-pl-e"><span class="m_1477040427581921272gmail-pl-c1">Sequence</span></span>>(
<span class="m_1477040427581921272gmail-pl-en">_</span> <span class="m_1477040427581921272gmail-pl-smi">other</span>: Other
) <span class="m_1477040427581921272gmail-pl-k">-></span> <span class="m_1477040427581921272gmail-pl-c1">Bool</span> <span class="m_1477040427581921272gmail-pl-k">where</span> Other.<span class="m_1477040427581921272gmail-pl-c1">Element</span> <span class="m_1477040427581921272gmail-pl-k">==</span> <span class="m_1477040427581921272gmail-pl-c1">Element</span> {
<span class="m_1477040427581921272gmail-pl-c"><span class="m_1477040427581921272gmail-pl-c">//</span> The body of this method is unchanged.</span>
<span class="m_1477040427581921272gmail-pl-c"></span> <span class="m_1477040427581921272gmail-pl-k">var</span> iter1 <span class="m_1477040427581921272gmail-pl-k">=</span> <span class="m_1477040427581921272gmail-pl-c1">self</span>.<span class="m_1477040427581921272gmail-pl-c1">makeIterator</span>()
<span class="m_1477040427581921272gmail-pl-k">var</span> iter2 <span class="m_1477040427581921272gmail-pl-k">=</span> other.<span class="m_1477040427581921272gmail-pl-c1">makeIterator</span>()
<span class="m_1477040427581921272gmail-pl-k">while</span> <span class="m_1477040427581921272gmail-pl-c1">true</span> {
<span class="m_1477040427581921272gmail-pl-k">switch</span> (iter1.<span class="m_1477040427581921272gmail-pl-c1">next</span>(), iter2.<span class="m_1477040427581921272gmail-pl-c1">next</span>()) {
<span class="m_1477040427581921272gmail-pl-k">case</span> <span class="m_1477040427581921272gmail-pl-k">let</span> (e1<span class="m_1477040427581921272gmail-pl-k">?</span>, e2<span class="m_1477040427581921272gmail-pl-k">?</span>)<span class="m_1477040427581921272gmail-pl-k">:</span>
<span class="m_1477040427581921272gmail-pl-k">if</span> e1 <span class="m_1477040427581921272gmail-pl-k">!=</span> e2 { <span class="m_1477040427581921272gmail-pl-k">return</span> <span class="m_1477040427581921272gmail-pl-c1">false</span> }
<span class="m_1477040427581921272gmail-pl-k">case</span> (<span class="m_1477040427581921272gmail-pl-c1">_</span><span class="m_1477040427581921272gmail-pl-k">?</span>, <span class="m_1477040427581921272gmail-pl-c1">nil</span>), (<span class="m_1477040427581921272gmail-pl-c1">nil</span>, <span class="m_1477040427581921272gmail-pl-c1">_</span><span class="m_1477040427581921272gmail-pl-k">?</span>)<span class="m_1477040427581921272gmail-pl-k">:</span>
<span class="m_1477040427581921272gmail-pl-k">return</span> <span class="m_1477040427581921272gmail-pl-c1">false</span>
<span class="m_1477040427581921272gmail-pl-k">case</span> (<span class="m_1477040427581921272gmail-pl-c1">nil</span>, <span class="m_1477040427581921272gmail-pl-c1">nil</span>)<span class="m_1477040427581921272gmail-pl-k">:</span>
<span class="m_1477040427581921272gmail-pl-k">return</span> <span class="m_1477040427581921272gmail-pl-c1">true</span>
}
}
}
}</pre></div><p>A parallel change will be made with respect to <code>elementsEqual(_:by:)</code>; that is, it will be deprecated in favor of <code>lexicographicallyEquals(_:by:)</code><wbr>.</p>
<h2><a href="https://gist.github.com/xwu/1f0ef4e18a7f321f22ca65a2f56772f6#source-compatibility" class="m_1477040427581921272gmail-anchor" id="m_1477040427581921272gmail-user-content-source-compatibility" target="_blank"></a>Source compatibility</h2><p>Existing code that uses <code>elementsEqual</code> will gain a deprecation warning.</p>
<h2><a href="https://gist.github.com/xwu/1f0ef4e18a7f321f22ca65a2f56772f6#effect-on-abi-stability" class="m_1477040427581921272gmail-anchor" id="m_1477040427581921272gmail-user-content-effect-on-abi-stability" target="_blank"></a>Effect on ABI stability</h2><p>None.</p>
<h2><a href="https://gist.github.com/xwu/1f0ef4e18a7f321f22ca65a2f56772f6#effect-on-api-resilience" class="m_1477040427581921272gmail-anchor" id="m_1477040427581921272gmail-user-content-effect-on-api-resilience" target="_blank"></a>Effect on API resilience</h2><p>This proposal adds new methods to the public API of <code>Sequence</code> and conforming types.</p>
<h2><a href="https://gist.github.com/xwu/1f0ef4e18a7f321f22ca65a2f56772f6#alternatives-considered" class="m_1477040427581921272gmail-anchor" id="m_1477040427581921272gmail-user-content-alternatives-considered" target="_blank"></a>Alternatives considered</h2><p>It is to be noted that <code>lexicographicallyPrecedes(_:<wbr>by:)</code> and <code>elementsEqual(_:by:)</code>
are essentially the same method, since both perform a lexicographical
comparison using a custom predicate. However, there is not a good
unifying name. (<code>lexicographicallyCompares(to:<wbr>by:)</code> reads
poorly.) Moreover, the predicate supplied is intended to have very
different semantics, and maintaining two distinct methods may be a
superior fit with the typical user's mental model of the intended
behavior and may also be clearer to readers of the code. Therefore, this
proposal does not seek to unify the two methods; instead, <code>elementsEqual(_:by:)</code> will be renamed <code>lexicographicallyEquals(_:by:)</code> as detailed above.</p></div></div></div>
______________________________<wbr>_________________<span class=""><br>swift-evolution mailing list<br><a href="mailto:swift-evolution@swift.org" target="_blank">swift-evolution@swift.org</a><br><a href="https://lists.swift.org/mailman/listinfo/swift-evolution" target="_blank">https://lists.swift.org/<wbr>mailman/listinfo/swift-<wbr>evolution</a><br></span></div></blockquote></div><br></div></blockquote></div><br></div></div>