On Wed, Oct 18, 2017 at 08:11 Martin R <martinr...@gmail.com> wrote: > > > > On 18. Oct 2017, at 13:55, Xiaodi Wu <xiaodi...@gmail.com> wrote: > > > > On Wed, Oct 18, 2017 at 03:05 Martin R <martinr...@gmail.com> wrote: > > > > > > > On 17. Oct 2017, at 23:22, Michael Ilseman via swift-evolution < > swift-evolution@swift.org> wrote: > > > > > > > > > > > >> On Oct 17, 2017, at 1:36 PM, Benjamin G <benjamin.garrig...@gmail.com> > wrote: > > >> > > >> > > >> > > >> On Tue, Oct 17, 2017 at 10:25 PM, Michael Ilseman <milse...@apple.com> > wrote: > > >> > > >> > > >>> On Oct 17, 2017, at 12:54 PM, Benjamin G < > benjamin.garrig...@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 > >
_______________________________________________ swift-evolution mailing list swift-evolution@swift.org https://lists.swift.org/mailman/listinfo/swift-evolution