One rationale I heard (I think from Ben Cohen) for why 'first' is not defined on Collection is that Sequences can be single-pass, and it would feel weird for a seemingly innocuous property like 'first' to have side effects.
This should be "not defined on Sequence", of course. Apologies for making the same mistake I was pointing out.
Hmm, I do think I can squash some of these suggestions into an explicit and very clear option:
equalsInIterationOrder(_:)
I could live with that name.
We would then clarify the corresponding precedence function in the same way:
lexicographicallyPrecedesInIterationOrder(_:)
but that one seems a bit unwieldy...
On Oct 15, 2017, at 12:26 AM, Xiaodi Wu <xiaodi.wu@gmail.com> wrote:
But let it never be said to be anything but crystal clear :) We could just
leave it alone though.
On Sun, Oct 15, 2017 at 2:39 AM, Adam Kemp <adam.kemp@apple.com> wrote:
> On Oct 15, 2017, at 12:26 AM, Xiaodi Wu <xiaodi.wu@gmail.com> wrote:
>
> Hmm, I do think I can squash some of these suggestions into an explicit
and very clear option:
>
> equalsInIterationOrder(_:)I could live with that name.
>
> We would then clarify the corresponding precedence function in the same
way:
>
> lexicographicallyPrecedesInIterationOrder(_:)but that one seems a bit unwieldy...
> Ordered, yes, but it’s only admittedly poor wording that suggests multi-pass, and I don’t think anything there suggests finite.
If a Sequence is "guaranteed to iterate the same every time," then surely it must be multi-pass; what's the alternative?
Single-pass, but where two dictionaries/sets with the same elements would be guaranteed to output the same ordering.
I'm not sure I understand. A single-pass sequence is one where iteration can happen only once because it is destructive. By definition, then, it is not guaranteed to "iterate the same" a second time. Neither sets nor dictionaries are single-pass sequences. Kevin says that his definition of a "Sequence" is something "guaranteed to iterate the same every time," which requires them to be multi-pass, does it not?
But if I am comparing two single-pass things, the order can still be defined when they compare that one time. Single-pass doesn’t mean that the order is undefined. On the contrary, as you point out, it has a “first” thing, and then a thing after that, and so on.
Regardless, most of the objects we are talking about here are multi-pass collections (e.g. sets).
That ordering can be arbitrary, but it shouldn’t leak internal representation such that the method used to create identical things affects the outcome of generic methods because of differences in internal representation.
It would be better to say that the iteration order is well-defined. That will almost always mean documented, and usually predictable though obviously e.g. RNGs and iterating in random order will not be predictable by design.
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.
I think you’re talking about Sequence here, I’ve lost track of your nonsense by now. Yes, the current Swift protocol named Sequence allows unordered types. You seem to keep asserting that but not actually addressing my argument, which is that allowing Sequences to be unordered with the current API is undesired and actively harmful, and should therefore be changed.
What is harmful about it?
After thinking about it, I think the harmful bit is that unordered sequences are leaking internal representation (In your example, this is causing people to be surprised when two sets with identical elements are generating different sequences/orderings based on how they were created). You are correct when you say that this problem is even true for for-in.
I would not say it is a problem. Rather, by definition, iteration involves retrieving one element after another; if you're allowed to do that with Set, then the elements of a Set are observably ordered in some way. Since it's not an OrderedSet--i.e., order doesn't matter--then the only sensible conclusion is that the order of elements obtained in a for...in loop must be arbitrary. If you think this is harmful, then you must believe that one should be prohibited from iterating over an instance of Set. Otherwise, Set is inescapably a Sequence by the Swift definition of Sequence. All extension methods on Sequence like drop(while:) are really just conveniences for common things that you can do with iterated access; to my mind, they're essentially just alternative ways of spelling various for...in loops.
I think an argument could be made that you shouldn’t be able to iterate over a set without first defining an ordering on it (even if that ordering is somewhat arbitrary). Maybe we have something like a “Sequenc(e)able” protocol which defines things which can be turned into a sequence when combined with some sort of ordering. One possible ordering could be the internal representation (At least in that case we are calling it out specifically). If I had to say “setA.arbitraryOrder.elementsEqual(setB.arbitraryOrder)” I would definitely be less surprised when it returns false even though setA == setB.
If that is unergonomic, we could define an arbitrary but consistent ordering over all Swift types that can be used to create a predictable sequence order for unordered types. That is necessarily slower, but much safer… and people concerned with speed could use something like ‘arbitraryOrder’ above to regain full speed.
I am not arguing that that is necessarily the right approach, just that we need more thought/discussion around what is actually causing the confusion here: The fact that we are assuming an ordering on something where the ordering is undefined.
Thanks,
Jon
On Oct 14, 2017, at 9:21 PM, Xiaodi Wu <xiaodi.wu@gmail.com> wrote:
On Sat, Oct 14, 2017 at 10:55 PM, Jonathan Hull <jhull@gbis.com <mailto:jhull@gbis.com>> wrote:On Oct 14, 2017, at 7:55 PM, Xiaodi Wu via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:
> Ordered, yes, but it’s only admittedly poor wording that suggests
multi-pass, and I don’t think anything there suggests finite.If a Sequence is "guaranteed to iterate the same every time," then surely
it must be multi-pass; what's the alternative?Single-pass, but where two dictionaries/sets with the same elements would
be guaranteed to output the same ordering.I'm not sure I understand. A single-pass sequence is one where iteration
can happen only once because it is destructive. By definition, then, it is
not guaranteed to "iterate the same" a second time. Neither sets nor
dictionaries are single-pass sequences. Kevin says that his definition of a
"Sequence" is something "guaranteed to iterate the same every time," which
requires them to be multi-pass, does it not?But if I am comparing two single-pass things, the order can still be
defined when they compare that one time. Single-pass doesn’t mean that the
order is undefined. On the contrary, as you point out, it has a “first”
thing, and then a thing after that, and so on.Regardless, most of the objects we are talking about here are multi-pass
collections (e.g. sets).
Right, but I'm trying to figure out why Kevin wants a Sequence to "iterate
the same every time" and in what way that's not simply a Collection.
That ordering can be arbitrary, but it shouldn’t leak internal
representation such that the method used to create identical things affects
the outcome of generic methods because of differences in internal
representation.It would be better to say that the iteration order is well-defined. That
will almost always mean documented, and usually predictable though
obviously e.g. RNGs and iterating in random order will not be predictable
by design.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.I think you’re talking about Sequence here, I’ve lost track of your
nonsense by now. Yes, the current Swift protocol named Sequence allows
unordered types. You seem to keep asserting that but not actually
addressing my argument, which is *that allowing Sequences to be
unordered with the current API is undesired and actively harmful, and
should* *therefore** be changed*.What is harmful about it?
After thinking about it, I think the harmful bit is that unordered
sequences are leaking internal representation (In your example, this is
causing people to be surprised when two sets with identical elements are
generating different sequences/orderings based on how they were created).
You are correct when you say that this problem is even true for for-in.I would not say it is a problem. Rather, by definition, iteration involves
retrieving one element after another; if you're allowed to do that with
Set, then the elements of a Set are observably ordered in some way. Since
it's not an OrderedSet--i.e., order doesn't matter--then the only sensible
conclusion is that the order of elements obtained in a for...in loop must
be arbitrary. If you think this is harmful, then you must believe that one
should be prohibited from iterating over an instance of Set. Otherwise, Set
is inescapably a Sequence by the Swift definition of Sequence. All
extension methods on Sequence like drop(while:) are really just
conveniences for common things that you can do with iterated access; to my
mind, they're essentially just alternative ways of spelling various
for...in loops.I think an argument could be made that you shouldn’t be able to iterate
over a set without first defining an ordering on it (even if that ordering
is somewhat arbitrary). Maybe we have something like a “Sequenc(e)able”
protocol which defines things which can be turned into a sequence when
combined with some sort of ordering. One possible ordering could be the
internal representation (At least in that case we are calling it out
specifically). If I had to say “setA.arbitraryOrder.elementsEqual(setB.arbitraryOrder)”
I would definitely be less surprised when it returns false even though setA
== setB.
Well, that's a totally different direction, then; you're arguing that `Set`
and `Dictionary` should not conform to `Sequence` altogether. That's fine
(it's also a direction that some of us explored off-list a while ago), but
at this point in Swift's evolution, realistically, it's not within the
realm of possible changes.
If that is unergonomic, we could define an arbitrary but consistent
ordering over all Swift types that can be used to create a predictable
sequence order for unordered types. That is necessarily slower, but much
safer… and people concerned with speed could use something like
‘arbitraryOrder’ above to regain full speed.I am not arguing that that is necessarily the right approach, just that we
need more thought/discussion around what is actually causing the confusion
here: The fact that we are assuming an ordering on something where the
ordering is undefined.
The underlying source of the confusion is clear; I'm trying to encourage us
*not* to talk about it here, though, as it's not a tractable problem for
Swift 5.
On Sat, Oct 14, 2017 at 11:48 PM, Jonathan Hull <jhull@gbis.com> wrote:
On Oct 14, 2017, at 9:21 PM, Xiaodi Wu <xiaodi.wu@gmail.com> wrote:
On Sat, Oct 14, 2017 at 10:55 PM, Jonathan Hull <jhull@gbis.com> wrote:On Oct 14, 2017, at 7:55 PM, Xiaodi Wu via swift-evolution < >> swift-evolution@swift.org> wrote:
[…]
* 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.I’m not trying to bikeshed the name either, The underlying issue is that
(what is currently) Sequence actually encompasses two separate
functionalities, and those functionalities need to be separated with their
separate semantic requirements documented. “Sequence: Iterable,”
“OrderedSequence: Sequence,” “SpongeBob: ForLoopable,” the names are 100%
irrelevant at this point; what’s important is that one is not necessarily
ordered and the other guarantees an order.What are the "two separate functionalities”?
Iteration, with convenience methods that don’t imply or rely on an order
that may not be there; and convenience methods applicable to sequences that
do have an intrinsic order.
Sets, as a mathematical concept, have no intrinsic order. However,
instances of `Set`, which can be iterated over, *do* have at least one
order which can be said to be intrinsic in the following sense: as long as
iteration is possible, no API design can prevent that order from being
observed and associated with the instance. Put another way, if you can use
an instance of a type in a for...in loop, intrinsic to that functionality
is a publicly visible order.
All the extension methods on Sequence are ways of spelling things that you
can write in a few lines of code using a `for...in` loop; they're in the
stdlib to allow a more functional style which some prefer. If you accept
that a type should support iteration with a `for...in` loop, then what is
your basis for claiming that these extension methods are "separate
functionalities”?Just because you *can* express something in code doesn’t mean you should,
or that it’s correct. It is objectively false to say a Set has a first or
last object, because the objects therein have no order. You can take a
random object from the set and call it “first”, but that doesn’t make that
a correct definition of Set.first. A Set has no order, a specific iteration
has an “order” only in the sense that all and only the objects in the set
have to come out one at a time, but that doesn’t mean the Set itself has an
order, specifically a first or last object.
Since Set conforms to Collection, it is guaranteed that if one element of
an instance of Set comes out first one time, it'll come out first every
time from that instance. If it helps, think of Swift's Set as modeling
(imperfectly, as all models must) both a mathematical set and a multi-pass
sequence, just as Swift's Int models both an integer and a sequence of bits.
You’re a fan of the principal of least surprise. Tell me, which would be
less surprising: Set.dropFirst() actually drops a random element, or Set
doesn’t have a dropFirst()? And if you think dropFirst() removing an
element at random is not surprising, please explain why.
I think Set.dropFirst removing the first element that I observe on
iteration is the least surprising answer, because Swift tells me that the
stdlib Set models a set but that it is also a sequence.
[…]
* 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.Is `first` mutating? No. Should it be? No! `first` and `last` are a peek
at the state of the object.You're right, `first` should not be mutating; that's actually an important
design consideration, as Ole pointed out, and it's not actually available
on `Sequence` for that reason. However, `first { _ in true }` is available
and is potentially mutating, as are all methods on Sequence by design.Is `elementsEqual` (or *shudder* lexicographicallyEqual) reflexive? IMO it
clearly should be. Especially with the “lexicographically” part—from
everything I can find, a lexicographical ordering is by definition
reflexive. Do you have a citation for the idea that lexicographical
equality can legitimately be non-reflexive?Clearly (tautologically?), such a function should be reflexive for any
argument ordered with respect to itself. However, if there is no
lexicographical comparison possible, then a thing cannot compare
lexicographically equal to anything, even itself.And that’s PRECISELY why lexicographicallyEqual does not make sense to
apply to unordered sets. There is no lexicographical comparison possible,
so why do you keep insisting they should have a method that falsely claims
to lexicographically compare them?
I agree! It doesn't make sense if no comparison is possible! But Swift
tells me that a `Set` is a `Sequence`!
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.> IMO that’s a bug in the implementation; lexicographical equality is
reflexive, period.> Presumably the `elementsEqual` method contains something along these
lines (take from SequenceAlgorithms.swift.gyb):var iter1 = self.makeIterator()
var iter2 = other.makeIterator()> By creating two iterators, you’re mutating while iterating. Turns out
there’s even a warning against this in Sequence.swift:/// Using Multiple Iterators
/// ========================
///
/// Whenever you use multiple iterators (or `for`-`in` loops) over a single
/// sequence, be sure you know that the specific sequence supports repeated
/// iteration, either because you know its concrete type or because the
/// sequence is also constrained to the `Collection` protocol.
///
/// Obtain each separate iterator from separate calls to the sequence's
/// `makeIterator()` method rather than by copying. Copying an iterator is
/// safe, but advancing one copy of an iterator by calling its `next()`
method
/// may invalidate other copies of that iterator. `for`-`in` loops are
safe in
/// this regard.*> The default implementation of elementsEqual is therefore unsafe* because
it has the potential for using an invalidated iterator.You are misunderstanding the warning in the second paragraph here. The
implementation (not a default implementation, unless I'm mistaken, as it
cannot be overridden)makes each iterator using separate calls to `makeIterator()`, just as the
documentation tells you to do. Calling next() on one iterator does not
invalidate the other iterator, because the second is not a copy of the
first.Indeed, I misread that comment.
That said, is there a well-defined behavior when iterating a one-shot
sequence with two iterators?
(It *is* a default implementation, btw)
Not sure about that; I don't see a protocol requirement, in which case it
can only be shadowed in a concrete type but it can't be overridden. How to
accommodate single-pass sequences is an interesting question. Off the top
of my head, an iterator would have to be or wrap a reference type.
You are, however, right that calling `rng.elementsEqual(rng)` is not
advised. It isn't unsafe; it's just not useful. That said, calling
`array.elementsEqual(array)` is equally safe and equally useless, and the
uselessness of such a reflexive comparison is neither here nor there.Funny how you complain about my code being useless and yet you insist
below, "If it's not providing you with utility, then don't use it.”
Regardless, you’re wrong to dismiss this case. `foo.elementsEqual(foo)` on
its own makes little sense, sure, but you could easily find yourself in a
method comparing two iterators you obtained from elsewhere, and
occasionally they happen to be the identical object. Allowing an iterator
to return `false` for .elementsEqual on itself is unexpected and dangerous.
You will always have to account for this possibility, because Swift's
`Equatable` explicitly allows "special values" to be not equal to
themselves. This is, at least in part, in order to accommodate the IEEE
decree that NaN != NaN:
let x = [Double.nan]
x.elementsEqual(x) // false
Changing this behavior is way beyond the scope of this thread (and has been
the topic of hours (actually, weeks and weeks) of fun on this list
previously).
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.> Ordered, yes, but it’s only admittedly poor wording that suggests
multi-pass, and I don’t think anything there suggests finite.If a Sequence is "guaranteed to iterate the same every time," then surely
it must be multi-pass; what's the alternative?Not sure if you just missed the very next sentence or are actively
ignoring it just to be argumentative. I already acknowledged that that
phrase didn’t convey the meaning I intended, and a Sequence is not and
should not be required to be multi-pass.
I entirely misunderstood your next sentence as asserting that being
multi-pass makes the iteration order well-defined.
It would be better to say that the iteration order is well-defined. That
will almost always mean documented, and usually predictable though
obviously e.g. RNGs and iterating in random order will not be predictable
by design.Wouldn't it then suffice to document, say, that a set's iteration order is
the insertion order?
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.I think you’re talking about Sequence here, I’ve lost track of your
nonsense by now. Yes, the current Swift protocol named Sequence allows
unordered types. You seem to keep asserting that but not actually
addressing my argument, which is *that allowing Sequences to be
unordered with the current API is undesired and actively harmful, and
should* *therefore** be changed*.What is harmful about it?
Well, for one, the issue you raised this thread about—two sets that are
`==` could return either true or false for `elementsEqual`, depending on
how they arrived at their current state. That’s not acceptable, and the
problem isn’t with the name of the method.
Apple documentation calls this one of the "order-dependent" methods. It is
surely acceptable for a type that conforms to an order-dependent protocol
to have methods that are order-dependent; they do, however, have to be
clearly order-dependent to avoid confusion on unordered types.
Then there are all the methods that imply a specific order of iteration.
If the “sequence” is unordered, who knows what you’ll get? It is incredibly
easy for an engineer to write a method that implicitly relies on a passed
sequence being intrinsically ordered and another engineer to pass it an
unordered “sequence.” The first engineer could neglect to document the
dependency, or even not notice it; or the second engineer could just fail
to read the documentation thoroughly enough. There is currently no way for
the compiler to enforce passing only an object that is (or at least claims
to be) intrinsically ordered.
It is also incredibly easy for such an engineer to use `for...in` instead
to accomplish the same task, generic over ordered and unordered sequences
whatever you name such distinguished protocols. I think your beef really
still boils down to Set being compatible with `for...in` at all, as Jon
acknowledges.
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.It is “meaningful” in the sense that it can technically be programmed.
The actual results are meaningless beyond returning or dropping a random*
element.*: Don’t nitpick the word “random”, you know exactly what I mean. It’s
just shorter and no less clear than “technically more-or-less deterministic
but not documented, not generally predictable, and probably but not
necessarily consistent from one call to the next."I fail to see the issue here. If it's not providing you with utility, then
don't use it.I have no problem with functions I don’t use provided they are
well-defined and reasonably accurately named. Functions requiring an order
on unordered collections don’t pass that bar.
As I said, you're welcome to tackle the protocol hierarchy, but I really
doubt it's within the realm of realistic endpoints for Swift 5. I'm just
trying to propose a narrowly targeted pragmatic solution to one specific
limited harm that might be deliverable by the next point release. As a
great man once said, Swift is a pragmatic language.
Since Collections do guarantee multi-pass iteration, Brent's example of
`set.dropFirst().reduce(set.first!, ...)` provides just one instance
where an unordered Collection can profitably make use of `first`.
Permitting generic algorithms that can operate on either arrays or sets,
for example, is the desired effect of having such a protocol; a generic
algorithm that takes a Collection can ask for the first element, and in the
case of an unordered Collection, an arbitrary element will do just fine.The generic algorithms should be on a protocol that specifies everything
they require. If one can work on anything you can iterate over, put it on
Iterable. If another requires the objects to be ordered, put it on
Sequence. Need to express that an algorithm requires a multi-pass sequence?
Make a MultiPassSequence protocol and put the algorithm on an extension
containing that requirement. Use protocols to express requirements, as they
were designed for. Don’t just tack a bunch of methods onto a protocol that
isn’t sufficient to describe their requirements and say, “oh, by the way,
only use this method if your implementation meets these conditions…"
The benefits are likely outweighed by the costs of such an approach taken
to completion, because there are many axes to differentiate. The protocol
hierarchy for collections is already daunting, leading to monstrosities
such as `MutableRangeReplaceableRandomAccessSlice`. It stretches the bounds
of sensibility to have a
`LazyUnorderedInfiniteMultiPassMutableRangeReplaceableRandomAccessSlice`.
The Swift stdlib deliberately eschews modeling everything in protocol
hierarchies with the highest level of granularity. There's some fudging,
deliberately, to find a happy medium between obtuse and approachable,
between too many/too specialized and not enough. For example, I pushed for
protocols such as `Field` and `Ring` at the top of the numeric hierarchy,
which might allow complex number types to slot into the hierarchy more
sensibly, for example. But we have a compromise protocol `Numeric` which
doesn't quite have the same guarantees but is much more approachable.
Notice that we also don't break down numeric protocols into `Addable`,
`Subtractable`, etc.; we also have that fudge factor built into
`Equatable`, as I mentioned.
`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.No, no, no! What I want to call “Iterable” is specified below. It is
about HALF of what’s currently in Sequence—the half that has to do with
iterating, whence the name.
What I want to call Sequence is precisely what Swift now calls
Sequence—the methods that are in Iterable by virtue of adopting Iterable,
PLUS some methods that only make sense on iterable groups of objects where
the iteration order is well-defined.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.Apparently “collection" was a bad choice of word. What I clearly meant
was not the current Swift Collection protocol, but rather an unordered
assemblage of objects. UnorderedCollection, perhaps, or if that’s still
going to cause issues, try UnorderedAssemblage. What `first` and `last`
really mean in an UnorderedAssemblage is give me some object from the
assembled objects, I don’t care which one. For which it’s much more clear
to have an `anyObject()` as on NSSet; as another user has pointed out,
`assemblage.makeIterator().next()` works just as well. (I just checked,
and that’s actually how `first` is implemented. But it’s on Collection,
which is guaranteed to be multipass,)Again, the point of having a protocol-based design is to allow useful
_generic_ algorithms to be written; that `first` and `last` would be
equivalent to an arbitrary element in the case that a collection is
unordered is not at all an argument against these types conforming to
`Collection`; if anything, it's an argument for it.If a protocol demands the first object, you should give it the first
object. If you don’t have a first object, maybe you shouldn’t conform to
the protocol. If the protocol really just needs any old object, call it
`anyObject`.
Sure, but we *do* have a first element; it just happens to be the first
that is obtainable on iteration. That you could make a good case for any
other element to be first doesn't mean that this one isn't a perfectly
cromulent first.
Just as `Sequence.underestimatedCount` is equivalent to `Collection.count`
On Sun, Oct 15, 2017 at 2:29 AM, Kevin Nattinger <swift@nattinger.net> wrote:
On Oct 14, 2017, at 7:54 PM, Xiaodi Wu <xiaodi.wu@gmail.com> wrote:
On Sat, Oct 14, 2017 at 6:17 PM, Kevin Nattinger <swift@nattinger.net> > wrote:
for types that conform to `Collection`, or the instance
`BinaryInteger.bitWidth` is equivalent to a static `bitWidth` for types
that conform to `FixedWidthInteger`.I don’t see how those are relevant, they all mean what they claim to,
unlike Set.first/dropFirst/etc.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 {…}
> Ordered, yes, but it’s only admittedly poor wording that suggests multi-pass, and I don’t think anything there suggests finite.
If a Sequence is "guaranteed to iterate the same every time," then surely it must be multi-pass; what's the alternative?
Single-pass, but where two dictionaries/sets with the same elements would be guaranteed to output the same ordering.
I'm not sure I understand. A single-pass sequence is one where iteration can happen only once because it is destructive. By definition, then, it is not guaranteed to "iterate the same" a second time. Neither sets nor dictionaries are single-pass sequences. Kevin says that his definition of a "Sequence" is something "guaranteed to iterate the same every time," which requires them to be multi-pass, does it not?
But if I am comparing two single-pass things, the order can still be defined when they compare that one time. Single-pass doesn’t mean that the order is undefined. On the contrary, as you point out, it has a “first” thing, and then a thing after that, and so on.
Regardless, most of the objects we are talking about here are multi-pass collections (e.g. sets).
Right, but I'm trying to figure out why Kevin wants a Sequence to "iterate the same every time" and in what way that's not simply a Collection.
I guess you will have to ask Kevin that.
That ordering can be arbitrary, but it shouldn’t leak internal representation such that the method used to create identical things affects the outcome of generic methods because of differences in internal representation.
It would be better to say that the iteration order is well-defined. That will almost always mean documented, and usually predictable though obviously e.g. RNGs and iterating in random order will not be predictable by design.
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.
I think you’re talking about Sequence here, I’ve lost track of your nonsense by now. Yes, the current Swift protocol named Sequence allows unordered types. You seem to keep asserting that but not actually addressing my argument, which is that allowing Sequences to be unordered with the current API is undesired and actively harmful, and should therefore be changed.
What is harmful about it?
After thinking about it, I think the harmful bit is that unordered sequences are leaking internal representation (In your example, this is causing people to be surprised when two sets with identical elements are generating different sequences/orderings based on how they were created). You are correct when you say that this problem is even true for for-in.
I would not say it is a problem. Rather, by definition, iteration involves retrieving one element after another; if you're allowed to do that with Set, then the elements of a Set are observably ordered in some way. Since it's not an OrderedSet--i.e., order doesn't matter--then the only sensible conclusion is that the order of elements obtained in a for...in loop must be arbitrary. If you think this is harmful, then you must believe that one should be prohibited from iterating over an instance of Set. Otherwise, Set is inescapably a Sequence by the Swift definition of Sequence. All extension methods on Sequence like drop(while:) are really just conveniences for common things that you can do with iterated access; to my mind, they're essentially just alternative ways of spelling various for...in loops.
I think an argument could be made that you shouldn’t be able to iterate over a set without first defining an ordering on it (even if that ordering is somewhat arbitrary). Maybe we have something like a “Sequenc(e)able” protocol which defines things which can be turned into a sequence when combined with some sort of ordering. One possible ordering could be the internal representation (At least in that case we are calling it out specifically). If I had to say “setA.arbitraryOrder.elementsEqual(setB.arbitraryOrder)” I would definitely be less surprised when it returns false even though setA == setB.
Well, that's a totally different direction, then; you're arguing that `Set` and `Dictionary` should not conform to `Sequence` altogether. That's fine (it's also a direction that some of us explored off-list a while ago), but at this point in Swift's evolution, realistically, it's not within the realm of possible changes.
I am actually suggesting something slightly different. Basically, Set and Dictionary’s conformance to Collection would have a different implementation. They would conform to another protocol declaring that they are unordered. That protocol would fill in part of the conformance to sequence/collection using a default ordering, which is mostly arbitrary, but guaranteed to produce the same ordering for the same list of elements (even across collection types). This would be safer, but a tiny bit slower than what we have now (We could also potentially develop a way for collections like set to amortize the cost). For those who need to recover speed, the new protocol would also define a property which quickly returns a sequence/iterator using the internal ordering (I arbitrarily called it .arbitraryOrder).
I believe it would not be source breaking.
I am not arguing that that is necessarily the right approach, just that we need more thought/discussion around what is actually causing the confusion here: The fact that we are assuming an ordering on something where the ordering is undefined.
The underlying source of the confusion is clear; I'm trying to encourage us *not* to talk about it here, though, as it's not a tractable problem for Swift 5.
I find that problematic.
There are a range of potential solutions that are being offered, from renaming the ‘elementsEqual’ to other things besides ‘lexicographicallyEquals’ to updating our sequence/collection protocols in a minimally source breaking (or even source compatible) way.
Also, I would also argue that if we do find that there are real problems with the sequence protocols, now is the time to fix them before the ABI is set.
Thanks,
Jon
On Oct 14, 2017, at 9:59 PM, Xiaodi Wu <xiaodi.wu@gmail.com> wrote:
On Sat, Oct 14, 2017 at 11:48 PM, Jonathan Hull <jhull@gbis.com <mailto:jhull@gbis.com>> wrote:On Oct 14, 2017, at 9:21 PM, Xiaodi Wu <xiaodi.wu@gmail.com <mailto:xiaodi.wu@gmail.com>> wrote:
On Sat, Oct 14, 2017 at 10:55 PM, Jonathan Hull <jhull@gbis.com <mailto:jhull@gbis.com>> wrote:On Oct 14, 2017, at 7:55 PM, Xiaodi Wu via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:
> Ordered, yes, but it’s only admittedly poor wording that suggests
multi-pass, and I don’t think anything there suggests finite.If a Sequence is "guaranteed to iterate the same every time," then
surely it must be multi-pass; what's the alternative?Single-pass, but where two dictionaries/sets with the same elements
would be guaranteed to output the same ordering.I'm not sure I understand. A single-pass sequence is one where iteration
can happen only once because it is destructive. By definition, then, it is
not guaranteed to "iterate the same" a second time. Neither sets nor
dictionaries are single-pass sequences. Kevin says that his definition of a
"Sequence" is something "guaranteed to iterate the same every time," which
requires them to be multi-pass, does it not?But if I am comparing two single-pass things, the order can still be
defined when they compare that one time. Single-pass doesn’t mean that the
order is undefined. On the contrary, as you point out, it has a “first”
thing, and then a thing after that, and so on.Regardless, most of the objects we are talking about here are multi-pass
collections (e.g. sets).Right, but I'm trying to figure out why Kevin wants a Sequence to "iterate
the same every time" and in what way that's not simply a Collection.I guess you will have to ask Kevin that.
Indeed, I'm asking Kevin that.
That ordering can be arbitrary, but it shouldn’t leak internal
representation such that the method used to create identical things affects
the outcome of generic methods because of differences in internal
representation.It would be better to say that the iteration order is well-defined.
That will almost always mean documented, and usually predictable though
obviously e.g. RNGs and iterating in random order will not be predictable
by design.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.I think you’re talking about Sequence here, I’ve lost track of your
nonsense by now. Yes, the current Swift protocol named Sequence allows
unordered types. You seem to keep asserting that but not actually
addressing my argument, which is *that allowing Sequences to be
unordered with the current API is undesired and actively harmful, and
should* *therefore** be changed*.What is harmful about it?
After thinking about it, I think the harmful bit is that unordered
sequences are leaking internal representation (In your example, this is
causing people to be surprised when two sets with identical elements are
generating different sequences/orderings based on how they were created).
You are correct when you say that this problem is even true for for-in.I would not say it is a problem. Rather, by definition, iteration
involves retrieving one element after another; if you're allowed to do that
with Set, then the elements of a Set are observably ordered in some way.
Since it's not an OrderedSet--i.e., order doesn't matter--then the only
sensible conclusion is that the order of elements obtained in a for...in
loop must be arbitrary. If you think this is harmful, then you must believe
that one should be prohibited from iterating over an instance of Set.
Otherwise, Set is inescapably a Sequence by the Swift definition of
Sequence. All extension methods on Sequence like drop(while:) are really
just conveniences for common things that you can do with iterated access;
to my mind, they're essentially just alternative ways of spelling various
for...in loops.I think an argument could be made that you shouldn’t be able to iterate
over a set without first defining an ordering on it (even if that ordering
is somewhat arbitrary). Maybe we have something like a “Sequenc(e)able”
protocol which defines things which can be turned into a sequence when
combined with some sort of ordering. One possible ordering could be the
internal representation (At least in that case we are calling it out
specifically). If I had to say “setA.arbitraryOrder.elementsEqual(setB.arbitraryOrder)”
I would definitely be less surprised when it returns false even though setA
== setB.Well, that's a totally different direction, then; you're arguing that
`Set` and `Dictionary` should not conform to `Sequence` altogether. That's
fine (it's also a direction that some of us explored off-list a while ago),
but at this point in Swift's evolution, realistically, it's not within the
realm of possible changes.I am actually suggesting something slightly different. Basically, Set and
Dictionary’s conformance to Collection would have a different
implementation. They would conform to another protocol declaring that they
are unordered. That protocol would fill in part of the conformance to
sequence/collection using a default ordering, which is mostly arbitrary,
but guaranteed to produce the same ordering for the same list of elements
(even across collection types). This would be safer, but a tiny bit slower
than what we have now (We could also potentially develop a way for
collections like set to amortize the cost). For those who need to recover
speed, the new protocol would also define a property which quickly returns
a sequence/iterator using the internal ordering (I arbitrarily called it
.arbitraryOrder).I believe it would not be source breaking.
That is indeed something slightly different.
In an ideal world--and my initial understanding of what you were
suggesting--Set and Dictionary would each have a member like `collection`,
which would expose the underlying data as a `SetCollection` or
`DictionaryCollection` that in turn would conform to `Collection`;
meanwhile, Set and Dictionary themselves would not offer methods such as
`prefix`, or indexing by subscript, which are not compatible with being
unordered. For those who want a particular ordering, there'd be something
like `collection(ordered areInIncreasingOrder: (T, T) -> Bool) ->
{Set|Dictionary}Collection`.
What you suggest here instead would be minimally source-breaking. However,
I'm unsure of where these guarantees provide benefit to justify the
performance cost. Certainly not for `first` or `dropFirst(_:)`, which still
yields an arbitrary result which doesn't make sense for something
_unordered_. We *could* have an underscored customization point named
something like `_customOrderingPass` that is only invoked from
`elementsEqual` or other such methods to pre-rearrange the internal
ordering of unordered collections in some deterministic way before
comparison. Is that what you have in mind?
I am not arguing that that is necessarily the right approach, just that we
need more thought/discussion around what is actually causing the confusion
here: The fact that we are assuming an ordering on something where the
ordering is undefined.The underlying source of the confusion is clear; I'm trying to encourage
us *not* to talk about it here, though, as it's not a tractable problem for
Swift 5.I find that problematic.
There are a range of potential solutions that are being offered, from
renaming the ‘elementsEqual’ to other things besides
‘lexicographicallyEquals’ to updating our sequence/collection protocols in
a minimally source breaking (or even source compatible) way.
...to fundamentally changing the protocol hierarchy, which is what I'm
encouraging us *not* to talk about. If it's source-compatible or
justifiably limited to breaking only provably harmful behavior, then of
course we should discuss it.
On Sun, Oct 15, 2017 at 12:33 AM, Jonathan Hull <jhull@gbis.com> wrote:
On Oct 14, 2017, at 9:59 PM, Xiaodi Wu <xiaodi.wu@gmail.com> wrote:
On Sat, Oct 14, 2017 at 11:48 PM, Jonathan Hull <jhull@gbis.com> wrote:On Oct 14, 2017, at 9:21 PM, Xiaodi Wu <xiaodi.wu@gmail.com> wrote:
On Sat, Oct 14, 2017 at 10:55 PM, Jonathan Hull <jhull@gbis.com> wrote:On Oct 14, 2017, at 7:55 PM, Xiaodi Wu via swift-evolution < >>> swift-evolution@swift.org> wrote:
Also, I would also argue that if we do find that there are real problems
with the sequence protocols, now is the time to fix them before the ABI is
set.Thanks,
Jon
[…]
Sets, as a mathematical concept, have no intrinsic order. However, instances of `Set`, which can be iterated over, *do* have at least one order which can be said to be intrinsic in the following sense: as long as iteration is possible, no API design can prevent that order from being observed and associated with the instance. Put another way, if you can use an instance of a type in a for...in loop, intrinsic to that functionality is a publicly visible order.
You keep saying this, I keep saying it’s only a technical “order” that is an implementation detail and can’t be relied upon for anything and so we shouldn’t provide methods that rely on it. I think this part of the discussion has reached the “agree to disagree” stage.
[…]
You’re a fan of the principal of least surprise. Tell me, which would be less surprising: Set.dropFirst() actually drops a random element, or Set doesn’t have a dropFirst()? And if you think dropFirst() removing an element at random is not surprising, please explain why.I think Set.dropFirst removing the first element that I observe on iteration is the least surprising answer, because Swift tells me that the stdlib Set models a set but that it is also a sequence.
Your logic is backwards. You’re saying it’s “least surprising” because that’s how it’s currently implemented, not that it should be implemented that way because it’s least surprising.
[…]
And that’s PRECISELY why lexicographicallyEqual does not make sense to apply to unordered sets. There is no lexicographical comparison possible, so why do you keep insisting they should have a method that falsely claims to lexicographically compare them?
I agree! It doesn't make sense if no comparison is possible! But Swift tells me that a `Set` is a `Sequence`!
You keep making the circular argument that a Set should do things because it currently does them. If you want to argue against changing things, argue that things shouldn’t be changed, not that the current implementation is correct because it is the current implementation.
[…]
You will always have to account for this possibility, because Swift's `Equatable` explicitly allows "special values" to be not equal to themselves. This is, at least in part, in order to accommodate the IEEE decree that NaN != NaN:
let x = [Double.nan] x.elementsEqual(x) // false
NaN is special, one-shot and unordered sequences are not. Unless you think that all unordered and single-pass sequences should compare false for `elementsEqual`, this is irrelevant for any sequence that doesn’t contain NaN and well-defined (false) for any that does.
Changing this behavior is way beyond the scope of this thread (and has been the topic of hours (actually, weeks and weeks) of fun on this list previously).
Yes, I’ve seen the discussion on NaN and Comparable. It’s not the same discussion.
[…]
It would be better to say that the iteration order is well-defined. That will almost always mean documented, and usually predictable though obviously e.g. RNGs and iterating in random order will not be predictable by design.
Wouldn't it then suffice to document, say, that a set's iteration order is the insertion order?
Now this actually gave me pause. I guess it does match what I said, but I still take issue with the fact that two Sets could compare `==` but not `elementsEqual`. I think that defining iteration order as insertion order adds a piece of publicly documented state that goes beyond what a Set really is. What you describe is really an OrderedSet, just without the random-access manipulation. I’ll have to mull this over to see if I can come up with a coherent and (more) specific requirement for what makes an Iterable a Sequence, since clearly “documented” isn’t enough. Perhaps something along the lines that any two Sequences that compare equal must iterate the same.
[…]
Apple documentation calls this one of the "order-dependent" methods. It is surely acceptable for a type that conforms to an order-dependent protocol to have methods that are order-dependent; they do, however, have to be clearly order-dependent to avoid confusion on unordered types.
I’m not clear on what you’re trying to get across here. It seems you’re saying unordered types shouldn’t have order-dependent methods, which is exactly what I’ve been arguing.
[...]
Then there are all the methods that imply a specific order of iteration. If the “sequence” is unordered, who knows what you’ll get? It is incredibly easy for an engineer to write a method that implicitly relies on a passed sequence being intrinsically ordered and another engineer to pass it an unordered “sequence.” The first engineer could neglect to document the dependency, or even not notice it; or the second engineer could just fail to read the documentation thoroughly enough. There is currently no way for the compiler to enforce passing only an object that is (or at least claims to be) intrinsically ordered.It is also incredibly easy for such an engineer to use `for...in` instead to accomplish the same task, generic over ordered and unordered sequences whatever you name such distinguished protocols. I think your beef really still boils down to Set being compatible with `for...in` at all, as Jon acknowledges.
Not providing ordered functions for unordered collections makes the developers think about what they actually need. If any object will do, they can use for…in, .makeIterator().next(), or an `anyObject()` we provide as a convenience. If they actually need the first from some specific order, it’s a reminder they need to sort the objects first to get the right one. That’s particularly useful for functions that actually need an ordered sequence; using OrderedSequence instead of Iterable (just as placeholders) would be a firm reminder not to pass in an unordered collection.
[…]
As I said, you're welcome to tackle the protocol hierarchy, but I really doubt it's within the realm of realistic endpoints for Swift 5. I'm just trying to propose a narrowly targeted pragmatic solution to one specific limited harm that might be deliverable by the next point release. As a great man once said, Swift is a pragmatic language.
If you want a pragmatic solution, fix the bug in functionality, don’t try and rename the method to something obscure to cover it up.
If you want to limit the harm, override `equalObjects` on unordered sequences to use `==` (very strongly preferred), or always `false` (less desirable, but at least consistent)
[…]
The Swift stdlib deliberately eschews modeling everything in protocol hierarchies with the highest level of granularity. There's some fudging, deliberately, to find a happy medium between obtuse and approachable, between too many/too specialized and not enough. For example, I pushed for protocols such as `Field` and `Ring` at the top of the numeric hierarchy, which might allow complex number types to slot into the hierarchy more sensibly, for example. But we have a compromise protocol `Numeric` which doesn't quite have the same guarantees but is much more approachable. Notice that we also don't break down numeric protocols into `Addable`, `Subtractable`, etc.; we also have that fudge factor built into `Equatable`, as I mentioned.
Eh, one or two corner cases on a protocol is probably fine. What’s not fine is over half (Sequence) or almost all (Collection) the methods not being applicable. There is a very clear gap there. We don’t need to fix everything, but this is something that can and should be addressed.
[…]
[…]
* 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.
I’m not trying to bikeshed the name either, The underlying issue is that (what is currently) Sequence actually encompasses two separate functionalities, and those functionalities need to be separated with their separate semantic requirements documented. “Sequence: Iterable,” “OrderedSequence: Sequence,” “SpongeBob: ForLoopable,” the names are 100% irrelevant at this point; what’s important is that one is not necessarily ordered and the other guarantees an order.
What are the "two separate functionalities”?
Iteration, with convenience methods that don’t imply or rely on an order that may not be there; and convenience methods applicable to sequences that do have an intrinsic order.
Sets, as a mathematical concept, have no intrinsic order. However, instances of `Set`, which can be iterated over, *do* have at least one order which can be said to be intrinsic in the following sense: as long as iteration is possible, no API design can prevent that order from being observed and associated with the instance. Put another way, if you can use an instance of a type in a for...in loop, intrinsic to that functionality is a publicly visible order.
I disagree. Sets are value types, therefore two instances of `Set` are equal if they contain the same elements. An intrinsic order should therefore only depend on the elements contained and should be the same for two instances of `Set` which are equal.
This is not the case, though, as you can easily check in a playground by looking at Set([1,2,3,4,5,6]) and Set([6,5,4,3,2,1]) which represent the same value and are equal but do *not* have the same order.
All the extension methods on Sequence are ways of spelling things that you can write in a few lines of code using a `for...in` loop; they're in the stdlib to allow a more functional style which some prefer. If you accept that a type should support iteration with a `for...in` loop, then what is your basis for claiming that these extension methods are "separate functionalities”?
Just because you *can* express something in code doesn’t mean you should, or that it’s correct. It is objectively false to say a Set has a first or last object, because the objects therein have no order. You can take a random object from the set and call it “first”, but that doesn’t make that a correct definition of Set.first. A Set has no order, a specific iteration has an “order” only in the sense that all and only the objects in the set have to come out one at a time, but that doesn’t mean the Set itself has an order, specifically a first or last object.
Since Set conforms to Collection, it is guaranteed that if one element of an instance of Set comes out first one time, it'll come out first every time from that instance. If it helps, think of Swift's Set as modeling (imperfectly, as all models must) both a mathematical set and a multi-pass sequence, just as Swift's Int models both an integer and a sequence of bits.
You’re a fan of the principal of least surprise. Tell me, which would be less surprising: Set.dropFirst() actually drops a random element, or Set doesn’t have a dropFirst()? And if you think dropFirst() removing an element at random is not surprising, please explain why.
I think Set.dropFirst removing the first element that I observe on iteration is the least surprising answer, because Swift tells me that the stdlib Set models a set but that it is also a sequence.
The latter is exactly the problem Kevin did point out. A Set is an Iterable (in the sense that I can iterate over its elements with the order being a meaningless random side effect) but it is *not* a Sequence (in the sense that the order conveys any meaning).
-Thorsten
Am 15.10.2017 um 10:38 schrieb Xiaodi Wu via swift-evolution <swift-evolution@swift.org>:
On Sun, Oct 15, 2017 at 2:29 AM, Kevin Nattinger <swift@nattinger.net <mailto:swift@nattinger.net>> wrote:On Oct 14, 2017, at 7:54 PM, Xiaodi Wu <xiaodi.wu@gmail.com <mailto:xiaodi.wu@gmail.com>> wrote:
On Sat, Oct 14, 2017 at 6:17 PM, Kevin Nattinger <swift@nattinger.net <mailto:swift@nattinger.net>> wrote:
[…]
* 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.
Is `first` mutating? No. Should it be? No! `first` and `last` are a peek at the state of the object.
You're right, `first` should not be mutating; that's actually an important design consideration, as Ole pointed out, and it's not actually available on `Sequence` for that reason. However, `first { _ in true }` is available and is potentially mutating, as are all methods on Sequence by design.
Is `elementsEqual` (or *shudder* lexicographicallyEqual) reflexive? IMO it clearly should be. Especially with the “lexicographically” part—from everything I can find, a lexicographical ordering is by definition reflexive. Do you have a citation for the idea that lexicographical equality can legitimately be non-reflexive?
Clearly (tautologically?), such a function should be reflexive for any argument ordered with respect to itself. However, if there is no lexicographical comparison possible, then a thing cannot compare lexicographically equal to anything, even itself.
And that’s PRECISELY why lexicographicallyEqual does not make sense to apply to unordered sets. There is no lexicographical comparison possible, so why do you keep insisting they should have a method that falsely claims to lexicographically compare them?
I agree! It doesn't make sense if no comparison is possible! But Swift tells me that a `Set` is a `Sequence`!
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.
> IMO that’s a bug in the implementation; lexicographical equality is reflexive, period.
> Presumably the `elementsEqual` method contains something along these lines (take from SequenceAlgorithms.swift.gyb):
var iter1 = self.makeIterator()
var iter2 = other.makeIterator()> By creating two iterators, you’re mutating while iterating. Turns out there’s even a warning against this in Sequence.swift:
/// Using Multiple Iterators
/// ========================
///
/// Whenever you use multiple iterators (or `for`-`in` loops) over a single
/// sequence, be sure you know that the specific sequence supports repeated
/// iteration, either because you know its concrete type or because the
/// sequence is also constrained to the `Collection` protocol.
///
/// Obtain each separate iterator from separate calls to the sequence's
/// `makeIterator()` method rather than by copying. Copying an iterator is
/// safe, but advancing one copy of an iterator by calling its `next()` method
/// may invalidate other copies of that iterator. `for`-`in` loops are safe in
/// this regard.> The default implementation of elementsEqual is therefore unsafe because it has the potential for using an invalidated iterator.
You are misunderstanding the warning in the second paragraph here. The implementation (not a default implementation, unless I'm mistaken, as it cannot be overridden)
makes each iterator using separate calls to `makeIterator()`, just as the documentation tells you to do. Calling next() on one iterator does not invalidate the other iterator, because the second is not a copy of the first.
Indeed, I misread that comment.
That said, is there a well-defined behavior when iterating a one-shot sequence with two iterators?
(It *is* a default implementation, btw)Not sure about that; I don't see a protocol requirement, in which case it can only be shadowed in a concrete type but it can't be overridden. How to accommodate single-pass sequences is an interesting question. Off the top of my head, an iterator would have to be or wrap a reference type.
You are, however, right that calling `rng.elementsEqual(rng)` is not advised. It isn't unsafe; it's just not useful. That said, calling `array.elementsEqual(array)` is equally safe and equally useless, and the uselessness of such a reflexive comparison is neither here nor there.
Funny how you complain about my code being useless and yet you insist below, "If it's not providing you with utility, then don't use it.”
Regardless, you’re wrong to dismiss this case. `foo.elementsEqual(foo)` on its own makes little sense, sure, but you could easily find yourself in a method comparing two iterators you obtained from elsewhere, and occasionally they happen to be the identical object. Allowing an iterator to return `false` for .elementsEqual on itself is unexpected and dangerous.You will always have to account for this possibility, because Swift's `Equatable` explicitly allows "special values" to be not equal to themselves. This is, at least in part, in order to accommodate the IEEE decree that NaN != NaN:
let x = [Double.nan] x.elementsEqual(x) // falseChanging this behavior is way beyond the scope of this thread (and has been the topic of hours (actually, weeks and weeks) of fun on this list previously).
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.
> Ordered, yes, but it’s only admittedly poor wording that suggests multi-pass, and I don’t think anything there suggests finite.
If a Sequence is "guaranteed to iterate the same every time," then surely it must be multi-pass; what's the alternative?
Not sure if you just missed the very next sentence or are actively ignoring it just to be argumentative. I already acknowledged that that phrase didn’t convey the meaning I intended, and a Sequence is not and should not be required to be multi-pass.
I entirely misunderstood your next sentence as asserting that being multi-pass makes the iteration order well-defined.
It would be better to say that the iteration order is well-defined. That will almost always mean documented, and usually predictable though obviously e.g. RNGs and iterating in random order will not be predictable by design.
Wouldn't it then suffice to document, say, that a set's iteration order is the insertion order?
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.
I think you’re talking about Sequence here, I’ve lost track of your nonsense by now. Yes, the current Swift protocol named Sequence allows unordered types. You seem to keep asserting that but not actually addressing my argument, which is that allowing Sequences to be unordered with the current API is undesired and actively harmful, and should therefore be changed.
What is harmful about it?
Well, for one, the issue you raised this thread about—two sets that are `==` could return either true or false for `elementsEqual`, depending on how they arrived at their current state. That’s not acceptable, and the problem isn’t with the name of the method.
Apple documentation calls this one of the "order-dependent" methods. It is surely acceptable for a type that conforms to an order-dependent protocol to have methods that are order-dependent; they do, however, have to be clearly order-dependent to avoid confusion on unordered types.
Then there are all the methods that imply a specific order of iteration. If the “sequence” is unordered, who knows what you’ll get? It is incredibly easy for an engineer to write a method that implicitly relies on a passed sequence being intrinsically ordered and another engineer to pass it an unordered “sequence.” The first engineer could neglect to document the dependency, or even not notice it; or the second engineer could just fail to read the documentation thoroughly enough. There is currently no way for the compiler to enforce passing only an object that is (or at least claims to be) intrinsically ordered.
It is also incredibly easy for such an engineer to use `for...in` instead to accomplish the same task, generic over ordered and unordered sequences whatever you name such distinguished protocols. I think your beef really still boils down to Set being compatible with `for...in` at all, as Jon acknowledges.
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.It is “meaningful” in the sense that it can technically be programmed. The actual results are meaningless beyond returning or dropping a random* element.
*: Don’t nitpick the word “random”, you know exactly what I mean. It’s just shorter and no less clear than “technically more-or-less deterministic but not documented, not generally predictable, and probably but not necessarily consistent from one call to the next."
I fail to see the issue here. If it's not providing you with utility, then don't use it.
I have no problem with functions I don’t use provided they are well-defined and reasonably accurately named. Functions requiring an order on unordered collections don’t pass that bar.
As I said, you're welcome to tackle the protocol hierarchy, but I really doubt it's within the realm of realistic endpoints for Swift 5. I'm just trying to propose a narrowly targeted pragmatic solution to one specific limited harm that might be deliverable by the next point release. As a great man once said, Swift is a pragmatic language.
Since Collections do guarantee multi-pass iteration, Brent's example of `set.dropFirst().reduce(set.first!, ...)` provides just one instance where an unordered Collection can profitably make use of `first`. Permitting generic algorithms that can operate on either arrays or sets, for example, is the desired effect of having such a protocol; a generic algorithm that takes a Collection can ask for the first element, and in the case of an unordered Collection, an arbitrary element will do just fine.
The generic algorithms should be on a protocol that specifies everything they require. If one can work on anything you can iterate over, put it on Iterable. If another requires the objects to be ordered, put it on Sequence. Need to express that an algorithm requires a multi-pass sequence? Make a MultiPassSequence protocol and put the algorithm on an extension containing that requirement. Use protocols to express requirements, as they were designed for. Don’t just tack a bunch of methods onto a protocol that isn’t sufficient to describe their requirements and say, “oh, by the way, only use this method if your implementation meets these conditions…"
The benefits are likely outweighed by the costs of such an approach taken to completion, because there are many axes to differentiate. The protocol hierarchy for collections is already daunting, leading to monstrosities such as `MutableRangeReplaceableRandomAccessSlice`. It stretches the bounds of sensibility to have a `LazyUnorderedInfiniteMultiPassMutableRangeReplaceableRandomAccessSlice`.
The Swift stdlib deliberately eschews modeling everything in protocol hierarchies with the highest level of granularity. There's some fudging, deliberately, to find a happy medium between obtuse and approachable, between too many/too specialized and not enough. For example, I pushed for protocols such as `Field` and `Ring` at the top of the numeric hierarchy, which might allow complex number types to slot into the hierarchy more sensibly, for example. But we have a compromise protocol `Numeric` which doesn't quite have the same guarantees but is much more approachable. Notice that we also don't break down numeric protocols into `Addable`, `Subtractable`, etc.; we also have that fudge factor built into `Equatable`, as I mentioned.
`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.
No, no, no! What I want to call “Iterable” is specified below. It is about HALF of what’s currently in Sequence—the half that has to do with iterating, whence the name.
What I want to call Sequence is precisely what Swift now calls Sequence—the methods that are in Iterable by virtue of adopting Iterable, PLUS some methods that only make sense on iterable groups of objects where the iteration order is well-defined.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.
Apparently “collection" was a bad choice of word. What I clearly meant was not the current Swift Collection protocol, but rather an unordered assemblage of objects. UnorderedCollection, perhaps, or if that’s still going to cause issues, try UnorderedAssemblage. What `first` and `last` really mean in an UnorderedAssemblage is give me some object from the assembled objects, I don’t care which one. For which it’s much more clear to have an `anyObject()` as on NSSet; as another user has pointed out, `assemblage.makeIterator().next()` works just as well. (I just checked, and that’s actually how `first` is implemented. But it’s on Collection, which is guaranteed to be multipass,)
Again, the point of having a protocol-based design is to allow useful _generic_ algorithms to be written; that `first` and `last` would be equivalent to an arbitrary element in the case that a collection is unordered is not at all an argument against these types conforming to `Collection`; if anything, it's an argument for it.
If a protocol demands the first object, you should give it the first object. If you don’t have a first object, maybe you shouldn’t conform to the protocol. If the protocol really just needs any old object, call it `anyObject`.
Sure, but we *do* have a first element; it just happens to be the first that is obtainable on iteration. That you could make a good case for any other element to be first doesn't mean that this one isn't a perfectly cromulent first.
Just as `Sequence.underestimatedCount` is equivalent to `Collection.count` for types that conform to `Collection`, or the instance `BinaryInteger.bitWidth` is equivalent to a static `bitWidth` for types that conform to `FixedWidthInteger`.
I don’t see how those are relevant, they all mean what they claim to, unlike Set.first/dropFirst/etc.
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's Sequence protocol does not require the order of iteration to "convey any meaning"; it doesn't even require it to be deterministic.
And that’s EXACTLY why none of the functions on Sequence should rely on the order conveying meaning. `ElementsEqual` (for example) DOES rely on the order of iteration conveying a meaning not required by the protocol, and renaming it `lexicographicallyEquals` does not change that fact. Either Sequence needs to require a meaningful order or `elementsEqual` should be moved to a protocol that does.
Why not use an equals Implementation that doesn't rely on order?
Something like this (which doesn't compile in my iPad playground). If two sets have the same number of elements, and every element in one can be found in the other, they are equal, otherwise they are not equal.
protocol Set {
static func == (lhs: Self, rhs: Self) {
guard lhs.count == rhs.count else { return false }
for x in lhs {
if !rhs.contains(x) { return false }
}
return true
}
}
--
C. Keith Ray
* https://leanpub.com/wepntk <- buy my book?
* http://www.thirdfoundationsw.com/keith_ray_resume_2014_long.pdf
* http://agilesolutionspace.blogspot.com/
On Oct 15, 2017, at 12:40 PM, Kevin Nattinger via swift-evolution <swift-evolution@swift.org> wrote:
[…]
Swift's Sequence protocol does not require the order of iteration to "convey any meaning"; it doesn't even require it to be deterministic.And that’s EXACTLY why none of the functions on Sequence should rely on the order conveying meaning. `ElementsEqual` (for example) DOES rely on the order of iteration conveying a meaning not required by the protocol, and renaming it `lexicographicallyEquals` does not change that fact. Either Sequence needs to require a meaningful order or `elementsEqual` should be moved to a protocol that does.
_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution
That is what == does: https://github.com/apple/swift/blob/master/stdlib/public/core/HashedCollections.swift.gyb#L1267
On Oct 15, 2017, at 1:25 PM, C. Keith Ray via swift-evolution <swift-evolution@swift.org> wrote:
Why not use an equals Implementation that doesn't rely on order?
Something like this (which doesn't compile in my iPad playground). If two sets have the same number of elements, and every element in one can be found in the other, they are equal, otherwise they are not equal.
protocol Set {
static func == (lhs: Self, rhs: Self) {
guard lhs.count == rhs.count else { return false }
for x in lhs {
if !rhs.contains(x) { return false }
}
return true
}
}--
C. Keith Ray* https://leanpub.com/wepntk <- buy my book?
* http://www.thirdfoundationsw.com/keith_ray_resume_2014_long.pdf
* http://agilesolutionspace.blogspot.com/On Oct 15, 2017, at 12:40 PM, Kevin Nattinger via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:
[…]
Swift's Sequence protocol does not require the order of iteration to "convey any meaning"; it doesn't even require it to be deterministic.And that’s EXACTLY why none of the functions on Sequence should rely on the order conveying meaning. `ElementsEqual` (for example) DOES rely on the order of iteration conveying a meaning not required by the protocol, and renaming it `lexicographicallyEquals` does not change that fact. Either Sequence needs to require a meaningful order or `elementsEqual` should be moved to a protocol that does.
_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org <mailto: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
[…]
Sets, as a mathematical concept, have no intrinsic order. However,
instances of `Set`, which can be iterated over, *do* have at least one
order which can be said to be intrinsic in the following sense: as long as
iteration is possible, no API design can prevent that order from being
observed and associated with the instance. Put another way, if you can use
an instance of a type in a for...in loop, intrinsic to that functionality
is a publicly visible order.You keep saying this, I keep saying it’s only a technical “order” that is
an implementation detail
You keep saying it's an implementation detail, which it emphatically is
*not*. It's a *public guarantee* by the protocol that you can use an
instance of `Set` in a `for...in` loop, thereby exposing a publicly visible
order. An implementation detail is something that could go away with an
alternative implementation. By contrast, no implementation that permits an
instance of `Set` being iterated over in a `for...in` loop can avoid
exposing at least one publicly visible order, because it's not a matter of
implementation. Put another way, by allowing iteration, a type necessarily
exposes at least one publicly visible order and thereby models a sequence
in at least one way.
and can’t be relied upon for anything and so we shouldn’t provide methods
that rely on it. I think this part of the discussion has reached the “agree
to disagree” stage.[…]
You’re a fan of the principal of least surprise. Tell me, which would be
less surprising: Set.dropFirst() actually drops a random element, or Set
doesn’t have a dropFirst()? And if you think dropFirst() removing an
element at random is not surprising, please explain why.I think Set.dropFirst removing the first element that I observe on
iteration is the least surprising answer, because Swift tells me that the
stdlib Set models a set but that it is also a sequence.Your logic is backwards. You’re saying it’s “least surprising” because
that’s how it’s currently implemented, not that it should be implemented
that way because it’s least surprising.
No, I'm saying it's least surprising because any type that supports
iterated access thereby exposes an order--not as an implementation detail
but as a matter of public API--and in the absence of any other order,
"first" must refer to that order so exposed.
[…]
And that’s PRECISELY why lexicographicallyEqual does not make sense to
apply to unordered sets. There is no lexicographical comparison possible,
so why do you keep insisting they should have a method that falsely claims
to lexicographically compare them?I agree! It doesn't make sense if no comparison is possible! But Swift
tells me that a `Set` is a `Sequence`!You keep making the circular argument that a Set should do things because
it currently does them. If you want to argue against changing things, argue
that things shouldn’t be changed, not that the current implementation is
correct because it is the current implementation.
No, I'm arguing that `Set`, by supporting iterated access, is not wrong to
conform to a protocol called `Sequence` because it does have an intrinsic
and publicly observable order, which is not an accident of a particular
implementation but is inherent to any type that supports iterated access.
Now, whether it's the *best choice* to conform `Set` to `Sequence` and
offer order-dependent functions is a matter of taste, but it isn't *wrong*.
[…]
You will always have to account for this possibility, because Swift's
`Equatable` explicitly allows "special values" to be not equal to
themselves. This is, at least in part, in order to accommodate the IEEE
decree that NaN != NaN:let x = [Double.nan] x.elementsEqual(x) // falseNaN is special, one-shot and unordered sequences are not. Unless you think
that all unordered and single-pass sequences should compare false for
`elementsEqual`, this is irrelevant for any sequence that doesn’t contain
NaN and well-defined (false) for any that does.
Certainly, not all single-pass sequences should compare false to
themselves, but some should: for instance, an infinite single-pass stream
of all 1's should compare true to itself, but an infinite single-pass
stream of alternating 1's and 0's should compare false to itself. If you
write generic code that calls `elementsEqual`, it is pervasively incorrect
to test for identity by assuming that elementsEqual will return true on
reflexive comparison. NaN is only one of many reasons why such code would
blow up.
Changing this behavior is way beyond the scope of this thread (and has
been the topic of hours (actually, weeks and weeks) of fun on this list
previously).Yes, I’ve seen the discussion on NaN and Comparable. It’s not the same
discussion.[…]
It would be better to say that the iteration order is well-defined. That
will almost always mean documented, and usually predictable though
obviously e.g. RNGs and iterating in random order will not be predictable
by design.Wouldn't it then suffice to document, say, that a set's iteration order
is the insertion order?
Now this actually gave me pause. I guess it does match what I said, but I
still take issue with the fact that two Sets could compare `==` but not
`elementsEqual`. I think that defining iteration order as insertion order
adds a piece of publicly documented state that goes beyond what a Set
really is. What you describe is really an OrderedSet, just without the
random-access manipulation.
a) There is no semantic requirement on the part of `==` to be equivalent to
an elementwise comparison when it is defined on a collection; in fact, one
could imagine that some exotic sequence might legitimately define equality
in a way that has nothing to do with elementwise comparison. Put another
way, `==` returning `true` does not imply `elementsEqual` returning `true`,
and `elementsEqual` returning `true` does not imply `==` returning `true`.
This applies equally to ordered collections and is independent of the
question of how to model unordered collections.
b) You keep writing that some Foo is really some Bar, but those are really
just names. What would be the harm if Swift's `Set` indeed simply models an
ordered set without random-access manipulation?
I’ll have to mull this over to see if I can come up with a coherent and
(more) specific requirement for what makes an Iterable a Sequence, since
clearly “documented” isn’t enough. Perhaps something along the lines that
any two Sequences that compare equal must iterate the same.[…]
Apple documentation calls this one of the "order-dependent" methods. It is
surely acceptable for a type that conforms to an order-dependent protocol
to have methods that are order-dependent; they do, however, have to be
clearly order-dependent to avoid confusion on unordered types.I’m not clear on what you’re trying to get across here. It seems you’re
saying unordered types shouldn’t have order-dependent methods, which is
exactly what I’ve been arguing.
No, I'm saying, essentially, that there are no truly unordered types in
Swift; `Set` and `Dictionary` lead double lives modeling unordered
collections on the one hand and ordered collections on the other. The
order-dependent methods can continue to exist; they just need to be clearly
named so that users know when they're using an instance of `Set` in the
manner of an unordered collection and when they're using an instance of
`Set` in the manner of an ordered collection.
[...]
Then there are all the methods that imply a specific order of iteration.
If the “sequence” is unordered, who knows what you’ll get? It is incredibly
easy for an engineer to write a method that implicitly relies on a passed
sequence being intrinsically ordered and another engineer to pass it an
unordered “sequence.” The first engineer could neglect to document the
dependency, or even not notice it; or the second engineer could just fail
to read the documentation thoroughly enough. There is currently no way for
the compiler to enforce passing only an object that is (or at least claims
to be) intrinsically ordered.It is also incredibly easy for such an engineer to use `for...in` instead
to accomplish the same task, generic over ordered and unordered sequences
whatever you name such distinguished protocols. I think your beef really
still boils down to Set being compatible with `for...in` at all, as Jon
acknowledges.Not providing ordered functions for unordered collections makes the
developers think about what they actually need. If any object will do, they
can use for…in, .makeIterator().next(), or an `anyObject()` we provide as a
convenience. If they actually need the first from some specific order, it’s
a reminder they need to sort the objects first to get the right one.
The whole point of protocol hierarchies is to enable useful generic
algorithms. Here, the purpose of having a protocol that unites both ordered
and unordered collections is to permit the writing of generic algorithms
that operate on both; a user would want the first item from an ordered
collection or an arbitrary item (but the same one on multiple passes) from
an unordered collection. The name for that is currently `first`. Brent
demonstrated a trivial one-line example of such a use.
That’s particularly useful for functions that actually need an ordered
sequence; using OrderedSequence instead of Iterable (just as placeholders)
would be a firm reminder not to pass in an unordered collection.[…]
As I said, you're welcome to tackle the protocol hierarchy, but I really
doubt it's within the realm of realistic endpoints for Swift 5. I'm just
trying to propose a narrowly targeted pragmatic solution to one specific
limited harm that might be deliverable by the next point release. As a
great man once said, Swift is a pragmatic language.If you want a pragmatic solution, fix the bug in functionality, don’t try
and rename the method to something obscure to cover it up.
What I'm arguing is that there *is no bug in functionality*, only a naming
problem. It is true that the current protocol hierarchy would not be my
preferred design, but that's a matter of taste in terms of, again, where to
draw the line between too much modeling or not enough. But that's not
tantamount to a *bug*.
If you want to limit the harm, override `equalObjects` on unordered
sequences to use `==` (very strongly preferred), or always `false` (less
desirable, but at least consistent)[…]
The Swift stdlib deliberately eschews modeling everything in protocol
hierarchies with the highest level of granularity. There's some fudging,
deliberately, to find a happy medium between obtuse and approachable,
between too many/too specialized and not enough. For example, I pushed for
protocols such as `Field` and `Ring` at the top of the numeric hierarchy,
which might allow complex number types to slot into the hierarchy more
sensibly, for example. But we have a compromise protocol `Numeric` which
doesn't quite have the same guarantees but is much more approachable.
Notice that we also don't break down numeric protocols into `Addable`,
`Subtractable`, etc.; we also have that fudge factor built into
`Equatable`, as I mentioned.Eh, one or two corner cases on a protocol is probably fine. What’s not
fine is over half (Sequence) or almost all (Collection) the methods not
being applicable. There is a very clear gap there. We don’t need to fix
everything, but this is something that can and should be addressed.
This would be based on the premise that an instance of `Set` has no
intrinsic order; I disagree for the reasons above.
On Sun, Oct 15, 2017 at 2:32 PM, Kevin Nattinger <swift@nattinger.net> wrote:
What's your basis for saying that `elementsEqual` requires orders of
iteration that "convey a meaning"? It merely answers the question of
whether iterating over `a` is substitutable for iterating over `b`, a
question applicable to instances of any type which offers iterated access.
On Sun, Oct 15, 2017 at 2:39 PM, Kevin Nattinger <swift@nattinger.net> wrote:
[…]
Swift's Sequence protocol does not require the order of iteration to
"convey any meaning"; it doesn't even require it to be deterministic.And that’s EXACTLY why none of the functions on Sequence should rely on
the order conveying meaning. `ElementsEqual` (for example) DOES rely on
the order of iteration conveying a meaning not required by the protocol,
and renaming it `lexicographicallyEquals` does not change that fact. Either
Sequence needs to require a meaningful order or `elementsEqual` should be
moved to a protocol that does.
Something like that. Whatever we do, there will be a tradeoff between speed, correctness, and ergonomics.
My suggestion trades speed for correctness, and provides a way to recover speed through additional typing (which is slightly less ergonomic).
We could do something like you suggest. I don’t think the method would need to be underscored… the ordering pass could just be a method on the protocol which defines it as unordered. Then we could provide a special conformance for things where order really matters based on adherence to that protocol. That might be an acceptable tradeoff. It would give us speed at the cost of having the correct implementation being less ergonomic and more error prone (you have to remember to check that it is unordered and call the ordering method when it mattered).
I’d still be a bit worried that people would make incorrect generic algorithms based on expecting an order from unordered things, but at least it would be possible for them check and handle it correctly. I think I could get behind that tradeoff/compromise, given where we are in the swift process and Swift's obsession with speed (though I still slightly prefer the safer default). At least the standard library would handle all the things correctly, and that is what will affect the majority of programmers.
Thanks,
Jon
On Oct 14, 2017, at 10:48 PM, Xiaodi Wu <xiaodi.wu@gmail.com> wrote:
That ordering can be arbitrary, but it shouldn’t leak internal representation such that the method used to create identical things affects the outcome of generic methods because of differences in internal representation.
It would be better to say that the iteration order is well-defined. That will almost always mean documented, and usually predictable though obviously e.g. RNGs and iterating in random order will not be predictable by design.
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.
I think you’re talking about Sequence here, I’ve lost track of your nonsense by now. Yes, the current Swift protocol named Sequence allows unordered types. You seem to keep asserting that but not actually addressing my argument, which is that allowing Sequences to be unordered with the current API is undesired and actively harmful, and should therefore be changed.
What is harmful about it?
After thinking about it, I think the harmful bit is that unordered sequences are leaking internal representation (In your example, this is causing people to be surprised when two sets with identical elements are generating different sequences/orderings based on how they were created). You are correct when you say that this problem is even true for for-in.
I would not say it is a problem. Rather, by definition, iteration involves retrieving one element after another; if you're allowed to do that with Set, then the elements of a Set are observably ordered in some way. Since it's not an OrderedSet--i.e., order doesn't matter--then the only sensible conclusion is that the order of elements obtained in a for...in loop must be arbitrary. If you think this is harmful, then you must believe that one should be prohibited from iterating over an instance of Set. Otherwise, Set is inescapably a Sequence by the Swift definition of Sequence. All extension methods on Sequence like drop(while:) are really just conveniences for common things that you can do with iterated access; to my mind, they're essentially just alternative ways of spelling various for...in loops.
I think an argument could be made that you shouldn’t be able to iterate over a set without first defining an ordering on it (even if that ordering is somewhat arbitrary). Maybe we have something like a “Sequenc(e)able” protocol which defines things which can be turned into a sequence when combined with some sort of ordering. One possible ordering could be the internal representation (At least in that case we are calling it out specifically). If I had to say “setA.arbitraryOrder.elementsEqual(setB.arbitraryOrder)” I would definitely be less surprised when it returns false even though setA == setB.
Well, that's a totally different direction, then; you're arguing that `Set` and `Dictionary` should not conform to `Sequence` altogether. That's fine (it's also a direction that some of us explored off-list a while ago), but at this point in Swift's evolution, realistically, it's not within the realm of possible changes.
I am actually suggesting something slightly different. Basically, Set and Dictionary’s conformance to Collection would have a different implementation. They would conform to another protocol declaring that they are unordered. That protocol would fill in part of the conformance to sequence/collection using a default ordering, which is mostly arbitrary, but guaranteed to produce the same ordering for the same list of elements (even across collection types). This would be safer, but a tiny bit slower than what we have now (We could also potentially develop a way for collections like set to amortize the cost). For those who need to recover speed, the new protocol would also define a property which quickly returns a sequence/iterator using the internal ordering (I arbitrarily called it .arbitraryOrder).
I believe it would not be source breaking.
That is indeed something slightly different.
In an ideal world--and my initial understanding of what you were suggesting--Set and Dictionary would each have a member like `collection`, which would expose the underlying data as a `SetCollection` or `DictionaryCollection` that in turn would conform to `Collection`; meanwhile, Set and Dictionary themselves would not offer methods such as `prefix`, or indexing by subscript, which are not compatible with being unordered. For those who want a particular ordering, there'd be something like `collection(ordered areInIncreasingOrder: (T, T) -> Bool) -> {Set|Dictionary}Collection`.
What you suggest here instead would be minimally source-breaking. However, I'm unsure of where these guarantees provide benefit to justify the performance cost. Certainly not for `first` or `dropFirst(_:)`, which still yields an arbitrary result which doesn't make sense for something _unordered_. We *could* have an underscored customization point named something like `_customOrderingPass` that is only invoked from `elementsEqual` or other such methods to pre-rearrange the internal ordering of unordered collections in some deterministic way before comparison. Is that what you have in mind?
[…]
* 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.I’m not trying to bikeshed the name either, The underlying issue is that
(what is currently) Sequence actually encompasses two separate
functionalities, and those functionalities need to be separated with their
separate semantic requirements documented. “Sequence: Iterable,”
“OrderedSequence: Sequence,” “SpongeBob: ForLoopable,” the names are 100%
irrelevant at this point; what’s important is that one is not necessarily
ordered and the other guarantees an order.What are the "two separate functionalities”?
Iteration, with convenience methods that don’t imply or rely on an order
that may not be there; and convenience methods applicable to sequences that
do have an intrinsic order.Sets, as a mathematical concept, have no intrinsic order. However,
instances of `Set`, which can be iterated over, *do* have at least one
order which can be said to be intrinsic in the following sense: as long as
iteration is possible, no API design can prevent that order from being
observed and associated with the instance. Put another way, if you can use
an instance of a type in a for...in loop, intrinsic to that functionality
is a publicly visible order.I disagree. Sets are value types, therefore two instances of `Set` are
equal if they contain the same elements. An intrinsic order should
therefore only depend on the elements contained and should be the same for
two instances of `Set` which are equal.
This is not the case, though, as you can easily check in a playground by
looking at Set([1,2,3,4,5,6]) and Set([6,5,4,3,2,1]) which represent the
same value and are equal but do *not* have the same order.All the extension methods on Sequence are ways of spelling things that
you can write in a few lines of code using a `for...in` loop; they're in
the stdlib to allow a more functional style which some prefer. If you
accept that a type should support iteration with a `for...in` loop, then
what is your basis for claiming that these extension methods are "separate
functionalities”?Just because you *can* express something in code doesn’t mean you should,
or that it’s correct. It is objectively false to say a Set has a first or
last object, because the objects therein have no order. You can take a
random object from the set and call it “first”, but that doesn’t make that
a correct definition of Set.first. A Set has no order, a specific iteration
has an “order” only in the sense that all and only the objects in the set
have to come out one at a time, but that doesn’t mean the Set itself has an
order, specifically a first or last object.Since Set conforms to Collection, it is guaranteed that if one element of
an instance of Set comes out first one time, it'll come out first every
time from that instance. If it helps, think of Swift's Set as modeling
(imperfectly, as all models must) both a mathematical set and a multi-pass
sequence, just as Swift's Int models both an integer and a sequence of bits.You’re a fan of the principal of least surprise. Tell me, which would be
less surprising: Set.dropFirst() actually drops a random element, or Set
doesn’t have a dropFirst()? And if you think dropFirst() removing an
element at random is not surprising, please explain why.I think Set.dropFirst removing the first element that I observe on
iteration is the least surprising answer, because Swift tells me that the
stdlib Set models a set but that it is also a sequence.The latter is exactly the problem Kevin did point out. A Set is an
Iterable (in the sense that I can iterate over its elements with the order
being a meaningless random side effect) but it is *not* a Sequence (in the
sense that the order conveys any meaning).
Swift's Sequence protocol does not require the order of iteration to
"convey any meaning"; it doesn't even require it to be deterministic.
On Sun, Oct 15, 2017 at 14:14 Thorsten Seitz <tseitz42@icloud.com> wrote:
Am 15.10.2017 um 10:38 schrieb Xiaodi Wu via swift-evolution < > swift-evolution@swift.org>:
On Sun, Oct 15, 2017 at 2:29 AM, Kevin Nattinger <swift@nattinger.net> > wrote:On Oct 14, 2017, at 7:54 PM, Xiaodi Wu <xiaodi.wu@gmail.com> wrote:
On Sat, Oct 14, 2017 at 6:17 PM, Kevin Nattinger <swift@nattinger.net> >> wrote:
-Thorsten
[…]
* 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.Is `first` mutating? No. Should it be? No! `first` and `last` are a peek
at the state of the object.You're right, `first` should not be mutating; that's actually an
important design consideration, as Ole pointed out, and it's not actually
available on `Sequence` for that reason. However, `first { _ in true }` is
available and is potentially mutating, as are all methods on Sequence by
design.Is `elementsEqual` (or *shudder* lexicographicallyEqual) reflexive? IMO
it clearly should be. Especially with the “lexicographically” part—from
everything I can find, a lexicographical ordering is by definition
reflexive. Do you have a citation for the idea that lexicographical
equality can legitimately be non-reflexive?Clearly (tautologically?), such a function should be reflexive for any
argument ordered with respect to itself. However, if there is no
lexicographical comparison possible, then a thing cannot compare
lexicographically equal to anything, even itself.And that’s PRECISELY why lexicographicallyEqual does not make sense to
apply to unordered sets. There is no lexicographical comparison possible,
so why do you keep insisting they should have a method that falsely claims
to lexicographically compare them?I agree! It doesn't make sense if no comparison is possible! But Swift
tells me that a `Set` is a `Sequence`!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.> IMO that’s a bug in the implementation; lexicographical equality is
reflexive, period.> Presumably the `elementsEqual` method contains something along these
lines (take from SequenceAlgorithms.swift.gyb):var iter1 = self.makeIterator()
var iter2 = other.makeIterator()> By creating two iterators, you’re mutating while iterating. Turns out
there’s even a warning against this in Sequence.swift:/// Using Multiple Iterators
/// ========================
///
/// Whenever you use multiple iterators (or `for`-`in` loops) over a
single
/// sequence, be sure you know that the specific sequence supports
repeated
/// iteration, either because you know its concrete type or because the
/// sequence is also constrained to the `Collection` protocol.
///
/// Obtain each separate iterator from separate calls to the sequence's
/// `makeIterator()` method rather than by copying. Copying an iterator is
/// safe, but advancing one copy of an iterator by calling its `next()`
method
/// may invalidate other copies of that iterator. `for`-`in` loops are
safe in
/// this regard.*> The default implementation of elementsEqual is therefore unsafe* because
it has the potential for using an invalidated iterator.You are misunderstanding the warning in the second paragraph here. The
implementation (not a default implementation, unless I'm mistaken, as it
cannot be overridden)makes each iterator using separate calls to `makeIterator()`, just as the
documentation tells you to do. Calling next() on one iterator does not
invalidate the other iterator, because the second is not a copy of the
first.Indeed, I misread that comment.
That said, is there a well-defined behavior when iterating a one-shot
sequence with two iterators?
(It *is* a default implementation, btw)Not sure about that; I don't see a protocol requirement, in which case it
can only be shadowed in a concrete type but it can't be overridden. How to
accommodate single-pass sequences is an interesting question. Off the top
of my head, an iterator would have to be or wrap a reference type.You are, however, right that calling `rng.elementsEqual(rng)` is not
advised. It isn't unsafe; it's just not useful. That said, calling
`array.elementsEqual(array)` is equally safe and equally useless, and the
uselessness of such a reflexive comparison is neither here nor there.Funny how you complain about my code being useless and yet you insist
below, "If it's not providing you with utility, then don't use it.”
Regardless, you’re wrong to dismiss this case. `foo.elementsEqual(foo)`
on its own makes little sense, sure, but you could easily find yourself in
a method comparing two iterators you obtained from elsewhere, and
occasionally they happen to be the identical object. Allowing an iterator
to return `false` for .elementsEqual on itself is unexpected and dangerous.You will always have to account for this possibility, because Swift's
`Equatable` explicitly allows "special values" to be not equal to
themselves. This is, at least in part, in order to accommodate the IEEE
decree that NaN != NaN:let x = [Double.nan] x.elementsEqual(x) // falseChanging this behavior is way beyond the scope of this thread (and has
been the topic of hours (actually, weeks and weeks) of fun on this list
previously).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.> Ordered, yes, but it’s only admittedly poor wording that suggests
multi-pass, and I don’t think anything there suggests finite.If a Sequence is "guaranteed to iterate the same every time," then surely
it must be multi-pass; what's the alternative?Not sure if you just missed the very next sentence or are actively
ignoring it just to be argumentative. I already acknowledged that that
phrase didn’t convey the meaning I intended, and a Sequence is not and
should not be required to be multi-pass.I entirely misunderstood your next sentence as asserting that being
multi-pass makes the iteration order well-defined.It would be better to say that the iteration order is well-defined. That
will almost always mean documented, and usually predictable though
obviously e.g. RNGs and iterating in random order will not be predictable
by design.Wouldn't it then suffice to document, say, that a set's iteration order
is the insertion order?
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.I think you’re talking about Sequence here, I’ve lost track of your
nonsense by now. Yes, the current Swift protocol named Sequence allows
unordered types. You seem to keep asserting that but not actually
addressing my argument, which is *that allowing Sequences to be
unordered with the current API is undesired and actively harmful, and
should* *therefore** be changed*.What is harmful about it?
Well, for one, the issue you raised this thread about—two sets that are
`==` could return either true or false for `elementsEqual`, depending on
how they arrived at their current state. That’s not acceptable, and the
problem isn’t with the name of the method.Apple documentation calls this one of the "order-dependent" methods. It is
surely acceptable for a type that conforms to an order-dependent protocol
to have methods that are order-dependent; they do, however, have to be
clearly order-dependent to avoid confusion on unordered types.Then there are all the methods that imply a specific order of iteration.
If the “sequence” is unordered, who knows what you’ll get? It is incredibly
easy for an engineer to write a method that implicitly relies on a passed
sequence being intrinsically ordered and another engineer to pass it an
unordered “sequence.” The first engineer could neglect to document the
dependency, or even not notice it; or the second engineer could just fail
to read the documentation thoroughly enough. There is currently no way for
the compiler to enforce passing only an object that is (or at least claims
to be) intrinsically ordered.It is also incredibly easy for such an engineer to use `for...in` instead
to accomplish the same task, generic over ordered and unordered sequences
whatever you name such distinguished protocols. I think your beef really
still boils down to Set being compatible with `for...in` at all, as Jon
acknowledges.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.It is “meaningful” in the sense that it can technically be programmed.
The actual results are meaningless beyond returning or dropping a random*
element.*: Don’t nitpick the word “random”, you know exactly what I mean. It’s
just shorter and no less clear than “technically more-or-less deterministic
but not documented, not generally predictable, and probably but not
necessarily consistent from one call to the next."I fail to see the issue here. If it's not providing you with utility,
then don't use it.I have no problem with functions I don’t use provided they are
well-defined and reasonably accurately named. Functions requiring an order
on unordered collections don’t pass that bar.As I said, you're welcome to tackle the protocol hierarchy, but I really
doubt it's within the realm of realistic endpoints for Swift 5. I'm just
trying to propose a narrowly targeted pragmatic solution to one specific
limited harm that might be deliverable by the next point release. As a
great man once said, Swift is a pragmatic language.Since Collections do guarantee multi-pass iteration, Brent's example of
`set.dropFirst().reduce(set.first!, ...)` provides just one instance where
an unordered Collection can profitably make use of `first`. Permitting
generic algorithms that can operate on either arrays or sets, for example,
is the desired effect of having such a protocol; a generic algorithm that
takes a Collection can ask for the first element, and in the case of an
unordered Collection, an arbitrary element will do just fine.The generic algorithms should be on a protocol that specifies everything
they require. If one can work on anything you can iterate over, put it on
Iterable. If another requires the objects to be ordered, put it on
Sequence. Need to express that an algorithm requires a multi-pass sequence?
Make a MultiPassSequence protocol and put the algorithm on an extension
containing that requirement. Use protocols to express requirements, as they
were designed for. Don’t just tack a bunch of methods onto a protocol that
isn’t sufficient to describe their requirements and say, “oh, by the way,
only use this method if your implementation meets these conditions…"The benefits are likely outweighed by the costs of such an approach taken
to completion, because there are many axes to differentiate. The protocol
hierarchy for collections is already daunting, leading to monstrosities
such as `MutableRangeReplaceableRandomAccessSlice`. It stretches the bounds
of sensibility to have a
`LazyUnorderedInfiniteMultiPassMutableRangeReplaceableRandomAccessSlice`.The Swift stdlib deliberately eschews modeling everything in protocol
hierarchies with the highest level of granularity. There's some fudging,
deliberately, to find a happy medium between obtuse and approachable,
between too many/too specialized and not enough. For example, I pushed for
protocols such as `Field` and `Ring` at the top of the numeric hierarchy,
which might allow complex number types to slot into the hierarchy more
sensibly, for example. But we have a compromise protocol `Numeric` which
doesn't quite have the same guarantees but is much more approachable.
Notice that we also don't break down numeric protocols into `Addable`,
`Subtractable`, etc.; we also have that fudge factor built into
`Equatable`, as I mentioned.`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.No, no, no! What I want to call “Iterable” is specified below. It is
about HALF of what’s currently in Sequence—the half that has to do with
iterating, whence the name.
What I want to call Sequence is precisely what Swift now calls
Sequence—the methods that are in Iterable by virtue of adopting Iterable,
PLUS some methods that only make sense on iterable groups of objects where
the iteration order is well-defined.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.Apparently “collection" was a bad choice of word. What I clearly meant
was not the current Swift Collection protocol, but rather an unordered
assemblage of objects. UnorderedCollection, perhaps, or if that’s still
going to cause issues, try UnorderedAssemblage. What `first` and `last`
really mean in an UnorderedAssemblage is give me some object from the
assembled objects, I don’t care which one. For which it’s much more clear
to have an `anyObject()` as on NSSet; as another user has pointed out,
`assemblage.makeIterator().next()` works just as well. (I just checked, and
that’s actually how `first` is implemented. But it’s on Collection, which
is guaranteed to be multipass,)Again, the point of having a protocol-based design is to allow useful
_generic_ algorithms to be written; that `first` and `last` would be
equivalent to an arbitrary element in the case that a collection is
unordered is not at all an argument against these types conforming to
`Collection`; if anything, it's an argument for it.If a protocol demands the first object, you should give it the first
object. If you don’t have a first object, maybe you shouldn’t conform to
the protocol. If the protocol really just needs any old object, call it
`anyObject`.Sure, but we *do* have a first element; it just happens to be the first
that is obtainable on iteration. That you could make a good case for any
other element to be first doesn't mean that this one isn't a perfectly
cromulent first.Just as `Sequence.underestimatedCount` is equivalent to `Collection.count`
for types that conform to `Collection`, or the instance
`BinaryInteger.bitWidth` is equivalent to a static `bitWidth` for types
that conform to `FixedWidthInteger`.I don’t see how those are relevant, they all mean what they claim to,
unlike Set.first/dropFirst/etc.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
[…]
* 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.
I’m not trying to bikeshed the name either, The underlying issue is that (what is currently) Sequence actually encompasses two separate functionalities, and those functionalities need to be separated with their separate semantic requirements documented. “Sequence: Iterable,” “OrderedSequence: Sequence,” “SpongeBob: ForLoopable,” the names are 100% irrelevant at this point; what’s important is that one is not necessarily ordered and the other guarantees an order.
What are the "two separate functionalities”?
Iteration, with convenience methods that don’t imply or rely on an order that may not be there; and convenience methods applicable to sequences that do have an intrinsic order.
Sets, as a mathematical concept, have no intrinsic order. However, instances of `Set`, which can be iterated over, *do* have at least one order which can be said to be intrinsic in the following sense: as long as iteration is possible, no API design can prevent that order from being observed and associated with the instance. Put another way, if you can use an instance of a type in a for...in loop, intrinsic to that functionality is a publicly visible order.
I disagree. Sets are value types, therefore two instances of `Set` are equal if they contain the same elements. An intrinsic order should therefore only depend on the elements contained and should be the same for two instances of `Set` which are equal.
This is not the case, though, as you can easily check in a playground by looking at Set([1,2,3,4,5,6]) and Set([6,5,4,3,2,1]) which represent the same value and are equal but do *not* have the same order.All the extension methods on Sequence are ways of spelling things that you can write in a few lines of code using a `for...in` loop; they're in the stdlib to allow a more functional style which some prefer. If you accept that a type should support iteration with a `for...in` loop, then what is your basis for claiming that these extension methods are "separate functionalities”?
Just because you *can* express something in code doesn’t mean you should, or that it’s correct. It is objectively false to say a Set has a first or last object, because the objects therein have no order. You can take a random object from the set and call it “first”, but that doesn’t make that a correct definition of Set.first. A Set has no order, a specific iteration has an “order” only in the sense that all and only the objects in the set have to come out one at a time, but that doesn’t mean the Set itself has an order, specifically a first or last object.
Since Set conforms to Collection, it is guaranteed that if one element of an instance of Set comes out first one time, it'll come out first every time from that instance. If it helps, think of Swift's Set as modeling (imperfectly, as all models must) both a mathematical set and a multi-pass sequence, just as Swift's Int models both an integer and a sequence of bits.
You’re a fan of the principal of least surprise. Tell me, which would be less surprising: Set.dropFirst() actually drops a random element, or Set doesn’t have a dropFirst()? And if you think dropFirst() removing an element at random is not surprising, please explain why.
I think Set.dropFirst removing the first element that I observe on iteration is the least surprising answer, because Swift tells me that the stdlib Set models a set but that it is also a sequence.
The latter is exactly the problem Kevin did point out. A Set is an Iterable (in the sense that I can iterate over its elements with the order being a meaningless random side effect) but it is *not* a Sequence (in the sense that the order conveys any meaning).
Swift's Sequence protocol does not require the order of iteration to "convey any meaning"; it doesn't even require it to be deterministic.
Exactly. This is what makes methods like `first(where:)` meaningless which is why separating Sequence into Iterable and Sequence makes sense.
-Thorsten
Am 15.10.2017 um 21:22 schrieb Xiaodi Wu <xiaodi.wu@gmail.com>:
On Sun, Oct 15, 2017 at 14:14 Thorsten Seitz <tseitz42@icloud.com> wrote:Am 15.10.2017 um 10:38 schrieb Xiaodi Wu via swift-evolution <swift-evolution@swift.org>:
On Sun, Oct 15, 2017 at 2:29 AM, Kevin Nattinger <swift@nattinger.net> wrote:
On Oct 14, 2017, at 7:54 PM, Xiaodi Wu <xiaodi.wu@gmail.com> wrote:
On Sat, Oct 14, 2017 at 6:17 PM, Kevin Nattinger <swift@nattinger.net> wrote:
-Thorsten
[…]
* 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.
Is `first` mutating? No. Should it be? No! `first` and `last` are a peek at the state of the object.
You're right, `first` should not be mutating; that's actually an important design consideration, as Ole pointed out, and it's not actually available on `Sequence` for that reason. However, `first { _ in true }` is available and is potentially mutating, as are all methods on Sequence by design.
Is `elementsEqual` (or *shudder* lexicographicallyEqual) reflexive? IMO it clearly should be. Especially with the “lexicographically” part—from everything I can find, a lexicographical ordering is by definition reflexive. Do you have a citation for the idea that lexicographical equality can legitimately be non-reflexive?
Clearly (tautologically?), such a function should be reflexive for any argument ordered with respect to itself. However, if there is no lexicographical comparison possible, then a thing cannot compare lexicographically equal to anything, even itself.
And that’s PRECISELY why lexicographicallyEqual does not make sense to apply to unordered sets. There is no lexicographical comparison possible, so why do you keep insisting they should have a method that falsely claims to lexicographically compare them?
I agree! It doesn't make sense if no comparison is possible! But Swift tells me that a `Set` is a `Sequence`!
A random number generator fulfills all the semantic requirements of conforming to `SpongeBob`, and in fact I do just that in NumericAnnex. `first` gives a different value every time, and a randomly generated `SpongeBob` would unsurprisingly compare lexicographically not equal to itself.
> IMO that’s a bug in the implementation; lexicographical equality is reflexive, period.
> Presumably the `elementsEqual` method contains something along these lines (take from SequenceAlgorithms.swift.gyb):
var iter1 = self.makeIterator()
var iter2 = other.makeIterator()> By creating two iterators, you’re mutating while iterating. Turns out there’s even a warning against this in Sequence.swift:
/// Using Multiple Iterators
/// ========================
///
/// Whenever you use multiple iterators (or `for`-`in` loops) over a single
/// sequence, be sure you know that the specific sequence supports repeated
/// iteration, either because you know its concrete type or because the
/// sequence is also constrained to the `Collection` protocol.
///
/// Obtain each separate iterator from separate calls to the sequence's
/// `makeIterator()` method rather than by copying. Copying an iterator is
/// safe, but advancing one copy of an iterator by calling its `next()` method
/// may invalidate other copies of that iterator. `for`-`in` loops are safe in
/// this regard.> The default implementation of elementsEqual is therefore unsafe because it has the potential for using an invalidated iterator.
You are misunderstanding the warning in the second paragraph here. The implementation (not a default implementation, unless I'm mistaken, as it cannot be overridden)
makes each iterator using separate calls to `makeIterator()`, just as the documentation tells you to do. Calling next() on one iterator does not invalidate the other iterator, because the second is not a copy of the first.
Indeed, I misread that comment.
That said, is there a well-defined behavior when iterating a one-shot sequence with two iterators?
(It *is* a default implementation, btw)Not sure about that; I don't see a protocol requirement, in which case it can only be shadowed in a concrete type but it can't be overridden. How to accommodate single-pass sequences is an interesting question. Off the top of my head, an iterator would have to be or wrap a reference type.
You are, however, right that calling `rng.elementsEqual(rng)` is not advised. It isn't unsafe; it's just not useful. That said, calling `array.elementsEqual(array)` is equally safe and equally useless, and the uselessness of such a reflexive comparison is neither here nor there.
Funny how you complain about my code being useless and yet you insist below, "If it's not providing you with utility, then don't use it.”
Regardless, you’re wrong to dismiss this case. `foo.elementsEqual(foo)` on its own makes little sense, sure, but you could easily find yourself in a method comparing two iterators you obtained from elsewhere, and occasionally they happen to be the identical object. Allowing an iterator to return `false` for .elementsEqual on itself is unexpected and dangerous.You will always have to account for this possibility, because Swift's `Equatable` explicitly allows "special values" to be not equal to themselves. This is, at least in part, in order to accommodate the IEEE decree that NaN != NaN:
let x = [Double.nan] x.elementsEqual(x) // falseChanging this behavior is way beyond the scope of this thread (and has been the topic of hours (actually, weeks and weeks) of fun on this list previously).
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.
> Ordered, yes, but it’s only admittedly poor wording that suggests multi-pass, and I don’t think anything there suggests finite.
If a Sequence is "guaranteed to iterate the same every time," then surely it must be multi-pass; what's the alternative?
Not sure if you just missed the very next sentence or are actively ignoring it just to be argumentative. I already acknowledged that that phrase didn’t convey the meaning I intended, and a Sequence is not and should not be required to be multi-pass.
I entirely misunderstood your next sentence as asserting that being multi-pass makes the iteration order well-defined.
It would be better to say that the iteration order is well-defined. That will almost always mean documented, and usually predictable though obviously e.g. RNGs and iterating in random order will not be predictable by design.
Wouldn't it then suffice to document, say, that a set's iteration order is the insertion order?
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.
I think you’re talking about Sequence here, I’ve lost track of your nonsense by now. Yes, the current Swift protocol named Sequence allows unordered types. You seem to keep asserting that but not actually addressing my argument, which is that allowing Sequences to be unordered with the current API is undesired and actively harmful, and should therefore be changed.
What is harmful about it?
Well, for one, the issue you raised this thread about—two sets that are `==` could return either true or false for `elementsEqual`, depending on how they arrived at their current state. That’s not acceptable, and the problem isn’t with the name of the method.
Apple documentation calls this one of the "order-dependent" methods. It is surely acceptable for a type that conforms to an order-dependent protocol to have methods that are order-dependent; they do, however, have to be clearly order-dependent to avoid confusion on unordered types.
Then there are all the methods that imply a specific order of iteration. If the “sequence” is unordered, who knows what you’ll get? It is incredibly easy for an engineer to write a method that implicitly relies on a passed sequence being intrinsically ordered and another engineer to pass it an unordered “sequence.” The first engineer could neglect to document the dependency, or even not notice it; or the second engineer could just fail to read the documentation thoroughly enough. There is currently no way for the compiler to enforce passing only an object that is (or at least claims to be) intrinsically ordered.
It is also incredibly easy for such an engineer to use `for...in` instead to accomplish the same task, generic over ordered and unordered sequences whatever you name such distinguished protocols. I think your beef really still boils down to Set being compatible with `for...in` at all, as Jon acknowledges.
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.It is “meaningful” in the sense that it can technically be programmed. The actual results are meaningless beyond returning or dropping a random* element.
*: Don’t nitpick the word “random”, you know exactly what I mean. It’s just shorter and no less clear than “technically more-or-less deterministic but not documented, not generally predictable, and probably but not necessarily consistent from one call to the next."
I fail to see the issue here. If it's not providing you with utility, then don't use it.
I have no problem with functions I don’t use provided they are well-defined and reasonably accurately named. Functions requiring an order on unordered collections don’t pass that bar.
As I said, you're welcome to tackle the protocol hierarchy, but I really doubt it's within the realm of realistic endpoints for Swift 5. I'm just trying to propose a narrowly targeted pragmatic solution to one specific limited harm that might be deliverable by the next point release. As a great man once said, Swift is a pragmatic language.
Since Collections do guarantee multi-pass iteration, Brent's example of `set.dropFirst().reduce(set.first!, ...)` provides just one instance where an unordered Collection can profitably make use of `first`. Permitting generic algorithms that can operate on either arrays or sets, for example, is the desired effect of having such a protocol; a generic algorithm that takes a Collection can ask for the first element, and in the case of an unordered Collection, an arbitrary element will do just fine.
The generic algorithms should be on a protocol that specifies everything they require. If one can work on anything you can iterate over, put it on Iterable. If another requires the objects to be ordered, put it on Sequence. Need to express that an algorithm requires a multi-pass sequence? Make a MultiPassSequence protocol and put the algorithm on an extension containing that requirement. Use protocols to express requirements, as they were designed for. Don’t just tack a bunch of methods onto a protocol that isn’t sufficient to describe their requirements and say, “oh, by the way, only use this method if your implementation meets these conditions…"
The benefits are likely outweighed by the costs of such an approach taken to completion, because there are many axes to differentiate. The protocol hierarchy for collections is already daunting, leading to monstrosities such as `MutableRangeReplaceableRandomAccessSlice`. It stretches the bounds of sensibility to have a `LazyUnorderedInfiniteMultiPassMutableRangeReplaceableRandomAccessSlice`.
The Swift stdlib deliberately eschews modeling everything in protocol hierarchies with the highest level of granularity. There's some fudging, deliberately, to find a happy medium between obtuse and approachable, between too many/too specialized and not enough. For example, I pushed for protocols such as `Field` and `Ring` at the top of the numeric hierarchy, which might allow complex number types to slot into the hierarchy more sensibly, for example. But we have a compromise protocol `Numeric` which doesn't quite have the same guarantees but is much more approachable. Notice that we also don't break down numeric protocols into `Addable`, `Subtractable`, etc.; we also have that fudge factor built into `Equatable`, as I mentioned.
`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.
No, no, no! What I want to call “Iterable” is specified below. It is about HALF of what’s currently in Sequence—the half that has to do with iterating, whence the name.
What I want to call Sequence is precisely what Swift now calls Sequence—the methods that are in Iterable by virtue of adopting Iterable, PLUS some methods that only make sense on iterable groups of objects where the iteration order is well-defined.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.
Apparently “collection" was a bad choice of word. What I clearly meant was not the current Swift Collection protocol, but rather an unordered assemblage of objects. UnorderedCollection, perhaps, or if that’s still going to cause issues, try UnorderedAssemblage. What `first` and `last` really mean in an UnorderedAssemblage is give me some object from the assembled objects, I don’t care which one. For which it’s much more clear to have an `anyObject()` as on NSSet; as another user has pointed out, `assemblage.makeIterator().next()` works just as well. (I just checked, and that’s actually how `first` is implemented. But it’s on Collection, which is guaranteed to be multipass,)
Again, the point of having a protocol-based design is to allow useful _generic_ algorithms to be written; that `first` and `last` would be equivalent to an arbitrary element in the case that a collection is unordered is not at all an argument against these types conforming to `Collection`; if anything, it's an argument for it.
If a protocol demands the first object, you should give it the first object. If you don’t have a first object, maybe you shouldn’t conform to the protocol. If the protocol really just needs any old object, call it `anyObject`.
Sure, but we *do* have a first element; it just happens to be the first that is obtainable on iteration. That you could make a good case for any other element to be first doesn't mean that this one isn't a perfectly cromulent first.
Just as `Sequence.underestimatedCount` is equivalent to `Collection.count` for types that conform to `Collection`, or the instance `BinaryInteger.bitWidth` is equivalent to a static `bitWidth` for types that conform to `FixedWidthInteger`.
I don’t see how those are relevant, they all mean what they claim to, unlike Set.first/dropFirst/etc.
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
As Set has no intrinsic order of elements just imagine it was implemented to have each iterator created on it to iterate in a random order. This would satisfy the Sequence protocol (or rather its Iterable part hich should be split off) and clearly show that the order is meaningless for Sets.
-Thorsten
Am 16.10.2017 um 00:46 schrieb Xiaodi Wu <xiaodi.wu@gmail.com>:
On Sun, Oct 15, 2017 at 2:39 PM, Kevin Nattinger <swift@nattinger.net> wrote:
[…]
Swift's Sequence protocol does not require the order of iteration to "convey any meaning"; it doesn't even require it to be deterministic.And that’s EXACTLY why none of the functions on Sequence should rely on the order conveying meaning. `ElementsEqual` (for example) DOES rely on the order of iteration conveying a meaning not required by the protocol, and renaming it `lexicographicallyEquals` does not change that fact. Either Sequence needs to require a meaningful order or `elementsEqual` should be moved to a protocol that does.
What's your basis for saying that `elementsEqual` requires orders of iteration that "convey a meaning"? It merely answers the question of whether iterating over `a` is substitutable for iterating over `b`, a question applicable to instances of any type which offers iterated access.
Is the order of elements returned from Set/Dictionary guaranteed not to change based on implementation? For instance, the elements of a dictionary may shift around as I add items, and they may be different in different runs of a program.
If we document/say that Set will always return elements in the order they were added, then it may prevent us from using a more efficient implementation of Sets in a future version of Swift.
Just to check what we are saying. I am saying that we can’t really build generic algorithms on something which is undefined (because we are leaking implementation details, and depending on private implementation details leads to problems). You are saying that the leaking of implementation details is a feature, not a bug… and that we should just document them and consider them fixed ABI?
Thanks,
Jon
On Oct 15, 2017, at 3:41 PM, Xiaodi Wu via swift-evolution <swift-evolution@swift.org> wrote:
I’ll have to mull this over to see if I can come up with a coherent and (more) specific requirement for what makes an Iterable a Sequence, since clearly “documented” isn’t enough. Perhaps something along the lines that any two Sequences that compare equal must iterate the same.
[…]
Apple documentation calls this one of the "order-dependent" methods. It is surely acceptable for a type that conforms to an order-dependent protocol to have methods that are order-dependent; they do, however, have to be clearly order-dependent to avoid confusion on unordered types.I’m not clear on what you’re trying to get across here. It seems you’re saying unordered types shouldn’t have order-dependent methods, which is exactly what I’ve been arguing.
No, I'm saying, essentially, that there are no truly unordered types in Swift; `Set` and `Dictionary` lead double lives modeling unordered collections on the one hand and ordered collections on the other. The order-dependent methods can continue to exist; they just need to be clearly named so that users know when they're using an instance of `Set` in the manner of an unordered collection and when they're using an instance of `Set` in the manner of an ordered collection.