I think what you're saying and what Kevin is saying are in way not contradictory :
You're saying the "SpongeBob" protocol functions make sense and are coherent, Kevin is saying the consequence is that it creates weird functions for Sets, and i think you're both right. an "UnorderedSequence" may very well have a "first" element. The problem is that when you apply it to sets, you're not calling: mySet.generatedRandomOrderSequence().first() but mySet.first() That's where the issue stands, and that's IMHO, a symptom that the protocol hierarchy is a bit misleading. What you would like for sets isn't "first()", but "any()". On Sat, Oct 14, 2017 at 10:26 AM, Xiaodi Wu via swift-evolution < swift-evolution@swift.org> wrote: > On Sat, Oct 14, 2017 at 2:28 AM, Kevin Nattinger <sw...@nattinger.net> > wrote: > >> >> On Oct 13, 2017, at 8:28 PM, Xiaodi Wu <xiaodi...@gmail.com> wrote: >> >> >> >> On Fri, Oct 13, 2017 at 12:03 PM, Kevin Nattinger <sw...@nattinger.net> >> wrote: >> >>> On Oct 13, 2017, at 6:52 AM, Xiaodi Wu <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. >> > > I'm not trying to bikeshed the name of `Sequence`. I'm picking an > intentionally unwieldy name for the purposes of discussing the semantics of > this particular protocol. The point is that the underlying issue has > nothing to do with the name; it can be `Iterable` or it can be `SpongeBob` > for all I care. > > >> >> >> * `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. >> > > What's your basis for saying that such behavior is absurd? It is > explicitly permitted for instances of types conforming to `SpongeBob` to be > single-pass and/or infinite. For a single-pass `SpongeBob`, `first` will > certainly return a different value every time it is invoked. > > A random number generator fulfills all the semantic requirements of > conforming to `SpongeBob`, and in fact I do just that in NumericAnnex > <https://github.com/xwu/NumericAnnex/blob/master/Sources/PRNG.swift#L53>. > `first` gives a different value every time, and a randomly generated > `SpongeBob` would unsurprisingly compare lexicographically not equal to > itself. > > 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. >> > > What you call a "Sequence" here would have to be multi-pass, finite, and > ordered. That's actually more semantically constrained than what Swift > calls a `Collection` (which requires conforming types to be multi-pass > and(?) finite). By contrast, Swift's `SpongeBob` protocol explicitly > permits conforming single-pass, infinite, and/or unordered types. As long > as it is possible to iterate over a `SpongeBob`, it is meaningful to ask > what element is first obtained upon iteration or to drop the first element > obtained upon iteration. And as long as iteration is not required to be > repeatable (and it isn't), it is perfectly acceptable for these algorithms > to return a different result every time. > > `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. >> > > What you want to call a "Sequence" is what Swift calls a `Collection`, > with additional restrictions. What you want to be called "Iterable" is what > Swift calls `Sequence` (or now, `SpongeBob`). Clearly, shuffling names will > not make these protocols support any more functionality, so that can be put > aside. > > Now, with that out of the way, why do you think that only `Collection` > types should have `first` and `last`? These helper properties and methods > are simply convenient ways to spell things that can be done with > `for...in`--the whole point of supplying them is to allow people to work > with these types in a more functional style. > > 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