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

Sat Oct 14 08:52:02 CDT 2017

Well said, Kevin! I agree to all points you made. Yes, a Set has no intrinsic order, just an iteration over a set has. And the latter does not even have to be stable.

Let’s split Iterable off Sequence.

-Thorsten

> Am 14.10.2017 um 09:28 schrieb Kevin Nattinger via swift-evolution <swift-evolution at swift.org>:
> 
> 
>> On Oct 13, 2017, at 8:28 PM, Xiaodi Wu <xiaodi.wu at gmail.com <mailto:xiaodi.wu at gmail.com>> wrote:
>> 
>> 
>> 
>> On Fri, Oct 13, 2017 at 12:03 PM, Kevin Nattinger <swift at nattinger.net <mailto:swift at nattinger.net>> wrote:
>>> On Oct 13, 2017, at 6:52 AM, Xiaodi Wu <xiaodi.wu at gmail.com <mailto:xiaodi.wu at gmail.com>> wrote:
>>> 
>>> You’re welcome to bikeshed the entire API surface area of sequences and collections, but you won’t be the first to explore this area. A number of us looked into this area in the past few years and did not reach a measurable improved result.
>> 
>> I don’t need or want to bikeshed the entire sequence and collection surface area, I just want to fix one clear and GLARING issue:
>> 
>> A Set is NOT a sequence.
>> 
>> Note that this goes for dictionaries and any other unordered “sequences" as well.
>> 
>> That was in an early draft of my original email, but I dropped it because I was afraid people would just stop reading and dismiss the idea out-of-hand without considering the problem or arguments. Apparently I should have at least put it at the bottom, so sorry if the root issue was unclear.
>> 
>>> Sequences can be ordered or unordered,
>> 
>> You seem to be confusing the English word “sequence” with the (current) Swift protocol “Sequence." A sequence is, by definition, ordered. Not enforcing that in a protocol does not override the English language, and as this entire thread demonstrates, causes issues further on down the line.
>> 
>> We are discussing the Swift protocol `Sequence`. It really doesn't matter at all what the English word "sequence" means, and any difference between the English word and the Swift term is emphatically *not* the root cause of the issue. Here's why:
>> 
>> * A Swift `Sequence` is, to put it simplistically, a thing that can be iterated over in a `for...in` loop. If it would make you happy, for the rest of the discussion, let's suppose we called the protocol `ForLoopable` instead of `Sequence`.
> 
> ForLoopable is so ugly. Since we’re just iterating over the elements, how about, oh, say, `Iterable`? Hey, that looks familiar.
> 
>> 
>> * `Set` should conform to `ForLoopable`. (This I state as a premise; if you disagree with the notion that we should be able to iterate over the elements of an instance of `Set` with a `for...in loop`, then it's clearly a whole other discussion and not a question of what the English word "sequence" means.)
> 
> Obviously, `Set: Iterable`. I don’t think I’ve said anything to suggest you shouldn’t be able to iterate over unordered collections.
> 
>> 
>> * If a type `T` conforms to `ForLoopable` and an instance `t` of that type has at least one element, then *something* has to be the first element in a `for element in t { ... }` loop. Put another way, every instance of a type that conforms to `ForLoopable` must have at least one publicly observable order (although, intriguingly, I'm not sure it has to be a repeatable one). It is possible, therefore, to have a semantic answer to the question of which element is `first` or (if finite) `last`; one can also `drop(while:)`, etc., and perform lexicographical comparisons.
> 
> As a side effect of Swift being a procedural language each iteration happens to occur in some order, yes, but that order is meaningless and reflects nothing about the Set itself.  In fact, I’d say that `first`, `last`, etc. are not even defined on the original Set per se, only on the specific order that a particular iteration resulted in. And that order is not necessarily predictable, nor necessarily stable, as you yourself said.
> 
> Consider an Iterable that gives a different order every time it’s iterated. 
> Should calling `.first` or `last` give a different object every time?  That’s absurd.
> Should an object lexicographically compare not equal to itself? Even more absurd. 
> 
> On the other hand, if I have a collection of objects that I want iterated in a particular order, I can use a container that iterates in a specific, known, well-defined way, and use that to construct the sequence of objects.  That’s clearly an Iterable collection, but the guarantee is stronger than that. Since it iterates objects in a specific sequence, the logical way to express that would be `Sequence: Iterable`. Again, we’ve seen that before.  
> 
> Now, since a Sequence is guaranteed to iterate the same every time, suddenly our `first`, `last`, `drop*`, etc. methods have a meaning inherent to the collection itself, rather than a specific iteration. 
> `first` is the first object in the Sequence. It doesn’t matter how the sequence came to be in that order; it doesn’t matter whether or not the sequence has already been iterated or how many times. `first` is the first object that is, was, and always will be presented by the Sequence’s Iterator. (Until the collection is mutated, obviously).
> 
> To summarize,
> A Set has no intrinsic order. You can iterate over it, and a specific iteration of a set has an order, but that order is not tied to the Set itself beyond including all and only the items therein. Therefore, the Set itself has no intrinsic `first`, `last`, lexicographical comparison, etc.; only its iterations do, and they are not themselves Sets.
> A Sequence does have an intrinsic order. The order of iteration reflects the order inherent to the Sequence. Therefore, a Sequence has a `first`, `last`, lexicographical comparison, etc.
> 
> Just in case it’s not obvious, `Set` here is pretty much interchangeable with any other unordered iterable.
> 
>>> 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)
>>> }
> 
> 
> And just to be explicit, 
> struct Set: Iterable {…}
> struct Dictionary: Iterable {…}
> struct Array: Sequence {…}
> etc.
> 
> Hopefully at some point:
> struct OrderedSet: Sequence {…}
> 
> _______________________________________________
> 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/20171014/99cd81a2/attachment.html>