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

[Xiaodi Wu]

On Sat, Oct 14, 2017 at 14:36 Benjamin G <benjamin.garrigues at 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 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/f4faf36a/attachment.html>