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

[Benjamin G]

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 at swift.org> wrote:

> On Sat, Oct 14, 2017 at 2:28 AM, Kevin Nattinger <swift at nattinger.net>
> wrote:
>
>>
>> On Oct 13, 2017, at 8:28 PM, Xiaodi Wu <xiaodi.wu at gmail.com> wrote:
>>
>>
>>
>> On Fri, Oct 13, 2017 at 12:03 PM, Kevin Nattinger <swift at nattinger.net>
>> wrote:
>>
>>> On Oct 13, 2017, at 6:52 AM, Xiaodi Wu <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.
>>
>
> 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 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/729c567d/attachment.html>