[swift-evolution] [Draft] Rename Sequence.elementsEqual

[Martin R]

> On 18. Oct 2017, at 13:55, Xiaodi Wu <xiaodi.wu at gmail.com> wrote:
> 
> On Wed, Oct 18, 2017 at 03:05 Martin R <martinr448 at gmail.com> wrote:
> 
> 
> > On 17. Oct 2017, at 23:22, Michael Ilseman via swift-evolution <swift-evolution at swift.org> wrote:
> >
> >
> >
> >> On Oct 17, 2017, at 1:36 PM, Benjamin G <benjamin.garrigues at gmail.com> wrote:
> >>
> >>
> >>
> >> On Tue, Oct 17, 2017 at 10:25 PM, Michael Ilseman <milseman at apple.com> wrote:
> >>
> >>
> >>> On Oct 17, 2017, at 12:54 PM, Benjamin G <benjamin.garrigues at gmail.com> wrote:
> >>>
> >>> Thanks for the post, that's the first clear explanation i see on this thread for the concepts behind the design for Sequence.
> >>>
> >>> I am a bit afraid that understanding all that is a bit above what to expect the average swift developer will guess when he sees functions like "prefix / first / elementEqual (or whatever it's called)" on the Set type.
> >>> There is, IMHO, a much higher chance he'll either :
> >>> 1/ not understand anything, or
> >>> 2/ think Sets are in fact secretely ordered sets, or start writing generic extensions above Sequence or Collection thinking those protocols are synonymous for orderer collections.
> >>>
> >>> 1/ is pretty harmless, but 2/ seems like a source of bug.
> >>>
> >>> My personal opinion after reading all this is that we should simply change the name
> >>
> >> Exactly, and that’s what Xiaodi’s proposal does. Confronted with these complexities, his proposal reasons that a name change is the lessor or evils, as in the “Proposed solution” section.
> >>
> >>> to sequentiallyEquals
> >>
> >> Xiaodi floated “lexicographicallyEqual” which is accurate and a big improvement, and I’m liking it more and more. I floated “sequentiallyEquals”, which I’m liking less and less now. My current preference is for “elementsOrderedEqual” which I think is more descriptive but unwieldy. On the other hand, this is a far less common facility, and order matters, so maybe more verbose names are fine.
> >>
> >> I'm sorry to bring more bikeshedding, but lexicographicallyEqual seems absolutely atrocious to me. Imagine all the steps required the user of a Set<Int> to understand why a lexicographicallyEqual function is suggested by the compiler ??
> >>
> >
> > My initial resistance is that lexicographical implies a comparability beyond equality. `lexicographicallyEquals`, then, had me (erroneously) wondering if the “lexicographically” part meant that the elements were presented in lexicographical order and then compared for equality. But, I was in error and this is a wrong interpretation of the term. “abc” is not lexicographically equal to “cba”, and it’s quite a mental leap to think that the order of elements would be presented differently. That’s not to say that others won't have the same misinterpretation and that’s why I’m hoping for a better name. But, if `lexicographicallyEquals` is what we settle on, that’s a huge improvement over `elementsEqual`.
> 
> 
> In the earlier post https://lists.swift.org/pipermail/swift-evolution/Week-of-Mon-20171009/040428.html, Xiaodi Wu quoted from http://en.cppreference.com/w/cpp/algorithm/lexicographical_compare because that "defines lexicographical comparison unambiguously for C++".
> 
> But that definition corresponds to what `lexicographicallyPrecedes()` method does: two sequences are compared in iteration order using `<`, until one is exhausted or a difference is found. It requires that the sequence Element type is Comparable (but not that the sequences elements are ordered!) and allows to order all sets with the same element type.
> 
> In your example, "abc" is not lexicographically equal to "cba" because "a" < "c".
> 
> Not quite. It's because "a" != "c".
> 
> C++ `lexicographical_compare` does correspond to `lexicographicallyPrecedes` and evaluates for lexicographical less-than, but the documentation there also defines lexicographical equality, which is in terms of equivalence.

Almost the first thing a user reads on http://en.cppreference.com/w/cpp/algorithm/lexicographical_compare after the prototypes is

> Elements are compared using operator< (or given binary comparison function comp)

and later

> The first mismatching element defines which range is lexicographically less or greater than the other.
> If two ranges have equivalent elements and are of the same length, then the ranges are lexicographically equal.

My interpretation would be that two ranges (or in our case, sequences) are "lexicographically equal" if the comparison of the elements in iteration order does not find a mismatching element, i.e. for all elements (a, b) at the corresponding position, neither a < b nor b < a holds.

> In Swift, a type can define a notion of equivalence without defining a notion of precedence, so lexicographical equality can be evaluated even if lexicographical less-than cannot in that case.

Yes, and the same can be done in C++ with http://en.cppreference.com/w/cpp/algorithm/equal. It compares elements in iteration order with operator== (or a given binary predicate). That is exactly what elementsEqual() does. 

However, std::equal has no "lexicographic" in its name.

So I would understand "lexicographicallyEquals" as: Comparing the elements in iteration order with `<` does not find a difference. 

I am aware that this is just my interpretation/opinion, and may be different from yours or other's.

Martin


> 
> The equivalent of `elementsEqual()` in C++ would be http://en.cppreference.com/w/cpp/algorithm/equal, which has the Note
> 
>    std::equal should not be used to compare the ranges formed by the iterators from
>    std::unordered_set, ... because the order in which the elements are stored in
>    those containers may be different even if the two containers store the same elements.
> 
> which is the same issue that we are talking about here.
> 
> My argument against the name "lexicographicallyEquals" would be
> 
> - It suggests that the elements from both sequences are compared (in iteration order) using `<` (and thus required to be Comparable).
> - Googling for "lexicographical comparison" leads to the above C++ reference, or to https://en.wikipedia.org/wiki/Lexicographical_order. Both are about ordering sequences (words) based on the order of the underlying element type (alphabet). This does not describe what `elementsEqual()` does.
> 
> Both arguments are unrelated to whether the sequences are generated from ordered or unordered collections (like sets), or whether the elements in each sequence are ordered or not.
> 
> Just my 2ct. Probably this has been said before, it is difficult to keep track of the various threads in this discussion.
> 
> Regards, Martin