<div dir="ltr">On Fri, Oct 13, 2017 at 3:06 PM, Jonathan Hull <span dir="ltr">&lt;<a href="mailto:jhull@gbis.com" target="_blank">jhull@gbis.com</a>&gt;</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">It has been a while, but I believe a lexicographical ordering is basically a mapping from a set to the natural numbers (which should, in effect, provide a total ordering).  The mapping itself can be arbitrary, but the same set of things should never map to two different sequences (which just happens to be the example given).<div><br><div>This tells me that “lexicographicallyPrecedes” is actually misnamed unless it refers to something which has a defined totally ordering.</div></div></div></blockquote><div><br></div><div>By defining lexicographical equivalence and precedence, a total order is defined for the set of all sequences that have the same element type. That is, defining lexicographical equivalence and precedence for sequences of Foos imposes a total ordering over the set of all sequences of Foos. Notice that `lexicographicallyPrecedes` refers to the singular sequence being ordered with respect to other sequences, not to the elements of the sequence.</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"><div><div><div></div><div>If we are looking to rename elementsEqual (which I would expect to check if the same elements are present regardless of ordering), I would recommend <b>elementOrderingEqual</b> or something like that that references that the answer will be affected by the internal representation/ordering of the sequence.</div><div><br></div><div>Thanks,</div><div>Jon</div><div><div class="h5"><div><br><div><blockquote type="cite"><div>On Oct 13, 2017, at 11:10 AM, Jarod Long via swift-evolution &lt;<a href="mailto:swift-evolution@swift.org" target="_blank">swift-evolution@swift.org</a>&gt; wrote:</div><br class="m_2510687898609815584Apple-interchange-newline"><div>



<div>
<div name="messageBodySection" style="font-size:14px;font-family:-apple-system,BlinkMacSystemFont,sans-serif">The name that feels natural to me would be `sequentiallyEquals`. I don&#39;t dispute that the term &quot;lexicographical&quot; is used correctly here, although at least for me personally, it&#39;s not a word that I encounter frequently enough to understand what this method would do without reading the documentation. Like Kevin, if I were to guess what the method did without checking, I would probably think that it compared lexicographically-sorted versions of the collections.
<div><br></div>
<div>But the consistency with `lexicographicallyPrecedes` is a pretty strong argument, although `sequentiallyPrecedes` would also feel more natural to me there, and my suspicion about the mentioned lack of evidence that the method has been a pitfall for users is that it&#39;s not actually used often enough out in the wild to have heard much about it. That&#39;s just a guess though. This proposal is the first time I&#39;ve learned of its existence.</div>
<div><br></div>
<div>In any case, my ideal version of this proposal would use `sequentiallyEquals` and also rename `lexicographicallyPrecedes` to `sequentiallyPrecedes`, but I still like the proposal overall as-is. Thanks for bringing it forward!</div>
</div>
<div name="messageSignatureSection" style="font-size:14px;font-family:-apple-system,BlinkMacSystemFont,sans-serif"><br>
Jarod</div>
<div name="messageReplySection" style="font-size:14px;font-family:-apple-system,BlinkMacSystemFont,sans-serif"><br>
On Oct 12, 2017, 16:24 -0700, Xiaodi Wu via swift-evolution &lt;<a href="mailto:swift-evolution@swift.org" target="_blank">swift-evolution@swift.org</a>&gt;, wrote:<br>
<blockquote type="cite" style="margin:5px 5px;padding-left:10px;border-left:thin solid #1abc9c">
<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_2510687898609815584gmail-anchor" id="m_2510687898609815584gmail-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_2510687898609815584gmail-anchor" id="m_2510687898609815584gmail-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_2510687898609815584gmail-highlight m_2510687898609815584gmail-highlight-source-swift">
<pre><span class="m_2510687898609815584gmail-pl-k">var</span> set1<span class="m_2510687898609815584gmail-pl-k">:</span> <span class="m_2510687898609815584gmail-pl-c1">Set</span><span class="m_2510687898609815584gmail-pl-k">&lt;</span><span class="m_2510687898609815584gmail-pl-c1">Int</span><span class="m_2510687898609815584gmail-pl-k">&gt;</span> <span class="m_2510687898609815584gmail-pl-k">=</span> <span class="m_2510687898609815584gmail-pl-c1">Set</span>(<span class="m_2510687898609815584gmail-pl-c1">1</span><span class="m_2510687898609815584gmail-pl-k">...</span><span class="m_2510687898609815584gmail-pl-c1">5</span>)
<span class="m_2510687898609815584gmail-pl-k">var</span> set2<span class="m_2510687898609815584gmail-pl-k">:</span> <span class="m_2510687898609815584gmail-pl-c1">Set</span><span class="m_2510687898609815584gmail-pl-k">&lt;</span><span class="m_2510687898609815584gmail-pl-c1">Int</span><span class="m_2510687898609815584gmail-pl-k">&gt;</span> <span class="m_2510687898609815584gmail-pl-k">=</span> <span class="m_2510687898609815584gmail-pl-c1">Set</span>((<span class="m_2510687898609815584gmail-pl-c1">1</span><span class="m_2510687898609815584gmail-pl-k">...</span><span class="m_2510687898609815584gmail-pl-c1">5</span>).<span class="m_2510687898609815584gmail-pl-c1">reversed</span>())

set1 <span class="m_2510687898609815584gmail-pl-k">==</span> set2 <span class="m_2510687898609815584gmail-pl-c"><span class="m_2510687898609815584gmail-pl-c">//</span> true</span>
<span class="m_2510687898609815584gmail-pl-c"></span>set1.<span class="m_2510687898609815584gmail-pl-c1">elementsEqual</span>(set2) <span class="m_2510687898609815584gmail-pl-c"><span class="m_2510687898609815584gmail-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_2510687898609815584gmail-anchor" id="m_2510687898609815584gmail-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&lt;Int&gt;</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_2510687898609815584gmail-anchor" id="m_2510687898609815584gmail-user-content-detailed-design" target="_blank"></a>Detailed design</h2>
<div class="m_2510687898609815584gmail-highlight m_2510687898609815584gmail-highlight-source-swift">
<pre><span class="m_2510687898609815584gmail-pl-k">extension</span> <span class="m_2510687898609815584gmail-pl-en"><span class="m_2510687898609815584gmail-pl-c1">Sequence</span></span> <span class="m_2510687898609815584gmail-pl-k">where</span> <span class="m_2510687898609815584gmail-pl-c1">Element</span> <span class="m_2510687898609815584gmail-pl-k">:</span> <span class="m_2510687898609815584gmail-pl-e"><span class="m_2510687898609815584gmail-pl-c1">Equatable</span></span> {
  <span class="m_2510687898609815584gmail-pl-k">@available</span>(<span class="m_2510687898609815584gmail-pl-k">*</span>, <span class="m_2510687898609815584gmail-pl-k">deprecated</span>, <span class="m_2510687898609815584gmail-pl-k">message</span>: <span class="m_2510687898609815584gmail-pl-s"><span class="m_2510687898609815584gmail-pl-pds">&quot;</span>Use &#39;==&#39; if possible to compare two sequences of the same type, or use &#39;lexicographicallyEquals&#39; to compare two ordered sequences.<span class="m_2510687898609815584gmail-pl-pds">&quot;</span></span>)
  <span class="m_2510687898609815584gmail-pl-k">public</span> <span class="m_2510687898609815584gmail-pl-k">func</span> <span class="m_2510687898609815584gmail-pl-en">elementsEqual</span>&lt;<span class="m_2510687898609815584gmail-pl-c1">Other</span> : <span class="m_2510687898609815584gmail-pl-e"><span class="m_2510687898609815584gmail-pl-c1">Sequence</span></span>&gt;(
    <span class="m_2510687898609815584gmail-pl-en">_</span> <span class="m_2510687898609815584gmail-pl-smi">other</span>: Other
  ) <span class="m_2510687898609815584gmail-pl-k">-&gt;</span> <span class="m_2510687898609815584gmail-pl-c1">Bool</span> <span class="m_2510687898609815584gmail-pl-k">where</span> Other.<span class="m_2510687898609815584gmail-pl-c1">Element</span> <span class="m_2510687898609815584gmail-pl-k">==</span> <span class="m_2510687898609815584gmail-pl-c1">Element</span> {
    <span class="m_2510687898609815584gmail-pl-k">return</span> <span class="m_2510687898609815584gmail-pl-c1">lexicographicallyEquals</span>(other)
  }
   
  <span class="m_2510687898609815584gmail-pl-k">public</span> <span class="m_2510687898609815584gmail-pl-k">func</span> <span class="m_2510687898609815584gmail-pl-en">lexicographicallyEquals</span>&lt;<span class="m_2510687898609815584gmail-pl-c1">Other</span> : <span class="m_2510687898609815584gmail-pl-e"><span class="m_2510687898609815584gmail-pl-c1">Sequence</span></span>&gt;(
    <span class="m_2510687898609815584gmail-pl-en">_</span> <span class="m_2510687898609815584gmail-pl-smi">other</span>: Other
  ) <span class="m_2510687898609815584gmail-pl-k">-&gt;</span> <span class="m_2510687898609815584gmail-pl-c1">Bool</span> <span class="m_2510687898609815584gmail-pl-k">where</span> Other.<span class="m_2510687898609815584gmail-pl-c1">Element</span> <span class="m_2510687898609815584gmail-pl-k">==</span> <span class="m_2510687898609815584gmail-pl-c1">Element</span> {
    <span class="m_2510687898609815584gmail-pl-c"><span class="m_2510687898609815584gmail-pl-c">//</span> The body of this method is unchanged.</span>
<span class="m_2510687898609815584gmail-pl-c"></span>    <span class="m_2510687898609815584gmail-pl-k">var</span> iter1 <span class="m_2510687898609815584gmail-pl-k">=</span> <span class="m_2510687898609815584gmail-pl-c1">self</span>.<span class="m_2510687898609815584gmail-pl-c1">makeIterator</span>()
    <span class="m_2510687898609815584gmail-pl-k">var</span> iter2 <span class="m_2510687898609815584gmail-pl-k">=</span> other.<span class="m_2510687898609815584gmail-pl-c1">makeIterator</span>()
    <span class="m_2510687898609815584gmail-pl-k">while</span> <span class="m_2510687898609815584gmail-pl-c1">true</span> {
      <span class="m_2510687898609815584gmail-pl-k">switch</span> (iter1.<span class="m_2510687898609815584gmail-pl-c1">next</span>(), iter2.<span class="m_2510687898609815584gmail-pl-c1">next</span>()) {
      <span class="m_2510687898609815584gmail-pl-k">case</span> <span class="m_2510687898609815584gmail-pl-k">let</span> (e1<span class="m_2510687898609815584gmail-pl-k">?</span>, e2<span class="m_2510687898609815584gmail-pl-k">?</span>)<span class="m_2510687898609815584gmail-pl-k">:</span>
        <span class="m_2510687898609815584gmail-pl-k">if</span> e1 <span class="m_2510687898609815584gmail-pl-k">!=</span> e2 { <span class="m_2510687898609815584gmail-pl-k">return</span> <span class="m_2510687898609815584gmail-pl-c1">false</span> }
      <span class="m_2510687898609815584gmail-pl-k">case</span> (<span class="m_2510687898609815584gmail-pl-c1">_</span><span class="m_2510687898609815584gmail-pl-k">?</span>, <span class="m_2510687898609815584gmail-pl-c1">nil</span>), (<span class="m_2510687898609815584gmail-pl-c1">nil</span>, <span class="m_2510687898609815584gmail-pl-c1">_</span><span class="m_2510687898609815584gmail-pl-k">?</span>)<span class="m_2510687898609815584gmail-pl-k">:</span>
        <span class="m_2510687898609815584gmail-pl-k">return</span> <span class="m_2510687898609815584gmail-pl-c1">false</span>
      <span class="m_2510687898609815584gmail-pl-k">case</span> (<span class="m_2510687898609815584gmail-pl-c1">nil</span>, <span class="m_2510687898609815584gmail-pl-c1">nil</span>)<span class="m_2510687898609815584gmail-pl-k">:</span>
        <span class="m_2510687898609815584gmail-pl-k">return</span> <span class="m_2510687898609815584gmail-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_2510687898609815584gmail-anchor" id="m_2510687898609815584gmail-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_2510687898609815584gmail-anchor" id="m_2510687898609815584gmail-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_2510687898609815584gmail-anchor" id="m_2510687898609815584gmail-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_2510687898609815584gmail-anchor" id="m_2510687898609815584gmail-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&#39;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>
______________________________<wbr>_________________<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></blockquote>
</div>
</div>

______________________________<wbr>_________________<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></div></blockquote></div><br></div></div></div></div></div></div></blockquote></div><br></div></div>