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

Xiaodi Wu xiaodi.wu at gmail.com
Fri Oct 13 22:09:28 CDT 2017

On Fri, Oct 13, 2017 at 10:28 AM, Adam Kemp <adam.kemp at apple.com> wrote:

> --
> Adam Kemp
> On Oct 13, 2017, at 7:59 AM, Xiaodi Wu <xiaodi.wu at gmail.com> wrote:
> On Fri, Oct 13, 2017 at 09:02 Adam Kemp <adam.kemp at apple.com> wrote:
>> Right, but if you do look it up you get a bunch of things talking about
>> sorting words.
> And that’s a perfect description of the behavior. It’s a lexicographical
> comparison operation!
> Is it? Are we always comparing words?

Let me clarify what I meant: the way in which a dictionary orders words is
an excellent and widely understood analog simulacrum of lexicographical
comparison. As others have already said, lexicographical comparison is an
established term for comparing sequences. Not only has such usage been long
established in Swift itself (`lexicographicallyPrecedes`), it is also
shared with other languages (C++ has `std::lexicographical_compare`), and
it originates in mathematical terminology that looked to dictionaries as
inspiration for the term.

How about pairwiseEqual?
> A lexicographical comparison compares not merely pairwise, but in order
> from the first item onwards, and stops at the first unequal pair.
> Proceeding in order is key information, while stopping early on false is a
> nice-to-have. There’s already a word for this, and it’s “lexicographical.”
> And the analogy is universally understood: everyone has used a dictionary
> or index.
> Clearly it’s not. You have several people telling you they don’t think
> it’s clear. You can argue that it’s technically correct if you want, but
> don’t try to tell us everyone understands it when it’s obvious that’s not
> true.

I'm saying that essentially everyone here understands the process by which
a dictionary arranges words; I hope we can accept this to be true without a
detailed inquiry. It is not strictly the aim of this proposal to make the
actual behavior of this function "clear" to any person who sees it, though
it would be nice as a bonus; the primary aim is to alleviate the situation
as it stands now where people see this function and _clearly believe it to
be what it is not_. That the proposed name is obtuse is intentional--as
Nate has surmised--as a way to prompt the unfamiliar user to look up the
documentation. The secondary aim is to have the name be unimpeachably
technically correct, and to avoid inventing new names for it; that way,
once the user has looked up this term, it will be knowledge transferrable
to other settings (e.g., C++), and if a user has learned about this
terminology elsewhere, they will be rewarded with having that knowledge
applicable to Swift.

>> On Oct 13, 2017, at 5:17 AM, Xiaodi Wu <xiaodi.wu at gmail.com> wrote:
>> “Lexicographical comparison” is a pretty standard term, and easy to
>> Google. We didn’t make it up for Swift :)
>> Since Swift names this protocol Sequence, something named
>> “Sequence.sequenceEqual” cannot distinguish this method from ==.
>> On Fri, Oct 13, 2017 at 01:28 Adam Kemp <adam.kemp at apple.com> wrote:
>>> I agree that the proposed name is a poor choice. If we just focus on
>>> the naming part, there is precedent in other languages for the name
>>> “sequenceEqual”. I think that name makes it a bit clearer that the result
>>> is whether the sequences match pair wise rather than whether they have the
>>> same elements irrespective of order. I don’t think it entirely solves the
>>> problem, but I like it a lot better than the proposed name.
>>> --
>>> Adam Kemp
>>> On Oct 12, 2017, at 9:57 PM, Kevin Nattinger via swift-evolution <
>>> swift-evolution at swift.org> wrote:
>>> –∞
>>> 1. I strongly object to the proposed name. It doesn't make it more clear
>>> to me what the method does, and is misleading at best. Among other issues,
>>> "lexicographical" is defined as alphabet order, and (1) this method applies
>>> to objects that are not Strings, and (2) this method's behavior isn't any
>>> more well-defined for Strings, so that name is even more of a lie than the
>>> original.
>>> 2. This is really just a symptom of a bigger problem. The fact that two
>>> Sets can compare equal and yet return different results for that method
>>> (among too many others) is logically inconsistent and points to a much
>>> deeper issue with Set and Sequence. It is probably about 3 releases too
>>> late to get this straightened out properly, but I'll outline the real issue
>>> in case someone has an idea for fixing it.
>>> *The root of the problem is that Set conforms to Sequence, but Sequence
>>> doesn't require a well-defined order.* Since Set doesn't have a
>>> well-defined order, a significant portion of its interface is unspecified.
>>> The methods are implemented because they have to be, but they doesn't have
>>> well-defined or necessarily consistent results.
>>> A sequence is, by definition, ordered. That is reflected in the fact
>>> that over half the methods in the main Sequence definition* make no sense
>>> and are not well-defined unless there is a well-defined order to the
>>> sequence itself. What does it even mean to `dropFirst()` in a Set? The fact
>>> that two objects that compare equal can give different results for a 100% deterministic
>>> function is illogical, nonsensical, and dangerous.
>>> * 7/12 by my count, ignoring `_*` funcs but including the `var`
>>> The current contents of Sequence can be cleanly divided into two groups;
>>> those that return SubSequence imply a specific ordering, and the
>>> rest do not.
>>>  I think those should be/should have been two separate protocols:
>>> public protocol Iterable {
>>>   associatedtype Iterator: IteratorProtocol
>>>   func map<T>(...) -> [T] // Iterable where .Iterator.Element == T
>>>   func filter(...) -> [Iterator.Element] // Iterable where
>>> .Iterator.Element == Self.Iterator.Element
>>>   func forEach(...)
>>>   func makeIterator() -> Iterator
>>>   var underestimatedCount: Int { get }
>>> }
>>> public protocol Sequence: Iterable { // Maybe OrderedSequence just to
>>> make the well-defined-order requirement explicit
>>>   associatedtype SubSequence
>>>   func dropFirst(...)   -> SubSequence   // Sequence where
>>> .Iterator.Element == Self.Iterator.Element
>>>   func dropLast(...)    -> SubSequence   //    " "
>>>   func drop(while...)   -> SubSequence   //    " "
>>>   func prefix(...)      -> SubSequence   //    " "
>>>   func prefix(while...) -> SubSequence   //    " "
>>>   func suffix(...)      -> SubSequence   //    " "
>>>   func split(...where...)  -> [SubSequence] // Iterable where
>>> .Iterator.Element == (Sequence where .Iterator.Element ==
>>> Self.Iterator.Element)
>>> }
>>> (The comments, of course, would be more sensible types once the ideas
>>> can actually be expressed in Swift)
>>> Then unordered collections (Set and Dictionary) would just conform to
>>> Iterable and not Sequence, so ALL the methods on those classes would make
>>> logical sense and have well-defined behavior; no change would be
>>> needed for ordered collections.
>>> Now, the practical matter. If this were Swift 1->2 or 2->3, I doubt
>>> there would be a significant issue with actually making this change.
>>> Unfortunately, we're well beyond that and making a change this
>>> deep is an enormous deal. So I see two ways forward.
>>> 1. We could go ahead and make this separation. Although it's a
>>> potentially large breaking change, I would argue that because the methods
>>> are ill-defined anyway, the breakage is justified and a net benefit.
>>> 2. We could try and think of a way to make the distinction between
>>> ordered and unordered "sequences" in a less-breaking manner. Unfortunately,
>>> I don't have a good suggestion for this, but if anyone has ideas, I'm all
>>> ears. Or eyes, as the case may be.
>>> On Oct 12, 2017, at 4:24 PM, Xiaodi Wu via swift-evolution <
>>> swift-evolution at swift.org> wrote:
>>> Rename Sequence.elementsEqual
>>>    - Proposal: SE-NNNN
>>>    <https://gist.github.com/xwu/NNNN-rename-elements-equal.md>
>>>    - Authors: Xiaodi Wu <https://github.com/xwu>
>>>    - Review Manager: TBD
>>>    - Status: *Awaiting review*
>>> <https://gist.github.com/xwu/1f0ef4e18a7f321f22ca65a2f56772f6#introduction>
>>> Introduction
>>> The current behavior of Sequence.elementsEqual 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 Sequence.
>>> lexicographicallyEquals.
>>> [...]
>>> _______________________________________________
>>> swift-evolution mailing list
>>> swift-evolution at swift.org
>>> https://lists.swift.org/mailman/listinfo/swift-evolution
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-evolution/attachments/20171013/8e72bb5b/attachment.html>

More information about the swift-evolution mailing list