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

Wed Oct 18 08:19:01 CDT 2017

On Wed, Oct 18, 2017 at 08:11 Martin R <martinr448 at gmail.com> wrote:

>
>
> > 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.

Yes, this is a description of C++ lexicographical_compare, which tells you
if range is lexicographically less than another.

> If two ranges have equivalent elements and are of the same length, then
> the ranges are lexicographically equal.

This is the definition of lexicographical equality. It is a named
std::equal in C++.

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.

No, it doesn’t have that word in the name, but it would be correct if it
did.

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

That is not the definition of lexicographical equality. The reference you
cite gives you the correct definition.

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
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-evolution/attachments/20171018/628e1689/attachment.html>