On Sat, Oct 14, 2017 at 14:36 Benjamin G <benjamin.garrig...@gmail.com> wrote:
> 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()". > 'first' is just a shorthand for 'let first; for element in sequence { first = element; break }'. Any type that offers iterated access in a for...in loop must, by construction, have a definable 'first'. Swift Sequences are deliberately allowed to be single-pass, infinite, or unordered. A multi-pass, finite Sequence is a Collection. It's not an oversight that 'first' is defined on Sequence and not Collection. It's not 'weird' to ask what the first element you get on iteration must be; by definition, iteration gives you elements sequentially and something must be first. > 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