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@swift.org>: > > >> On Oct 13, 2017, at 8:28 PM, Xiaodi Wu <xiaodi...@gmail.com >> <mailto:xiaodi...@gmail.com>> wrote: >> >> >> >> On Fri, Oct 13, 2017 at 12:03 PM, Kevin Nattinger <sw...@nattinger.net >> <mailto:sw...@nattinger.net>> wrote: >>> On Oct 13, 2017, at 6:52 AM, Xiaodi Wu <xiaodi...@gmail.com >>> <mailto:xiaodi...@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@swift.org > https://lists.swift.org/mailman/listinfo/swift-evolution
_______________________________________________ swift-evolution mailing list swift-evolution@swift.org https://lists.swift.org/mailman/listinfo/swift-evolution
