[Draft] Rename Sequence.elementsEqual

[xwu (Xiaodi Wu)]

You’re welcome to bikeshed the entire API surface area of sequences and
collections, but you won’t be the first to explore this area. A number of
us looked into this area in the past few years and did not reach a
measurable improved result.

Sequences can be ordered or unordered, single-pass or multi-pass, finite or
infinite, lazy or eager. Not all the combinations of these attributes make
sense, but many do. For each combination, a different subset of the
sequence algorithms are “useful.” As an example, “last” is not great for an
infinite sequence. It’s possibly also not what you want for a single-pass
sequence.

Now, as to the problem discussed here. It’s an orthogonal problem to what
you are discussing because, whether or not you reorganize the protocols
entirely, there is still going to be confusion about how exactly
“elementsEqual” differs from “==“ even for an ordered sequence. The name is
clearly problematic in that respect. However, I would argue that the
behavior of the method isn’t “improper” and the behavior is not “badly
defined.”

···

On Fri, Oct 13, 2017 at 07:09 Benjamin G <benjamin.garrigues@gmail.com> wrote:

+1 on both points. As for your solutions, i see 1/ as the best solution.
Breaking source code that rely on badly defined, or improper behavior isn't
"breaking". You don't break something that's already half broken.
As an app developer relying on swift on my day to day job and making a
living of it, i want to emphasis this: I really don't mind if a language
version change is making me look more carefully on some parts of my code
that i probably had overlooked.
Sure i may pester a bit when the code doesn't compile, but it sure is
better than discovering the weird behavior of a badly defined protocol
hierarchy in customer support.

On Fri, Oct 13, 2017 at 6:57 AM, Kevin Nattinger via swift-evolution < > swift-evolution@swift.org> wrote:

–∞

1. I strongly object to the proposed name. It doesn't make it more clear
to me what the method does, and is misleading at best. Among other issues,
"lexicographical" is defined as alphabet order, and (1) this method applies
to objects that are not Strings, and (2) this method's behavior isn't any
more well-defined for Strings, so that name is even more of a lie than the
original.

2. This is really just a symptom of a bigger problem. The fact that two
Sets can compare equal and yet return different results for that method
(among too many others) is logically inconsistent and points to a much
deeper issue with Set and Sequence. It is probably about 3 releases too
late to get this straightened out properly, but I'll outline the real issue
in case someone has an idea for fixing it.

*The root of the problem is that Set conforms to Sequence, but Sequence
doesn't require a well-defined order.* Since Set doesn't have a
well-defined order, a significant portion of its interface is unspecified.
The methods are implemented because they have to be, but they doesn't have
well-defined or necessarily consistent results.

A sequence is, by definition, ordered. That is reflected in the fact that
over half the methods in the main Sequence definition* make no sense and
are not well-defined unless there is a well-defined order to the sequence
itself. What does it even mean to `dropFirst()` in a Set? The fact that two
objects that compare equal can give different
results for a 100% deterministic function is illogical, nonsensical, and
dangerous.

* 7/12 by my count, ignoring `_*` funcs but including the `var`

The current contents of Sequence can be cleanly divided into two groups;
those that return SubSequence imply a specific ordering, and the
rest do not.

I think those should be/should have been two separate protocols:

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)
}

(The comments, of course, would be more sensible types once the ideas can
actually be expressed in Swift)

Then unordered collections (Set and Dictionary) would just conform to
Iterable and not Sequence, so ALL the methods on those classes would make
logical sense and have well-defined behavior; no change would be
needed for ordered collections.

Now, the practical matter. If this were Swift 1->2 or 2->3, I doubt there
would be a significant issue with actually making this change.
Unfortunately, we're well beyond that and making a change this
deep is an enormous deal. So I see two ways forward.

1. We could go ahead and make this separation. Although it's a
potentially large breaking change, I would argue that because the methods
are ill-defined anyway, the breakage is justified and a net benefit.

2. We could try and think of a way to make the distinction between
ordered and unordered "sequences" in a less-breaking manner. Unfortunately,
I don't have a good suggestion for this, but if anyone has ideas, I'm all
ears. Or eyes, as the case may be.

On Oct 12, 2017, at 4:24 PM, Xiaodi Wu via swift-evolution < >> swift-evolution@swift.org> wrote:

Rename Sequence.elementsEqual

   - Proposal: SE-NNNN
   <https://gist.github.com/xwu/NNNN-rename-elements-equal.md&gt;
   - Authors: Xiaodi Wu <https://github.com/xwu&gt;
   - Review Manager: TBD
   - Status: *Awaiting review*

<Rename Sequence.elementsEqual · GitHub;
Introduction

The current behavior of Sequence.elementsEqual is potentially confusing
to users given its name. Having surveyed the alternative solutions to this
problem, it is proposed that the method be renamed to
Sequence.lexicographicallyEquals.
[...]

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

[benjamin.g]

Hi, i'm not following this mailing for a long enough time, so i'm sorry if
all this conversation already took place. It seems however pretty obvious
to me what "ordered" and "unordered" means, and , knowing that collections
have value semantics in swift, i would expect the regular "==" to take that
difference into account, without having to resort to special functions..
Same as i would expect a complex numbers struct to compare correctly the
real and complex components, a vector compare correctly its dimension
components, and a regular (unordered) set to work only in terms of unions,
intersections and membership. Mostly because it seems to me that it's
traditional mathematical definition of equality in those cases...

···

On Fri, Oct 13, 2017 at 3:52 PM, Xiaodi Wu <xiaodi.wu@gmail.com> wrote:

You’re welcome to bikeshed the entire API surface area of sequences and
collections, but you won’t be the first to explore this area. A number of
us looked into this area in the past few years and did not reach a
measurable improved result.

Sequences can be ordered or unordered, single-pass or multi-pass, finite
or infinite, lazy or eager. Not all the combinations of these attributes
make sense, but many do. For each combination, a different subset of the
sequence algorithms are “useful.” As an example, “last” is not great for an
infinite sequence. It’s possibly also not what you want for a single-pass
sequence.

Now, as to the problem discussed here. It’s an orthogonal problem to what
you are discussing because, whether or not you reorganize the protocols
entirely, there is still going to be confusion about how exactly
“elementsEqual” differs from “==“ even for an ordered sequence. The name is
clearly problematic in that respect. However, I would argue that the
behavior of the method isn’t “improper” and the behavior is not “badly
defined.”

On Fri, Oct 13, 2017 at 07:09 Benjamin G <benjamin.garrigues@gmail.com> > wrote:

+1 on both points. As for your solutions, i see 1/ as the best solution.
Breaking source code that rely on badly defined, or improper behavior isn't
"breaking". You don't break something that's already half broken.
As an app developer relying on swift on my day to day job and making a
living of it, i want to emphasis this: I really don't mind if a language
version change is making me look more carefully on some parts of my code
that i probably had overlooked.
Sure i may pester a bit when the code doesn't compile, but it sure is
better than discovering the weird behavior of a badly defined protocol
hierarchy in customer support.

On Fri, Oct 13, 2017 at 6:57 AM, Kevin Nattinger via swift-evolution < >> swift-evolution@swift.org> wrote:

–∞

1. I strongly object to the proposed name. It doesn't make it more clear
to me what the method does, and is misleading at best. Among other issues,
"lexicographical" is defined as alphabet order, and (1) this method applies
to objects that are not Strings, and (2) this method's behavior isn't any
more well-defined for Strings, so that name is even more of a lie than the
original.

2. This is really just a symptom of a bigger problem. The fact that two
Sets can compare equal and yet return different results for that method
(among too many others) is logically inconsistent and points to a much
deeper issue with Set and Sequence. It is probably about 3 releases too
late to get this straightened out properly, but I'll outline the real issue
in case someone has an idea for fixing it.

*The root of the problem is that Set conforms to Sequence, but Sequence
doesn't require a well-defined order.* Since Set doesn't have a
well-defined order, a significant portion of its interface is unspecified.
The methods are implemented because they have to be, but they doesn't have
well-defined or necessarily consistent results.

A sequence is, by definition, ordered. That is reflected in the fact
that over half the methods in the main Sequence definition* make no sense
and are not well-defined unless there is a well-defined order to the
sequence itself. What does it even mean to `dropFirst()` in a Set? The fact
that two objects that compare equal can give different results for a 100% deterministic
function is illogical, nonsensical, and dangerous.

* 7/12 by my count, ignoring `_*` funcs but including the `var`

The current contents of Sequence can be cleanly divided into two groups;
those that return SubSequence imply a specific ordering, and the
rest do not.

I think those should be/should have been two separate protocols:

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)
}

(The comments, of course, would be more sensible types once the ideas
can actually be expressed in Swift)

Then unordered collections (Set and Dictionary) would just conform to
Iterable and not Sequence, so ALL the methods on those classes would make
logical sense and have well-defined behavior; no change would be
needed for ordered collections.

Now, the practical matter. If this were Swift 1->2 or 2->3, I doubt
there would be a significant issue with actually making this change.
Unfortunately, we're well beyond that and making a change this
deep is an enormous deal. So I see two ways forward.

1. We could go ahead and make this separation. Although it's a
potentially large breaking change, I would argue that because the methods
are ill-defined anyway, the breakage is justified and a net benefit.

2. We could try and think of a way to make the distinction between
ordered and unordered "sequences" in a less-breaking manner. Unfortunately,
I don't have a good suggestion for this, but if anyone has ideas, I'm all
ears. Or eyes, as the case may be.

On Oct 12, 2017, at 4:24 PM, Xiaodi Wu via swift-evolution < >>> swift-evolution@swift.org> wrote:

Rename Sequence.elementsEqual

   - Proposal: SE-NNNN
   <https://gist.github.com/xwu/NNNN-rename-elements-equal.md&gt;
   - Authors: Xiaodi Wu <https://github.com/xwu&gt;
   - Review Manager: TBD
   - Status: *Awaiting review*

<Rename Sequence.elementsEqual · GitHub;
Introduction

The current behavior of Sequence.elementsEqual is potentially confusing
to users given its name. Having surveyed the alternative solutions to this
problem, it is proposed that the method be renamed to Sequence.
lexicographicallyEquals.
[...]

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

[xwu (Xiaodi Wu)]

It has been a while, but I believe a lexicographical ordering is basically
a mapping from a set to the natural numbers (which should, in effect,
provide a total ordering). The mapping itself can be arbitrary, but the
same set of things should never map to two different sequences (which just
happens to be the example given).

This tells me that “lexicographicallyPrecedes” is actually misnamed unless
it refers to something which has a defined totally ordering.

By defining lexicographical equivalence and precedence, a total order is
defined for the set of all sequences that have the same element type. That
is, defining lexicographical equivalence and precedence for sequences of
Foos imposes a total ordering over the set of all sequences of Foos. Notice
that `lexicographicallyPrecedes` refers to the singular sequence being
ordered with respect to other sequences, not to the elements of the
sequence.

If we are looking to rename elementsEqual (which I would expect to check if

···

On Fri, Oct 13, 2017 at 3:06 PM, Jonathan Hull <jhull@gbis.com> wrote:

the same elements are present regardless of ordering), I would recommend
*elementOrderingEqual* or something like that that references that the
answer will be affected by the internal representation/ordering of the
sequence.

Thanks,
Jon

On Oct 13, 2017, at 11:10 AM, Jarod Long via swift-evolution < > swift-evolution@swift.org> wrote:

The name that feels natural to me would be `sequentiallyEquals`. I don't
dispute that the term "lexicographical" is used correctly here, although at
least for me personally, it's not a word that I encounter frequently enough
to understand what this method would do without reading the documentation.
Like Kevin, if I were to guess what the method did without checking, I
would probably think that it compared lexicographically-sorted versions of
the collections.

But the consistency with `lexicographicallyPrecedes` is a pretty strong
argument, although `sequentiallyPrecedes` would also feel more natural to
me there, and my suspicion about the mentioned lack of evidence that the
method has been a pitfall for users is that it's not actually used often
enough out in the wild to have heard much about it. That's just a guess
though. This proposal is the first time I've learned of its existence.

In any case, my ideal version of this proposal would use
`sequentiallyEquals` and also rename `lexicographicallyPrecedes` to
`sequentiallyPrecedes`, but I still like the proposal overall as-is. Thanks
for bringing it forward!

Jarod

On Oct 12, 2017, 16:24 -0700, Xiaodi Wu via swift-evolution < > swift-evolution@swift.org>, wrote:

Rename Sequence.elementsEqual

   - Proposal: SE-NNNN
   <https://gist.github.com/xwu/NNNN-rename-elements-equal.md&gt;
   - Authors: Xiaodi Wu <https://github.com/xwu&gt;
   - Review Manager: TBD
   - Status: *Awaiting review*

<Rename Sequence.elementsEqual · GitHub;
Introduction

The current behavior of Sequence.elementsEqual is potentially confusing
to users given its name. Having surveyed the alternative solutions to this
problem, it is proposed that the method be renamed to Sequence.
lexicographicallyEquals.
<Rename Sequence.elementsEqual · GitHub;
Motivation

As outlined by Ole Begemann
<https://twitter.com/olebegemann/status/916291785185529857&gt;, use of
Sequence.elementsEqual(_:) can lead to surprising results if the
sequences compared are unordered:

var set1: Set<Int> = Set(1...5)var set2: Set<Int> = Set((1...5).reversed())

set1 == set2 // trueset1.elementsEqual(set2) // false

This result does reflect the *intended and documented* behavior of the
elementsEqual(_:) method, which performs a *lexicographical* elementwise
comparison. That is, the method first compares set1.first to set2.first,
then (if the two elements compare equal) compares the next element stored
internally in set1 to the next element stored internally in set2, and so
on.

In almost all circumstances where a set is compared to another set, or a
dictionary is compared to another dictionary, users should use == instead
of elementsEqual(_:).

<Rename Sequence.elementsEqual · GitHub
solution

The proposed solution is the result of an iterative process of reasoning,
presented here:

The first and most obvious solution is to remove the elementsEqual(_:)
method altogether in favor of ==. This prevents its misuse. However,
because elementsEqual(_:) is a generic method on Sequence, we can use it
to compare an instance of UnsafeBufferPointer<Int> to an instance of [Int].
This is a useful and non-redundant feature which would be eliminated if the
method is removed altogether.

A second solution <https://github.com/apple/swift/pull/12318&gt; is to
create overloads that forbid the use of the elementsEqual(_:) method
specifically in non-generic code. This would prevent misuse in non-generic
code; however, it would also forbid legitimate mixed-type comparisons in
non-generic code while failing to prevent misuse in generic code. The
solution also creates a difference in the behavior of generic and
non-generic code calling the same method, which is potentially confusing,
without solving the problem completely.

A third solution is to dramatically overhaul the protocol hierarchy for
Swift sequences and collections so that unordered collections no longer
have members such as first and elementsEqual(_:). However, this would be
a colossal and source-breaking undertaking, and it is unlikely to be
satisfactory in addressing all the axes of differences among sequence and
collection types:

   - Finite versus infinite
   - Single-pass versus multi-pass
   - Ordered versus unordered
   - Lazy versus eager
   - Forward/bidirectional/random-access

A fourth solution is proposed here. It is predicated on the following
observation:

*Another method similar to elementsEqual(_:) already exists on Sequence
named lexicographicallyPrecedes(_:). Like first, elementsEqual(_:),
drop(while:), and others, it relies on the internal order of elements in a
manner that is not completely suitable for an unordered collection.
However, like first and unlike elementsEqual(_:), this fact is called out
in the name of the method; unsurprisingly, like first and unlike
elementsEqual(_:), there is no evidence that lexicographicallyPrecedes(_:)
has been a pitfall for users.*

This observation suggests that a major reason for confusion over
elementsEqual(_:) stems from its name. So, *it is proposed that
elementsEqual(_:) should be renamed to lexicographicallyEquals(_:)*. The
function will remain somewhat of a poor fit for unordered collections, but
no more so than many other methods that cannot trivially be removed from
the API of unordered collections (as discussed above). The key is that,
with such a renaming, the behavior of this method will no longer be
confusing.

<Rename Sequence.elementsEqual · GitHub
design

extension Sequence where Element : Equatable {
  @available(*, deprecated, message: "Use '==' if possible to compare two sequences of the same type, or use 'lexicographicallyEquals' to compare two ordered sequences.")
  public func elementsEqual<Other : Sequence>(
    _ other: Other
  ) -> Bool where Other.Element == Element {
    return lexicographicallyEquals(other)
  }

  public func lexicographicallyEquals<Other : Sequence>(
    _ other: Other
  ) -> Bool where Other.Element == Element {
    // The body of this method is unchanged. var iter1 = self.makeIterator()
    var iter2 = other.makeIterator()
    while true {
      switch (iter1.next(), iter2.next()) {
      case let (e1?, e2?):
        if e1 != e2 { return false }
      case (_?, nil), (nil, _?):
        return false
      case (nil, nil):
        return true
      }
    }
  }
}

A parallel change will be made with respect to elementsEqual(_:by:); that
is, it will be deprecated in favor of lexicographicallyEquals(_:by:).

<Rename Sequence.elementsEqual · GitHub
compatibility

Existing code that uses elementsEqual will gain a deprecation warning.

<Rename Sequence.elementsEqual · GitHub
on ABI stability

None.

<Rename Sequence.elementsEqual · GitHub
on API resilience

This proposal adds new methods to the public API of Sequence and
conforming types.

<Rename Sequence.elementsEqual · GitHub
considered

It is to be noted that lexicographicallyPrecedes(_:by:) and
elementsEqual(_:by:) are essentially the same method, since both perform
a lexicographical comparison using a custom predicate. However, there is
not a good unifying name. (lexicographicallyCompares(to:by:) reads
poorly.) Moreover, the predicate supplied is intended to have very
different semantics, and maintaining two distinct methods may be a superior
fit with the typical user's mental model of the intended behavior and may
also be clearer to readers of the code. Therefore, this proposal does not
seek to unify the two methods; instead, elementsEqual(_:by:) will be
renamed lexicographicallyEquals(_:by:) as detailed above.
_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

[xwu (Xiaodi Wu)]

Fair enough suggestion as well.

···

On Fri, Oct 13, 2017 at 8:45 PM, Brent Royal-Gordon <brent@architechies.com> wrote:

> On Oct 12, 2017, at 9:57 PM, Kevin Nattinger via swift-evolution < > swift-evolution@swift.org> wrote:
>
> That is reflected in the fact that over half the methods in the main
Sequence definition* make no sense and are not well-defined unless there is
a well-defined order to the sequence itself. What does it even mean to
`dropFirst()` in a Set?

It means to skip the first element the set would normally have given you.
Which element this will be may be arbitrary, but this is still not useless:

    set.dropFirst().reduce(set.first!, …)

Even elementsEqual(_:) does tell you something potentially valuable:
Whether two instances will end up giving the same result when processed by
an ordering-sensitive algorithm.

We should change the name to something like orderEquals(_:), and maybe
change the lexicographicallyPrecedes(_:) method to something analogous like
orderPrecedes(_:), and then be done with it.

[knatt (Kevin Nattinger)]

You’re welcome to bikeshed the entire API surface area of sequences and collections, but you won’t be the first to explore this area. A number of us looked into this area in the past few years and did not reach a measurable improved result.

I don’t need or want to bikeshed the entire sequence and collection surface area, I just want to fix one clear and GLARING issue:

A Set is NOT a sequence.

Note that this goes for dictionaries and any other unordered “sequences" as well.

That was in an early draft of my original email, but I dropped it because I was afraid people would just stop reading and dismiss the idea out-of-hand without considering the problem or arguments. Apparently I should have at least put it at the bottom, so sorry if the root issue was unclear.

Sequences can be ordered or unordered,

You seem to be confusing the English word “sequence” with the (current) Swift protocol “Sequence." A sequence is, by definition, ordered. Not enforcing that in a protocol does not override the English language, and as this entire thread demonstrates, causes issues further on down the line.

We are discussing the Swift protocol `Sequence`. It really doesn't matter at all what the English word "sequence" means, and any difference between the English word and the Swift term is emphatically *not* the root cause of the issue. Here's why:

* A Swift `Sequence` is, to put it simplistically, a thing that can be iterated over in a `for...in` loop. If it would make you happy, for the rest of the discussion, let's suppose we called the protocol `ForLoopable` instead of `Sequence`.

ForLoopable is so ugly. Since we’re just iterating over the elements, how about, oh, say, `Iterable`? Hey, that looks familiar.

* `Set` should conform to `ForLoopable`. (This I state as a premise; if you disagree with the notion that we should be able to iterate over the elements of an instance of `Set` with a `for...in loop`, then it's clearly a whole other discussion and not a question of what the English word "sequence" means.)

Obviously, `Set: Iterable`. I don’t think I’ve said anything to suggest you shouldn’t be able to iterate over unordered collections.

* If a type `T` conforms to `ForLoopable` and an instance `t` of that type has at least one element, then *something* has to be the first element in a `for element in t { ... }` loop. Put another way, every instance of a type that conforms to `ForLoopable` must have at least one publicly observable order (although, intriguingly, I'm not sure it has to be a repeatable one). It is possible, therefore, to have a semantic answer to the question of which element is `first` or (if finite) `last`; one can also `drop(while:)`, etc., and perform lexicographical comparisons.

As a side effect of Swift being a procedural language each iteration happens to occur in some order, yes, but that order is meaningless and reflects nothing about the Set itself. In fact, I’d say that `first`, `last`, etc. are not even defined on the original Set per se, only on the specific order that a particular iteration resulted in. And that order is not necessarily predictable, nor necessarily stable, as you yourself said.

Consider an Iterable that gives a different order every time it’s iterated.
Should calling `.first` or `last` give a different object every time? That’s absurd.
Should an object lexicographically compare not equal to itself? Even more absurd.

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.
`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.

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 {…}

···

On Oct 13, 2017, at 8:28 PM, Xiaodi Wu <xiaodi.wu@gmail.com> wrote:
On Fri, Oct 13, 2017 at 12:03 PM, Kevin Nattinger <swift@nattinger.net <mailto:swift@nattinger.net>> wrote:

On Oct 13, 2017, at 6:52 AM, Xiaodi Wu <xiaodi.wu@gmail.com <mailto:xiaodi.wu@gmail.com>> wrote:

[Jon_Hull]

Because the mathematical term you talk about has conditions which must be met to be used/valid. Namely:

1) The “Alphabet” of elements must be totally ordered
2) The lexicographical comparison must be applied to ordered sequences of elements from that alphabet

Neither of those conditions are met for an unordered generic collection (e.g. a set of equatable, but not comparable elements).

The underlying issue here is that the “ordering” of the sequence coming out of a set/dictionary is undefined and may rely on internal implementation details. Building anything on top of that is problematic because the foundation is undefined. Lexicographical’s connotation of applying a total order only compounds that original issue, especially if the elements are strings or some other sequential data type.

Thanks,
Jon

···

On Oct 14, 2017, at 8:45 PM, Xiaodi Wu via swift-evolution <swift-evolution@swift.org> wrote:

On Sat, Oct 14, 2017 at 8:11 PM, Michael Ilseman <milseman@apple.com <mailto:milseman@apple.com>> wrote:
I think that “match” is a word to avoid for this, as this doesn’t have anything to do with pattern matching, fuzzy matching, etc., while “equals” is precisely the concept we’re using.

What about the name “sequentiallyEquals”? Highlight the fact that we’re talking about sequential ordering, i.e. whatever order the sequence provides, as opposed to first doing some lexicographical ordering of elements themselves.

var a: Set<Int> = [3, 1, 2]
a.sequentiallyEquals([1,2,3]) // result depends on application of equality in a (potentially-arbitrary) sequential ordering

Whereas I could see the following being more confusing:

var a: Set<Int> = [3, 1, 2]
a.lexicographicallyEquals([1,2,3]) // result depends on application of equality, but what meaning does “lexicographically” convey?

It’s not immediately clear to someone new to the API that “lexicographically” speaks to the nature of the sequence’s (potentially-arbitrary) order, irrespective of element. It could give the false impression that it speaks to some nature of the elements themselves, in this case Ints, which have an obvious lexicographical ordering. I don’t know how frequent that misconception would be in practice, but it does cause me to do a double-take in this contrived example.

I'm entirely puzzled that apparently large numbers of people believe lexicographical comparison, a term with a very specific mathematical definition and no colloquial use, to mean what it does not. I'd like to avoid inventing Swift-specific new terms for this particular concept which is not at all unique to Swift. The other plausible terms I can see with some other use might be "elementwise equals" or "entrywise equals" or "coordinatewise equals."

On Oct 14, 2017, at 1:04 PM, Benjamin G via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:

To answer more precisely this request (which remains valid no matter the protocol hierarchy). I propose

"matchesSequence" ( or simply "matches" or "match", whatever is more coherent with the naming guidelines).

So
var a: [Int] = [1,2,3]
a.matchesSequence([1,2,3]) returns true.

I first thought that the verb "matching" was too heavily associated to regular expressions, but i think that it's the correct equivalent for something as general as a sequence.

On Fri, Oct 13, 2017 at 1:24 AM, Xiaodi Wu via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:
Rename Sequence.elementsEqual

Proposal: SE-NNNN <https://gist.github.com/xwu/NNNN-rename-elements-equal.md&gt;
Authors: Xiaodi Wu <https://github.com/xwu&gt;
Review Manager: TBD
Status: Awaiting review
<Rename Sequence.elementsEqual · GitHub

The current behavior of Sequence.elementsEqual is potentially confusing to users given its name. Having surveyed the alternative solutions to this problem, it is proposed that the method be renamed to Sequence.lexicographicallyEquals.

<Rename Sequence.elementsEqual · GitHub

As outlined by Ole Begemann <https://twitter.com/olebegemann/status/916291785185529857&gt;, use of Sequence.elementsEqual(_:) can lead to surprising results if the sequences compared are unordered:

var set1: Set<Int> = Set(1...5)
var set2: Set<Int> = Set((1...5).reversed())

set1 == set2 // true
set1.elementsEqual(set2) // false
This result does reflect the intended and documented behavior of the elementsEqual(_:) method, which performs a lexicographical elementwise comparison. That is, the method first compares set1.first to set2.first, then (if the two elements compare equal) compares the next element stored internally in set1 to the next element stored internally in set2, and so on.

In almost all circumstances where a set is compared to another set, or a dictionary is compared to another dictionary, users should use == instead of elementsEqual(_:).

<Rename Sequence.elementsEqual · GitHub solution

The proposed solution is the result of an iterative process of reasoning, presented here:

The first and most obvious solution is to remove the elementsEqual(_:) method altogether in favor of ==. This prevents its misuse. However, because elementsEqual(_:) is a generic method on Sequence, we can use it to compare an instance of UnsafeBufferPointer<Int> to an instance of [Int]. This is a useful and non-redundant feature which would be eliminated if the method is removed altogether.

A second solution <https://github.com/apple/swift/pull/12318&gt; is to create overloads that forbid the use of the elementsEqual(_:) method specifically in non-generic code. This would prevent misuse in non-generic code; however, it would also forbid legitimate mixed-type comparisons in non-generic code while failing to prevent misuse in generic code. The solution also creates a difference in the behavior of generic and non-generic code calling the same method, which is potentially confusing, without solving the problem completely.

A third solution is to dramatically overhaul the protocol hierarchy for Swift sequences and collections so that unordered collections no longer have members such as first and elementsEqual(_:). However, this would be a colossal and source-breaking undertaking, and it is unlikely to be satisfactory in addressing all the axes of differences among sequence and collection types:

Finite versus infinite
Single-pass versus multi-pass
Ordered versus unordered
Lazy versus eager
Forward/bidirectional/random-access
A fourth solution is proposed here. It is predicated on the following observation:

Another method similar to elementsEqual(_:) already exists on Sequence named lexicographicallyPrecedes(_:). Like first, elementsEqual(_:), drop(while:), and others, it relies on the internal order of elements in a manner that is not completely suitable for an unordered collection. However, like first and unlike elementsEqual(_:), this fact is called out in the name of the method; unsurprisingly, like first and unlike elementsEqual(_:), there is no evidence that lexicographicallyPrecedes(_:) has been a pitfall for users.

This observation suggests that a major reason for confusion over elementsEqual(_:) stems from its name. So, it is proposed that elementsEqual(_:) should be renamed to lexicographicallyEquals(_:). The function will remain somewhat of a poor fit for unordered collections, but no more so than many other methods that cannot trivially be removed from the API of unordered collections (as discussed above). The key is that, with such a renaming, the behavior of this method will no longer be confusing.

<Rename Sequence.elementsEqual · GitHub design

extension Sequence where Element : Equatable {
  @available(*, deprecated, message: "Use '==' if possible to compare two sequences of the same type, or use 'lexicographicallyEquals' to compare two ordered sequences.")
  public func elementsEqual<Other : Sequence>(
    _ other: Other
  ) -> Bool where Other.Element == Element {
    return lexicographicallyEquals(other)
  }
  
  public func lexicographicallyEquals<Other : Sequence>(
    _ other: Other
  ) -> Bool where Other.Element == Element {
    // The body of this method is unchanged.
    var iter1 = self.makeIterator()
    var iter2 = other.makeIterator()
    while true {
      switch (iter1.next(), iter2.next()) {
      case let (e1?, e2?):
        if e1 != e2 { return false }
      case (_?, nil), (nil, _?):
        return false
      case (nil, nil):
        return true
      }
    }
  }
}
A parallel change will be made with respect to elementsEqual(_:by:); that is, it will be deprecated in favor of lexicographicallyEquals(_:by:).

<Rename Sequence.elementsEqual · GitHub compatibility

Existing code that uses elementsEqual will gain a deprecation warning.

<Rename Sequence.elementsEqual · GitHub on ABI stability

None.

<Rename Sequence.elementsEqual · GitHub on API resilience

This proposal adds new methods to the public API of Sequence and conforming types.

<Rename Sequence.elementsEqual · GitHub considered

It is to be noted that lexicographicallyPrecedes(_:by:) and elementsEqual(_:by:) are essentially the same method, since both perform a lexicographical comparison using a custom predicate. However, there is not a good unifying name. (lexicographicallyCompares(to:by:) reads poorly.) Moreover, the predicate supplied is intended to have very different semantics, and maintaining two distinct methods may be a superior fit with the typical user's mental model of the intended behavior and may also be clearer to readers of the code. Therefore, this proposal does not seek to unify the two methods; instead, elementsEqual(_:by:) will be renamed lexicographicallyEquals(_:by:) as detailed above.

_______________________________________________
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 <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

[xwu (Xiaodi Wu)]

Because the mathematical term you talk about has conditions which must be
met to be used/valid. Namely:

1) The “Alphabet” of elements must be totally ordered
2) The lexicographical comparison must be applied to ordered sequences of
elements from that alphabet

Neither of those conditions are met for an unordered generic collection
(e.g. a set of equatable, but not comparable elements).

This is diametrically the opposite claim that Michael just made. Here, you
argue that the confusion stems from the extension of the term to sequences
with elements that are equatable but not comparable because there *isn't* a
total ordering for the elements. Michael just said that the term is
confusing particularly with Ints *because* they have an obvious total
ordering (i.e., they are comparable). And in fact, the apparently common
misconception is that the function would instead sort the elements of each
sequence by that ordering, which is obviously inapplicable for equatable
but not comparable elements, and such a misconception is therefore
impossible in that scenario.

_The very first result on Google_ defines lexicographical comparison
unambiguously for C++:

Lexicographical comparison is a operation with the following properties:

   - Two ranges are compared element by element.
   - The first mismatching element defines which range is
   lexicographically *less* or *greater* than the other.
   - If one range is a prefix of another, the shorter range is
   lexicographically *less* than the other.
   - If two ranges have equivalent elements and are of the same length,
   then the ranges are lexicographically *equal*.
   - An empty range is lexicographically *less* than any non-empty range.
   - Two empty ranges are lexicographically *equal*.

The purpose behind choosing "lexicographicallyEquals" was that it is a

term that has an established meaning, easily googled, that describes the
algorithm exactly and unambiguously in two words. If you have seen this
term in use, you will know what the Swift method does. If you have not seen
this term, then even in the absence of Swift documentation, a single search
will lead you to the correct answer. I am simply in disbelief that
apparently many people will see a term with which they are unfamiliar,
assume it means something it does not, and use the function without
consulting the documentation or looking up the term.

The underlying issue here is that the “ordering” of the sequence coming out

of a set/dictionary is undefined and may rely on internal implementation
details. Building anything on top of that is problematic because the
foundation is undefined. Lexicographical’s connotation of applying a total
order only compounds that original issue, especially if the elements are
strings or some other sequential data type.

Right, and the purpose of this proposal is to give it such a name that it
is obvious that this function is probably not what you want in comparing
two concrete sets (much as it is obvious on first glance that `first` is
probably not useful when working with concrete sets), without going down
the road of attempting to rip out the established protocol hierarchy.

···

On Sat, Oct 14, 2017 at 11:25 PM, Jonathan Hull <jhull@gbis.com> wrote:

On Oct 14, 2017, at 8:45 PM, Xiaodi Wu via swift-evolution < > swift-evolution@swift.org> wrote:

On Sat, Oct 14, 2017 at 8:11 PM, Michael Ilseman <milseman@apple.com> > wrote:

I think that “match” is a word to avoid for this, as this doesn’t have
anything to do with pattern matching, fuzzy matching, etc., while “equals”
is precisely the concept we’re using.

What about the name “sequentiallyEquals”? Highlight the fact that we’re
talking about sequential ordering, i.e. whatever order the sequence
provides, as opposed to first doing some lexicographical ordering of
elements themselves.

var a: Set<Int> = [3, 1, 2]
a.sequentiallyEquals([1,2,3]) // result depends on application of
equality in a (potentially-arbitrary) sequential ordering

Whereas I could see the following being more confusing:

var a: Set<Int> = [3, 1, 2]
a.lexicographicallyEquals([1,2,3]) // result depends on application of
equality, but what meaning does “lexicographically” convey?

It’s not immediately clear to someone new to the API that
“lexicographically” speaks to the nature of the sequence’s
(potentially-arbitrary) order, irrespective of element. It could give the
false impression that it speaks to some nature of the elements themselves,
in this case Ints, which have an obvious lexicographical ordering. I don’t
know how frequent that misconception would be in practice, but it does
cause me to do a double-take in this contrived example.

I'm entirely puzzled that apparently large numbers of people believe
lexicographical comparison, a term with a very specific mathematical
definition and no colloquial use, to mean what it does not. I'd like to
avoid inventing Swift-specific new terms for this particular concept which
is not at all unique to Swift. The other plausible terms I can see with
some other use might be "elementwise equals" or "entrywise equals" or
"coordinatewise equals."

On Oct 14, 2017, at 1:04 PM, Benjamin G via swift-evolution < >> swift-evolution@swift.org> wrote:

To answer more precisely this request (which remains valid no matter the
protocol hierarchy). I propose

"matchesSequence" ( or simply "matches" or "match", whatever is more
coherent with the naming guidelines).

So
var a: [Int] = [1,2,3]
a.matchesSequence([1,2,3]) returns true.

I first thought that the verb "matching" was too heavily associated to
regular expressions, but i think that it's the correct equivalent for
something as general as a sequence.

On Fri, Oct 13, 2017 at 1:24 AM, Xiaodi Wu via swift-evolution < >> swift-evolution@swift.org> wrote:

Rename Sequence.elementsEqual

   - Proposal: SE-NNNN
   <https://gist.github.com/xwu/NNNN-rename-elements-equal.md&gt;
   - Authors: Xiaodi Wu <https://github.com/xwu&gt;
   - Review Manager: TBD
   - Status: *Awaiting review*

<Rename Sequence.elementsEqual · GitHub;
Introduction

The current behavior of Sequence.elementsEqual is potentially confusing
to users given its name. Having surveyed the alternative solutions to this
problem, it is proposed that the method be renamed to
Sequence.lexicographicallyEquals.
<Rename Sequence.elementsEqual · GitHub;
Motivation

As outlined by Ole Begemann
<https://twitter.com/olebegemann/status/916291785185529857&gt;, use of
Sequence.elementsEqual(_:) can lead to surprising results if the
sequences compared are unordered:

var set1: Set<Int> = Set(1...5)var set2: Set<Int> = Set((1...5).reversed())

set1 == set2 // trueset1.elementsEqual(set2) // false

This result does reflect the *intended and documented* behavior of the
elementsEqual(_:) method, which performs a *lexicographical*
elementwise comparison. That is, the method first compares set1.first
to set2.first, then (if the two elements compare equal) compares the
next element stored internally in set1 to the next element stored
internally in set2, and so on.

In almost all circumstances where a set is compared to another set, or a
dictionary is compared to another dictionary, users should use ==
instead of elementsEqual(_:).

<Rename Sequence.elementsEqual · GitHub
solution

The proposed solution is the result of an iterative process of
reasoning, presented here:

The first and most obvious solution is to remove the elementsEqual(_:)
method altogether in favor of ==. This prevents its misuse. However,
because elementsEqual(_:) is a generic method on Sequence, we can use
it to compare an instance of UnsafeBufferPointer<Int> to an instance of
[Int]. This is a useful and non-redundant feature which would be
eliminated if the method is removed altogether.

A second solution <https://github.com/apple/swift/pull/12318&gt; is to
create overloads that forbid the use of the elementsEqual(_:) method
specifically in non-generic code. This would prevent misuse in non-generic
code; however, it would also forbid legitimate mixed-type comparisons in
non-generic code while failing to prevent misuse in generic code. The
solution also creates a difference in the behavior of generic and
non-generic code calling the same method, which is potentially confusing,
without solving the problem completely.

A third solution is to dramatically overhaul the protocol hierarchy for
Swift sequences and collections so that unordered collections no longer
have members such as first and elementsEqual(_:). However, this would
be a colossal and source-breaking undertaking, and it is unlikely to be
satisfactory in addressing all the axes of differences among sequence and
collection types:

   - Finite versus infinite
   - Single-pass versus multi-pass
   - Ordered versus unordered
   - Lazy versus eager
   - Forward/bidirectional/random-access

A fourth solution is proposed here. It is predicated on the following
observation:

*Another method similar to elementsEqual(_:) already exists on Sequence
named lexicographicallyPrecedes(_:). Like first, elementsEqual(_:),
drop(while:), and others, it relies on the internal order of elements in a
manner that is not completely suitable for an unordered collection.
However, like first and unlike elementsEqual(_:), this fact is called out
in the name of the method; unsurprisingly, like first and unlike
elementsEqual(_:), there is no evidence that lexicographicallyPrecedes(_:)
has been a pitfall for users.*

This observation suggests that a major reason for confusion over
elementsEqual(_:) stems from its name. So, *it is proposed that
elementsEqual(_:) should be renamed to lexicographicallyEquals(_:)*.
The function will remain somewhat of a poor fit for unordered collections,
but no more so than many other methods that cannot trivially be removed
from the API of unordered collections (as discussed above). The key is
that, with such a renaming, the behavior of this method will no longer be
confusing.

<Rename Sequence.elementsEqual · GitHub
design

extension Sequence where Element : Equatable {
  @available(*, deprecated, message: "Use '==' if possible to compare two sequences of the same type, or use 'lexicographicallyEquals' to compare two ordered sequences.")
  public func elementsEqual<Other : Sequence>(
    _ other: Other
  ) -> Bool where Other.Element == Element {
    return lexicographicallyEquals(other)
  }

  public func lexicographicallyEquals<Other : Sequence>(
    _ other: Other
  ) -> Bool where Other.Element == Element {
    // The body of this method is unchanged. var iter1 = self.makeIterator()
    var iter2 = other.makeIterator()
    while true {
      switch (iter1.next(), iter2.next()) {
      case let (e1?, e2?):
        if e1 != e2 { return false }
      case (_?, nil), (nil, _?):
        return false
      case (nil, nil):
        return true
      }
    }
  }
}

A parallel change will be made with respect to elementsEqual(_:by:);
that is, it will be deprecated in favor of
lexicographicallyEquals(_:by:).

<Rename Sequence.elementsEqual · GitHub
compatibility

Existing code that uses elementsEqual will gain a deprecation warning.

<Rename Sequence.elementsEqual · GitHub
on ABI stability

None.

<Rename Sequence.elementsEqual · GitHub
on API resilience

This proposal adds new methods to the public API of Sequence and
conforming types.

<Rename Sequence.elementsEqual · GitHub
considered

It is to be noted that lexicographicallyPrecedes(_:by:) and
elementsEqual(_:by:) are essentially the same method, since both
perform a lexicographical comparison using a custom predicate. However,
there is not a good unifying name. (lexicographicallyCompares(to:by:)
reads poorly.) Moreover, the predicate supplied is intended to have very
different semantics, and maintaining two distinct methods may be a superior
fit with the typical user's mental model of the intended behavior and may
also be clearer to readers of the code. Therefore, this proposal does not
seek to unify the two methods; instead, elementsEqual(_:by:) will be
renamed lexicographicallyEquals(_:by:) as detailed above.

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

[benjamin.g]

>
> That is reflected in the fact that over half the methods in the main
Sequence definition* make no sense and are not well-defined unless there is
a well-defined order to the sequence itself. What does it even mean to
`dropFirst()` in a Set?

It means to skip the first element the set would normally have given you.
Which element this will be may be arbitrary, but this is still not useless:

    set.dropFirst().reduce(set.first!, …)

Do we have the guarantee that set.dropFirst() is going to return the same
element as set.first! ?

I don't understand how you can build generic algorithms over Sequence using
first() and last() that work if the protocol itself doesn't give any
guarantee about ordering.. Unless "first" and "last" both mean "any"...

···

On Sat, Oct 14, 2017 at 3:45 AM, Brent Royal-Gordon via swift-evolution < swift-evolution@swift.org> wrote:

> On Oct 12, 2017, at 9:57 PM, Kevin Nattinger via swift-evolution < > swift-evolution@swift.org> wrote:

Even elementsEqual(_:) does tell you something potentially valuable:
Whether two instances will end up giving the same result when processed by
an ordering-sensitive algorithm.

We should change the name to something like orderEquals(_:), and maybe
change the lexicographicallyPrecedes(_:) method to something analogous like
orderPrecedes(_:), and then be done with it.

--
Brent Royal-Gordon
Sent from my iPhone

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

[adamkemp]

Right, but if you do look it up you get a bunch of things talking about sorting words.

How about pairwiseEqual?

···

--
Adam Kemp

On Oct 13, 2017, at 5:17 AM, Xiaodi Wu <xiaodi.wu@gmail.com> wrote:

“Lexicographical comparison” is a pretty standard term, and easy to Google. We didn’t make it up for Swift :)

Since Swift names this protocol Sequence, something named “Sequence.sequenceEqual” cannot distinguish this method from ==.

On Fri, Oct 13, 2017 at 01:28 Adam Kemp <adam.kemp@apple.com> wrote:
I agree that the proposed name is a poor choice. If we just focus on the naming part, there is precedent in other languages for the name “sequenceEqual”. I think that name makes it a bit clearer that the result is whether the sequences match pair wise rather than whether they have the same elements irrespective of order. I don’t think it entirely solves the problem, but I like it a lot better than the proposed name.

--
Adam Kemp

On Oct 12, 2017, at 9:57 PM, Kevin Nattinger via swift-evolution <swift-evolution@swift.org> wrote:

–∞

1. I strongly object to the proposed name. It doesn't make it more clear to me what the method does, and is misleading at best. Among other issues, "lexicographical" is defined as alphabet order, and (1) this method applies to objects that are not Strings, and (2) this method's behavior isn't any more well-defined for Strings, so that name is even more of a lie than the original.

2. This is really just a symptom of a bigger problem. The fact that two Sets can compare equal and yet return different results for that method (among too many others) is logically inconsistent and points to a much deeper issue with Set and Sequence. It is probably about 3 releases too late to get this straightened out properly, but I'll outline the real issue in case someone has an idea for fixing it.

The root of the problem is that Set conforms to Sequence, but Sequence doesn't require a well-defined order. Since Set doesn't have a well-defined order, a significant portion of its interface is unspecified. The methods are implemented because they have to be, but they doesn't have well-defined or necessarily consistent results.

A sequence is, by definition, ordered. That is reflected in the fact that over half the methods in the main Sequence definition* make no sense and are not well-defined unless there is a well-defined order to the sequence itself. What does it even mean to `dropFirst()` in a Set? The fact that two objects that compare equal can give different results for a 100% deterministic function is illogical, nonsensical, and dangerous.

* 7/12 by my count, ignoring `_*` funcs but including the `var`

The current contents of Sequence can be cleanly divided into two groups; those that return SubSequence imply a specific ordering, and the rest do not.

I think those should be/should have been two separate protocols:

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)
}

(The comments, of course, would be more sensible types once the ideas can actually be expressed in Swift)

Then unordered collections (Set and Dictionary) would just conform to Iterable and not Sequence, so ALL the methods on those classes would make logical sense and have well-defined behavior; no change would be needed for ordered collections.

Now, the practical matter. If this were Swift 1->2 or 2->3, I doubt there would be a significant issue with actually making this change. Unfortunately, we're well beyond that and making a change this deep is an enormous deal. So I see two ways forward.

1. We could go ahead and make this separation. Although it's a potentially large breaking change, I would argue that because the methods are ill-defined anyway, the breakage is justified and a net benefit.

2. We could try and think of a way to make the distinction between ordered and unordered "sequences" in a less-breaking manner. Unfortunately, I don't have a good suggestion for this, but if anyone has ideas, I'm all ears. Or eyes, as the case may be.

On Oct 12, 2017, at 4:24 PM, Xiaodi Wu via swift-evolution <swift-evolution@swift.org> wrote:

Rename Sequence.elementsEqual

Proposal: SE-NNNN
Authors: Xiaodi Wu
Review Manager: TBD
Status: Awaiting review
Introduction

The current behavior of Sequence.elementsEqual is potentially confusing to users given its name. Having surveyed the alternative solutions to this problem, it is proposed that the method be renamed to Sequence.lexicographicallyEquals.

[...]

_______________________________________________

swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

[Michael_Ilseman]

–∞

1. I strongly object to the proposed name. It doesn't make it more clear to me what the method does, and is misleading at best. Among other issues, "lexicographical" is defined as alphabet order, and (1) this method applies to objects that are not Strings, and (2) this method's behavior isn't any more well-defined for Strings, so that name is even more of a lie than the original.

FWIW, in the context of String, "lexicographical ordering” does not imply human-written-language-alphabetical order at all, as there’s no universal alphabetical ordering for human language. I.e., such a concrete notion for Strings does not exist, not even theoretically. “Lexicographical” derives its meaning from the mathematical usage[1] which uses that term as well as “alphabet” without being restricted to human-written-language, in which it means some total ordering over a finite set.

[1] Lexicographic order - Wikipedia

I see, apologies for the mistake.

No worries, I think my comment came across too blunt. Sorry about that. I was trying to defend the word “lexicographical” which I think is a very useful word to have at our disposal :-)

Regardless of the specific type of ordering, lexicographicallyEquals says to me that the objects should be sorted into lexicographical order and compared. Precisely the opposite of the proposal.

Right, and thus cuts to the heart of what Xiaodi raised in the proposal’s third potential solution.

Quoted from the proposal:

A third solution is to dramatically overhaul the protocol hierarchy for Swift sequences and collections so that unordered collections no longer have members such as first and elementsEqual(_:). However, this would be a colossal and source-breaking undertaking, and it is unlikely to be satisfactory in addressing all the axes of differences among sequence and collection types:

Finite versus infinite
Single-pass versus multi-pass
Ordered versus unordered
Lazy versus eager
Forward/bidirectional/random-access

Is seems like you’re arguing we should attack the “Ordered versus unordered” dichotomy prior to any name change. Is that correct?

···

On Oct 13, 2017, at 10:12 AM, Kevin Nattinger <swift@nattinger.net> wrote:

On Oct 13, 2017, at 10:01 AM, Michael Ilseman <milseman@apple.com <mailto:milseman@apple.com>> wrote:

On Oct 12, 2017, at 9:57 PM, Kevin Nattinger via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:

2. This is really just a symptom of a bigger problem. The fact that two Sets can compare equal and yet return different results for that method (among too many others) is logically inconsistent and points to a much deeper issue with Set and Sequence. It is probably about 3 releases too late to get this straightened out properly, but I'll outline the real issue in case someone has an idea for fixing it.

The root of the problem is that Set conforms to Sequence, but Sequence doesn't require a well-defined order. Since Set doesn't have a well-defined order, a significant portion of its interface is unspecified. The methods are implemented because they have to be, but they doesn't have well-defined or necessarily consistent results.

A sequence is, by definition, ordered. That is reflected in the fact that over half the methods in the main Sequence definition* make no sense and are not well-defined unless there is a well-defined order to the sequence itself. What does it even mean to `dropFirst()` in a Set? The fact that two objects that compare equal can give different results for a 100% deterministic function is illogical, nonsensical, and dangerous.

* 7/12 by my count, ignoring `_*` funcs but including the `var`

The current contents of Sequence can be cleanly divided into two groups; those that return SubSequence imply a specific ordering, and the rest do not.

I think those should be/should have been two separate protocols:

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)
}

(The comments, of course, would be more sensible types once the ideas can actually be expressed in Swift)

Then unordered collections (Set and Dictionary) would just conform to Iterable and not Sequence, so ALL the methods on those classes would make logical sense and have well-defined behavior; no change would be needed for ordered collections.

Now, the practical matter. If this were Swift 1->2 or 2->3, I doubt there would be a significant issue with actually making this change. Unfortunately, we're well beyond that and making a change this deep is an enormous deal. So I see two ways forward.

1. We could go ahead and make this separation. Although it's a potentially large breaking change, I would argue that because the methods are ill-defined anyway, the breakage is justified and a net benefit.

2. We could try and think of a way to make the distinction between ordered and unordered "sequences" in a less-breaking manner. Unfortunately, I don't have a good suggestion for this, but if anyone has ideas, I'm all ears. Or eyes, as the case may be.

On Oct 12, 2017, at 4:24 PM, Xiaodi Wu via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:

Rename Sequence.elementsEqual

Proposal: SE-NNNN <https://gist.github.com/xwu/NNNN-rename-elements-equal.md&gt;
Authors: Xiaodi Wu <https://github.com/xwu&gt;
Review Manager: TBD
Status: Awaiting review
<Rename Sequence.elementsEqual · GitHub

The current behavior of Sequence.elementsEqual is potentially confusing to users given its name. Having surveyed the alternative solutions to this problem, it is proposed that the method be renamed to Sequence.lexicographicallyEquals.

[...]

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org <mailto:swift-evolution@swift.org>
https://lists.swift.org/mailman/listinfo/swift-evolution

[Jon_Hull]

I would also expect lexicographicallyEquals to sort the elements (or otherwise create/reference a total ordering) before checking for equality. I would be more surprised by the behavior of a function named this than elementsEqual.

Given the name, I would expect elementsEqual to return true if two sequences have the same elements, regardless of ordering (this would be a valuable function IMHO). I would expect lexicographicallyEquals to compare the elements in some lexicographical order defined for the type which overrides the internal ordering of the sequence.

Kevin is right… the real answer is that the actual intended function really shouldn’t exist on unordered sequences.

Thanks,
Jon

···

On Oct 13, 2017, at 10:12 AM, Kevin Nattinger via swift-evolution <swift-evolution@swift.org> wrote:

On Oct 13, 2017, at 10:01 AM, Michael Ilseman <milseman@apple.com <mailto:milseman@apple.com>> wrote:

On Oct 12, 2017, at 9:57 PM, Kevin Nattinger via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:

–∞

1. I strongly object to the proposed name. It doesn't make it more clear to me what the method does, and is misleading at best. Among other issues, "lexicographical" is defined as alphabet order, and (1) this method applies to objects that are not Strings, and (2) this method's behavior isn't any more well-defined for Strings, so that name is even more of a lie than the original.

FWIW, in the context of String, "lexicographical ordering” does not imply human-written-language-alphabetical order at all, as there’s no universal alphabetical ordering for human language. I.e., such a concrete notion for Strings does not exist, not even theoretically. “Lexicographical” derives its meaning from the mathematical usage[1] which uses that term as well as “alphabet” without being restricted to human-written-language, in which it means some total ordering over a finite set.

[1] Lexicographic order - Wikipedia

I see, apologies for the mistake.
Regardless of the specific type of ordering, lexicographicallyEquals says to me that the objects should be sorted into lexicographical order and compared. Precisely the opposite of the proposal.

2. This is really just a symptom of a bigger problem. The fact that two Sets can compare equal and yet return different results for that method (among too many others) is logically inconsistent and points to a much deeper issue with Set and Sequence. It is probably about 3 releases too late to get this straightened out properly, but I'll outline the real issue in case someone has an idea for fixing it.

The root of the problem is that Set conforms to Sequence, but Sequence doesn't require a well-defined order. Since Set doesn't have a well-defined order, a significant portion of its interface is unspecified. The methods are implemented because they have to be, but they doesn't have well-defined or necessarily consistent results.

A sequence is, by definition, ordered. That is reflected in the fact that over half the methods in the main Sequence definition* make no sense and are not well-defined unless there is a well-defined order to the sequence itself. What does it even mean to `dropFirst()` in a Set? The fact that two objects that compare equal can give different results for a 100% deterministic function is illogical, nonsensical, and dangerous.

* 7/12 by my count, ignoring `_*` funcs but including the `var`

The current contents of Sequence can be cleanly divided into two groups; those that return SubSequence imply a specific ordering, and the rest do not.

I think those should be/should have been two separate protocols:

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)
}

(The comments, of course, would be more sensible types once the ideas can actually be expressed in Swift)

Then unordered collections (Set and Dictionary) would just conform to Iterable and not Sequence, so ALL the methods on those classes would make logical sense and have well-defined behavior; no change would be needed for ordered collections.

Now, the practical matter. If this were Swift 1->2 or 2->3, I doubt there would be a significant issue with actually making this change. Unfortunately, we're well beyond that and making a change this deep is an enormous deal. So I see two ways forward.

1. We could go ahead and make this separation. Although it's a potentially large breaking change, I would argue that because the methods are ill-defined anyway, the breakage is justified and a net benefit.

2. We could try and think of a way to make the distinction between ordered and unordered "sequences" in a less-breaking manner. Unfortunately, I don't have a good suggestion for this, but if anyone has ideas, I'm all ears. Or eyes, as the case may be.

On Oct 12, 2017, at 4:24 PM, Xiaodi Wu via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:

Rename Sequence.elementsEqual

Proposal: SE-NNNN <https://gist.github.com/xwu/NNNN-rename-elements-equal.md&gt;
Authors: Xiaodi Wu <https://github.com/xwu&gt;
Review Manager: TBD
Status: Awaiting review
<Rename Sequence.elementsEqual · GitHub

The current behavior of Sequence.elementsEqual is potentially confusing to users given its name. Having surveyed the alternative solutions to this problem, it is proposed that the method be renamed to Sequence.lexicographicallyEquals.

[...]

_______________________________________________
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

[xwu (Xiaodi Wu)]

Right, but if you do look it up you get a bunch of things talking about
sorting words.

And that’s a perfect description of the behavior. It’s a lexicographical
comparison operation!

How about pairwiseEqual?

A lexicographical comparison compares not merely pairwise, but in order
from the first item onwards, and stops at the first unequal pair.
Proceeding in order is key information, while stopping early on false is a
nice-to-have. There’s already a word for this, and it’s “lexicographical.”
And the analogy is universally understood: everyone has used a dictionary
or index.

···

On Fri, Oct 13, 2017 at 09:02 Adam Kemp <adam.kemp@apple.com> wrote:

--
Adam Kemp

On Oct 13, 2017, at 5:17 AM, Xiaodi Wu <xiaodi.wu@gmail.com> wrote:

“Lexicographical comparison” is a pretty standard term, and easy to
Google. We didn’t make it up for Swift :)

Since Swift names this protocol Sequence, something named
“Sequence.sequenceEqual” cannot distinguish this method from ==.

On Fri, Oct 13, 2017 at 01:28 Adam Kemp <adam.kemp@apple.com> wrote:

I agree that the proposed name is a poor choice. If we just focus on the
naming part, there is precedent in other languages for the name
“sequenceEqual”. I think that name makes it a bit clearer that the result
is whether the sequences match pair wise rather than whether they have the
same elements irrespective of order. I don’t think it entirely solves the
problem, but I like it a lot better than the proposed name.

--
Adam Kemp

On Oct 12, 2017, at 9:57 PM, Kevin Nattinger via swift-evolution < >> swift-evolution@swift.org> wrote:

–∞

1. I strongly object to the proposed name. It doesn't make it more clear
to me what the method does, and is misleading at best. Among other issues,
"lexicographical" is defined as alphabet order, and (1) this method applies
to objects that are not Strings, and (2) this method's behavior isn't any
more well-defined for Strings, so that name is even more of a lie than the
original.

2. This is really just a symptom of a bigger problem. The fact that two
Sets can compare equal and yet return different results for that method
(among too many others) is logically inconsistent and points to a much
deeper issue with Set and Sequence. It is probably about 3 releases too
late to get this straightened out properly, but I'll outline the real issue
in case someone has an idea for fixing it.

*The root of the problem is that Set conforms to Sequence, but Sequence
doesn't require a well-defined order.* Since Set doesn't have a
well-defined order, a significant portion of its interface is unspecified.
The methods are implemented because they have to be, but they doesn't have
well-defined or necessarily consistent results.

A sequence is, by definition, ordered. That is reflected in the fact that
over half the methods in the main Sequence definition* make no sense and
are not well-defined unless there is a well-defined order to the sequence
itself. What does it even mean to `dropFirst()` in a Set? The fact that two
objects that compare equal can give different
results for a 100% deterministic function is illogical, nonsensical, and
dangerous.

* 7/12 by my count, ignoring `_*` funcs but including the `var`

The current contents of Sequence can be cleanly divided into two groups;
those that return SubSequence imply a specific ordering, and the
rest do not.

I think those should be/should have been two separate protocols:

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)
}

(The comments, of course, would be more sensible types once the ideas can
actually be expressed in Swift)

Then unordered collections (Set and Dictionary) would just conform to
Iterable and not Sequence, so ALL the methods on those classes would make
logical sense and have well-defined behavior; no change would be
needed for ordered collections.

Now, the practical matter. If this were Swift 1->2 or 2->3, I doubt there
would be a significant issue with actually making this change.
Unfortunately, we're well beyond that and making a change this
deep is an enormous deal. So I see two ways forward.

1. We could go ahead and make this separation. Although it's a
potentially large breaking change, I would argue that because the methods
are ill-defined anyway, the breakage is justified and a net benefit.

2. We could try and think of a way to make the distinction between
ordered and unordered "sequences" in a less-breaking manner. Unfortunately,
I don't have a good suggestion for this, but if anyone has ideas, I'm all
ears. Or eyes, as the case may be.

On Oct 12, 2017, at 4:24 PM, Xiaodi Wu via swift-evolution < >> swift-evolution@swift.org> wrote:

Rename Sequence.elementsEqual

   - Proposal: SE-NNNN
   <https://gist.github.com/xwu/NNNN-rename-elements-equal.md&gt;
   - Authors: Xiaodi Wu <https://github.com/xwu&gt;
   - Review Manager: TBD
   - Status: *Awaiting review*

<Rename Sequence.elementsEqual · GitHub;
Introduction

The current behavior of Sequence.elementsEqual is potentially confusing
to users given its name. Having surveyed the alternative solutions to this
problem, it is proposed that the method be renamed to
Sequence.lexicographicallyEquals.
[...]

_______________________________________________

swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

[benjamin.g]

Ok, sorry for that answer that was really too quick. It seems that i really
didn't answer the rational for the "elementsEqual" function in the first
place which seems to be related to comparing sequences of different types,
so just ignore my last comment.

I do however wants to reiterate my encouragement to core language
developers to not get frightened to make deep source breaking changes if it
helps developers stay away from undefined behaviors (such as preventing
people from using first() or elementsEquals() on sets).

···

On Fri, Oct 13, 2017 at 7:08 PM, Benjamin G via swift-evolution < swift-evolution@swift.org> wrote:

Hi, i'm not following this mailing for a long enough time, so i'm sorry if
all this conversation already took place. It seems however pretty obvious
to me what "ordered" and "unordered" means, and , knowing that collections
have value semantics in swift, i would expect the regular "==" to take that
difference into account, without having to resort to special functions..
Same as i would expect a complex numbers struct to compare correctly the
real and complex components, a vector compare correctly its dimension
components, and a regular (unordered) set to work only in terms of unions,
intersections and membership. Mostly because it seems to me that it's
traditional mathematical definition of equality in those cases...

On Fri, Oct 13, 2017 at 3:52 PM, Xiaodi Wu <xiaodi.wu@gmail.com> wrote:

You’re welcome to bikeshed the entire API surface area of sequences and
collections, but you won’t be the first to explore this area. A number of
us looked into this area in the past few years and did not reach a
measurable improved result.

Sequences can be ordered or unordered, single-pass or multi-pass, finite
or infinite, lazy or eager. Not all the combinations of these attributes
make sense, but many do. For each combination, a different subset of the
sequence algorithms are “useful.” As an example, “last” is not great for an
infinite sequence. It’s possibly also not what you want for a single-pass
sequence.

Now, as to the problem discussed here. It’s an orthogonal problem to what
you are discussing because, whether or not you reorganize the protocols
entirely, there is still going to be confusion about how exactly
“elementsEqual” differs from “==“ even for an ordered sequence. The name is
clearly problematic in that respect. However, I would argue that the
behavior of the method isn’t “improper” and the behavior is not “badly
defined.”

On Fri, Oct 13, 2017 at 07:09 Benjamin G <benjamin.garrigues@gmail.com> >> wrote:

+1 on both points. As for your solutions, i see 1/ as the best solution.
Breaking source code that rely on badly defined, or improper behavior isn't
"breaking". You don't break something that's already half broken.
As an app developer relying on swift on my day to day job and making a
living of it, i want to emphasis this: I really don't mind if a language
version change is making me look more carefully on some parts of my code
that i probably had overlooked.
Sure i may pester a bit when the code doesn't compile, but it sure is
better than discovering the weird behavior of a badly defined protocol
hierarchy in customer support.

On Fri, Oct 13, 2017 at 6:57 AM, Kevin Nattinger via swift-evolution < >>> swift-evolution@swift.org> wrote:

–∞

1. I strongly object to the proposed name. It doesn't make it more
clear to me what the method does, and is misleading at best. Among other
issues, "lexicographical" is defined as alphabet order, and (1) this method
applies to objects that are not Strings, and (2) this method's behavior
isn't any more well-defined for Strings, so that name is even more of a lie
than the original.

2. This is really just a symptom of a bigger problem. The fact that two
Sets can compare equal and yet return different results for that method
(among too many others) is logically inconsistent and points to a much
deeper issue with Set and Sequence. It is probably about 3 releases too
late to get this straightened out properly, but I'll outline the real issue
in case someone has an idea for fixing it.

*The root of the problem is that Set conforms to Sequence, but Sequence
doesn't require a well-defined order.* Since Set doesn't have a
well-defined order, a significant portion of its interface is unspecified.
The methods are implemented because they have to be, but they doesn't have
well-defined or necessarily consistent results.

A sequence is, by definition, ordered. That is reflected in the fact
that over half the methods in the main Sequence definition* make no sense
and are not well-defined unless there is a well-defined order to the
sequence itself. What does it even mean to `dropFirst()` in a Set? The fact
that two objects that compare equal can give different
results for a 100% deterministic function is illogical, nonsensical,
and dangerous.

* 7/12 by my count, ignoring `_*` funcs but including the `var`

The current contents of Sequence can be cleanly divided into two
groups; those that return SubSequence imply a specific ordering, and the
rest do not.

I think those should be/should have been two separate protocols:

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)
}

(The comments, of course, would be more sensible types once the ideas
can actually be expressed in Swift)

Then unordered collections (Set and Dictionary) would just conform to
Iterable and not Sequence, so ALL the methods on those classes would make
logical sense and have well-defined behavior; no change would be
needed for ordered collections.

Now, the practical matter. If this were Swift 1->2 or 2->3, I doubt
there would be a significant issue with actually making this change.
Unfortunately, we're well beyond that and making a change this
deep is an enormous deal. So I see two ways forward.

1. We could go ahead and make this separation. Although it's a
potentially large breaking change, I would argue that because the methods
are ill-defined anyway, the breakage is justified and a net benefit.

2. We could try and think of a way to make the distinction between
ordered and unordered "sequences" in a less-breaking manner. Unfortunately,
I don't have a good suggestion for this, but if anyone has ideas, I'm all
ears. Or eyes, as the case may be.

On Oct 12, 2017, at 4:24 PM, Xiaodi Wu via swift-evolution < >>>> swift-evolution@swift.org> wrote:

Rename Sequence.elementsEqual

   - Proposal: SE-NNNN
   <https://gist.github.com/xwu/NNNN-rename-elements-equal.md&gt;
   - Authors: Xiaodi Wu <https://github.com/xwu&gt;
   - Review Manager: TBD
   - Status: *Awaiting review*

<Rename Sequence.elementsEqual · GitHub;
Introduction

The current behavior of Sequence.elementsEqual is potentially
confusing to users given its name. Having surveyed the alternative
solutions to this problem, it is proposed that the method be renamed to
Sequence.lexicographicallyEquals.
[...]

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

[xwu (Xiaodi Wu)]

–∞

1. I strongly object to the proposed name. It doesn't make it more clear
to me what the method does, and is misleading at best. Among other issues,
"lexicographical" is defined as alphabet order, and (1) this method applies
to objects that are not Strings, and (2) this method's behavior isn't any
more well-defined for Strings, so that name is even more of a lie than the
original.

FWIW, in the context of String, "lexicographical ordering” does not imply
human-written-language-alphabetical order at all, as there’s no universal
alphabetical ordering for human language. I.e., such a concrete notion for
Strings does not exist, not even theoretically. “Lexicographical” derives
its meaning from the mathematical usage[1] which uses that term as well as
“alphabet” without being restricted to human-written-language, in which it
means some total ordering over a finite set.

[1] Lexicographic order - Wikipedia

I see, apologies for the mistake.
Regardless of the specific type of ordering, lexicographicallyEquals says
to me that the objects should be sorted into lexicographical order and
compared. Precisely the opposite of the proposal.

That is an interesting interpretation. I suppose anyone has the right to
interpret anything in any way they please, but this seems a uniquely
idiosyncratic interpretation. The total ordering is over the set of all
sequences, and the comparison is between two sequences--note that the
function name uses the singular ("equals") and makes no reference to the
lexicography or ordering of elements. Likewise, dictionaries don't sort
"hello" and "world" by comparing "ehllo" and "dlorw".

···

On Fri, Oct 13, 2017 at 12:12 PM, Kevin Nattinger <swift@nattinger.net> wrote:

On Oct 13, 2017, at 10:01 AM, Michael Ilseman <milseman@apple.com> wrote:
On Oct 12, 2017, at 9:57 PM, Kevin Nattinger via swift-evolution < > swift-evolution@swift.org> wrote:

2. This is really just a symptom of a bigger problem. The fact that two
Sets can compare equal and yet return different results for that method
(among too many others) is logically inconsistent and points to a much
deeper issue with Set and Sequence. It is probably about 3 releases too
late to get this straightened out properly, but I'll outline the real issue
in case someone has an idea for fixing it.

*The root of the problem is that Set conforms to Sequence, but Sequence
doesn't require a well-defined order.* Since Set doesn't have a
well-defined order, a significant portion of its interface is unspecified.
The methods are implemented because they have to be, but they doesn't have
well-defined or necessarily consistent results.

A sequence is, by definition, ordered. That is reflected in the fact that
over half the methods in the main Sequence definition* make no sense and
are not well-defined unless there is a well-defined order to the sequence
itself. What does it even mean to `dropFirst()` in a Set? The fact that two
objects that compare equal can give different results for a 100% deterministic
function is illogical, nonsensical, and dangerous.

* 7/12 by my count, ignoring `_*` funcs but including the `var`

The current contents of Sequence can be cleanly divided into two groups;
those that return SubSequence imply a specific ordering, and the
rest do not.

I think those should be/should have been two separate protocols:

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)
}

(The comments, of course, would be more sensible types once the ideas can
actually be expressed in Swift)

Then unordered collections (Set and Dictionary) would just conform to
Iterable and not Sequence, so ALL the methods on those classes would make
logical sense and have well-defined behavior; no change would be
needed for ordered collections.

Now, the practical matter. If this were Swift 1->2 or 2->3, I doubt there
would be a significant issue with actually making this change.
Unfortunately, we're well beyond that and making a change this
deep is an enormous deal. So I see two ways forward.

1. We could go ahead and make this separation. Although it's a potentially
large breaking change, I would argue that because the methods are
ill-defined anyway, the breakage is justified and a net benefit.

2. We could try and think of a way to make the distinction between ordered
and unordered "sequences" in a less-breaking manner. Unfortunately, I don't
have a good suggestion for this, but if anyone has ideas, I'm all ears. Or
eyes, as the case may be.

On Oct 12, 2017, at 4:24 PM, Xiaodi Wu via swift-evolution < > swift-evolution@swift.org> wrote:

Rename Sequence.elementsEqual

   - Proposal: SE-NNNN
   <https://gist.github.com/xwu/NNNN-rename-elements-equal.md&gt;
   - Authors: Xiaodi Wu <https://github.com/xwu&gt;
   - Review Manager: TBD
   - Status: *Awaiting review*

<Rename Sequence.elementsEqual · GitHub;
Introduction

The current behavior of Sequence.elementsEqual is potentially confusing
to users given its name. Having surveyed the alternative solutions to this
problem, it is proposed that the method be renamed to Sequence.
lexicographicallyEquals.
[...]

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

[xwu (Xiaodi Wu)]

You’re welcome to bikeshed the entire API surface area of sequences and
collections, but you won’t be the first to explore this area. A number of
us looked into this area in the past few years and did not reach a
measurable improved result.

I don’t need or want to bikeshed the entire sequence and collection
surface area, I just want to fix one clear and GLARING issue:

A Set is NOT a sequence.

Note that this goes for dictionaries and any other unordered “sequences"
as well.

That was in an early draft of my original email, but I dropped it because
I was afraid people would just stop reading and dismiss the idea
out-of-hand without considering the problem or arguments. Apparently I
should have at least put it at the bottom, so sorry if the root issue was
unclear.

Sequences can be ordered or unordered,

You seem to be confusing the English word “sequence” with the (current)
Swift protocol “Sequence." A sequence is, by definition, ordered. Not
enforcing that in a protocol does not override the English language, and as
this entire thread demonstrates, causes issues further on down the line.

We are discussing the Swift protocol `Sequence`. It really doesn't matter
at all what the English word "sequence" means, and any difference between
the English word and the Swift term is emphatically *not* the root cause of
the issue. Here's why:

* A Swift `Sequence` is, to put it simplistically, a thing that can be
iterated over in a `for...in` loop. If it would make you happy, for the
rest of the discussion, let's suppose we called the protocol `ForLoopable`
instead of `Sequence`.

ForLoopable is so ugly. Since we’re just iterating over the elements, how
about, oh, say, `Iterable`? Hey, that looks familiar.

I'm not trying to bikeshed the name of `Sequence`. I'm picking an
intentionally unwieldy name for the purposes of discussing the semantics of
this particular protocol. The point is that the underlying issue has
nothing to do with the name; it can be `Iterable` or it can be `SpongeBob`
for all I care.

* `Set` should conform to `ForLoopable`. (This I state as a premise; if
you disagree with the notion that we should be able to iterate over the
elements of an instance of `Set` with a `for...in loop`, then it's clearly
a whole other discussion and not a question of what the English word
"sequence" means.)

Obviously, `Set: Iterable`. I don’t think I’ve said anything to suggest
you shouldn’t be able to iterate over unordered collections.

* If a type `T` conforms to `ForLoopable` and an instance `t` of that type
has at least one element, then *something* has to be the first element in a
`for element in t { ... }` loop. Put another way, every instance of a type
that conforms to `ForLoopable` must have at least one publicly observable
order (although, intriguingly, I'm not sure it has to be a repeatable one).
It is possible, therefore, to have a semantic answer to the question of
which element is `first` or (if finite) `last`; one can also
`drop(while:)`, etc., and perform lexicographical comparisons.

As a side effect of Swift being a procedural language each iteration
happens to occur in some order, yes, but that order is meaningless and
reflects nothing about the Set itself. In fact, I’d say that *`first`,
`last`, etc. are not even defined on the original Set per se, only on the
specific order that a particular iteration resulted in*. And that order
is not necessarily predictable, nor necessarily stable, as you yourself
said.

Consider an Iterable that gives a different order every time it’s
iterated.
Should calling `.first` or `last` give a different object every time?
That’s absurd.
Should an object lexicographically compare not equal to itself? Even more
absurd.

What's your basis for saying that such behavior is absurd? It is explicitly
permitted for instances of types conforming to `SpongeBob` to be
single-pass and/or infinite. For a single-pass `SpongeBob`, `first` will
certainly return a different value every time it is invoked.

A random number generator fulfills all the semantic requirements of
conforming to `SpongeBob`, and in fact I do just that in NumericAnnex
<https://github.com/xwu/NumericAnnex/blob/master/Sources/PRNG.swift#L53&gt;\.
`first` gives a different value every time, and a randomly generated
`SpongeBob` would unsurprisingly compare lexicographically not equal to
itself.

On the other hand, if I have a collection of objects that I want iterated

in a particular order, I can use a container that iterates in a specific,
known, well-defined way, and use that to construct the sequence of
objects. That’s clearly an Iterable collection, but the guarantee is
stronger than that. Since it iterates objects in a specific sequence, the
logical way to express that would be `Sequence: Iterable`. Again, we’ve
seen that before.

Now, since a Sequence is guaranteed to iterate the same every time,
suddenly our `first`, `last`, `drop*`, etc. methods have a meaning inherent
to the collection itself, rather than a specific iteration.

What you call a "Sequence" here would have to be multi-pass, finite, and
ordered. That's actually more semantically constrained than what Swift
calls a `Collection` (which requires conforming types to be multi-pass
and(?) finite). By contrast, Swift's `SpongeBob` protocol explicitly
permits conforming single-pass, infinite, and/or unordered types. As long
as it is possible to iterate over a `SpongeBob`, it is meaningful to ask
what element is first obtained upon iteration or to drop the first element
obtained upon iteration. And as long as iteration is not required to be
repeatable (and it isn't), it is perfectly acceptable for these algorithms
to return a different result every time.

`first` is the first object in the Sequence. It doesn’t matter how the

sequence came to be in that order; it doesn’t matter whether or not the
sequence has already been iterated or how many times. `first` is the first
object that is, was, and always will be presented by the Sequence’s
Iterator. (Until the collection is mutated, obviously).

*To summarize,*
A Set has no intrinsic order. You can iterate over it, and a specific
iteration of a set has an order, but that order is not tied to the Set
itself beyond including all and only the items therein. Therefore, the Set
itself has no intrinsic `first`, `last`, lexicographical comparison, etc.;
only its iterations do, and they are not themselves Sets.
A Sequence does have an intrinsic order. The order of iteration reflects
the order inherent to the Sequence. Therefore, a Sequence has a `first`,
`last`, lexicographical comparison, etc.

Just in case it’s not obvious, `Set` here is pretty much interchangeable
with any other unordered iterable.

What you want to call a "Sequence" is what Swift calls a `Collection`, with
additional restrictions. What you want to be called "Iterable" is what
Swift calls `Sequence` (or now, `SpongeBob`). Clearly, shuffling names will
not make these protocols support any more functionality, so that can be put
aside.

Now, with that out of the way, why do you think that only `Collection`
types should have `first` and `last`? These helper properties and methods
are simply convenient ways to spell things that can be done with
`for...in`--the whole point of supplying them is to allow people to work
with these types in a more functional style.

public protocol Iterable {

···

On Sat, Oct 14, 2017 at 2:28 AM, Kevin Nattinger <swift@nattinger.net> wrote:

On Oct 13, 2017, at 8:28 PM, Xiaodi Wu <xiaodi.wu@gmail.com> wrote:
On Fri, Oct 13, 2017 at 12:03 PM, Kevin Nattinger <swift@nattinger.net> > wrote:

On Oct 13, 2017, at 6:52 AM, Xiaodi Wu <xiaodi.wu@gmail.com> wrote:

  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 {…}

[trs (Thorsten Seitz)]

Well said, Kevin! I agree to all points you made. Yes, a Set has no intrinsic order, just an iteration over a set has. And the latter does not even have to be stable.

Let’s split Iterable off Sequence.

-Thorsten

···

Am 14.10.2017 um 09:28 schrieb Kevin Nattinger via swift-evolution <swift-evolution@swift.org>:

On Oct 13, 2017, at 8:28 PM, Xiaodi Wu <xiaodi.wu@gmail.com <mailto:xiaodi.wu@gmail.com>> wrote:

On Fri, Oct 13, 2017 at 12:03 PM, Kevin Nattinger <swift@nattinger.net <mailto:swift@nattinger.net>> wrote:

On Oct 13, 2017, at 6:52 AM, Xiaodi Wu <xiaodi.wu@gmail.com <mailto:xiaodi.wu@gmail.com>> wrote:

You’re welcome to bikeshed the entire API surface area of sequences and collections, but you won’t be the first to explore this area. A number of us looked into this area in the past few years and did not reach a measurable improved result.

I don’t need or want to bikeshed the entire sequence and collection surface area, I just want to fix one clear and GLARING issue:

A Set is NOT a sequence.

Note that this goes for dictionaries and any other unordered “sequences" as well.

That was in an early draft of my original email, but I dropped it because I was afraid people would just stop reading and dismiss the idea out-of-hand without considering the problem or arguments. Apparently I should have at least put it at the bottom, so sorry if the root issue was unclear.

Sequences can be ordered or unordered,

You seem to be confusing the English word “sequence” with the (current) Swift protocol “Sequence." A sequence is, by definition, ordered. Not enforcing that in a protocol does not override the English language, and as this entire thread demonstrates, causes issues further on down the line.

We are discussing the Swift protocol `Sequence`. It really doesn't matter at all what the English word "sequence" means, and any difference between the English word and the Swift term is emphatically *not* the root cause of the issue. Here's why:

* A Swift `Sequence` is, to put it simplistically, a thing that can be iterated over in a `for...in` loop. If it would make you happy, for the rest of the discussion, let's suppose we called the protocol `ForLoopable` instead of `Sequence`.

ForLoopable is so ugly. Since we’re just iterating over the elements, how about, oh, say, `Iterable`? Hey, that looks familiar.

* `Set` should conform to `ForLoopable`. (This I state as a premise; if you disagree with the notion that we should be able to iterate over the elements of an instance of `Set` with a `for...in loop`, then it's clearly a whole other discussion and not a question of what the English word "sequence" means.)

Obviously, `Set: Iterable`. I don’t think I’ve said anything to suggest you shouldn’t be able to iterate over unordered collections.

* If a type `T` conforms to `ForLoopable` and an instance `t` of that type has at least one element, then *something* has to be the first element in a `for element in t { ... }` loop. Put another way, every instance of a type that conforms to `ForLoopable` must have at least one publicly observable order (although, intriguingly, I'm not sure it has to be a repeatable one). It is possible, therefore, to have a semantic answer to the question of which element is `first` or (if finite) `last`; one can also `drop(while:)`, etc., and perform lexicographical comparisons.

As a side effect of Swift being a procedural language each iteration happens to occur in some order, yes, but that order is meaningless and reflects nothing about the Set itself. In fact, I’d say that `first`, `last`, etc. are not even defined on the original Set per se, only on the specific order that a particular iteration resulted in. And that order is not necessarily predictable, nor necessarily stable, as you yourself said.

Consider an Iterable that gives a different order every time it’s iterated.
Should calling `.first` or `last` give a different object every time? That’s absurd.
Should an object lexicographically compare not equal to itself? Even more absurd.

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.
`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.

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

[adamkemp]

The fact is, no matter how much it surprises and bothers you, there is clear evidence from the reactions in this thread that the proposed name is not as clear as you think it is. It doesn’t matter why. This thread could be more productive if you would consider the various other proposed names with an open mind instead of just expressing shock that people don’t interpret the proposed name the way you would like them to. There’s nothing you can do about that. It’s just the way it is. Let’s see what we can come up with that more people intuitively understand.

···

On Oct 14, 2017, at 9:49 PM, Xiaodi Wu via swift-evolution <swift-evolution@swift.org> wrote:

On Sat, Oct 14, 2017 at 11:25 PM, Jonathan Hull <jhull@gbis.com> wrote:
Because the mathematical term you talk about has conditions which must be met to be used/valid. Namely:

1) The “Alphabet” of elements must be totally ordered
2) The lexicographical comparison must be applied to ordered sequences of elements from that alphabet

Neither of those conditions are met for an unordered generic collection (e.g. a set of equatable, but not comparable elements).

This is diametrically the opposite claim that Michael just made. Here, you argue that the confusion stems from the extension of the term to sequences with elements that are equatable but not comparable because there *isn't* a total ordering for the elements. Michael just said that the term is confusing particularly with Ints *because* they have an obvious total ordering (i.e., they are comparable). And in fact, the apparently common misconception is that the function would instead sort the elements of each sequence by that ordering, which is obviously inapplicable for equatable but not comparable elements, and such a misconception is therefore impossible in that scenario.

_The very first result on Google_ defines lexicographical comparison unambiguously for C++:

Lexicographical comparison is a operation with the following properties:

Two ranges are compared element by element.
The first mismatching element defines which range is lexicographically less or greater than the other.
If one range is a prefix of another, the shorter range is lexicographically less than the other.
If two ranges have equivalent elements and are of the same length, then the ranges are lexicographically equal.
An empty range is lexicographically less than any non-empty range.
Two empty ranges are lexicographically equal.

The purpose behind choosing "lexicographicallyEquals" was that it is a term that has an established meaning, easily googled, that describes the algorithm exactly and unambiguously in two words. If you have seen this term in use, you will know what the Swift method does. If you have not seen this term, then even in the absence of Swift documentation, a single search will lead you to the correct answer. I am simply in disbelief that apparently many people will see a term with which they are unfamiliar, assume it means something it does not, and use the function without consulting the documentation or looking up the term.

The underlying issue here is that the “ordering” of the sequence coming out of a set/dictionary is undefined and may rely on internal implementation details. Building anything on top of that is problematic because the foundation is undefined. Lexicographical’s connotation of applying a total order only compounds that original issue, especially if the elements are strings or some other sequential data type.

Right, and the purpose of this proposal is to give it such a name that it is obvious that this function is probably not what you want in comparing two concrete sets (much as it is obvious on first glance that `first` is probably not useful when working with concrete sets), without going down the road of attempting to rip out the established protocol hierarchy.

On Oct 14, 2017, at 8:45 PM, Xiaodi Wu via swift-evolution <swift-evolution@swift.org> wrote:

On Sat, Oct 14, 2017 at 8:11 PM, Michael Ilseman <milseman@apple.com> wrote:
I think that “match” is a word to avoid for this, as this doesn’t have anything to do with pattern matching, fuzzy matching, etc., while “equals” is precisely the concept we’re using.

What about the name “sequentiallyEquals”? Highlight the fact that we’re talking about sequential ordering, i.e. whatever order the sequence provides, as opposed to first doing some lexicographical ordering of elements themselves.

var a: Set<Int> = [3, 1, 2]
a.sequentiallyEquals([1,2,3]) // result depends on application of equality in a (potentially-arbitrary) sequential ordering

Whereas I could see the following being more confusing:

var a: Set<Int> = [3, 1, 2]
a.lexicographicallyEquals([1,2,3]) // result depends on application of equality, but what meaning does “lexicographically” convey?

It’s not immediately clear to someone new to the API that “lexicographically” speaks to the nature of the sequence’s (potentially-arbitrary) order, irrespective of element. It could give the false impression that it speaks to some nature of the elements themselves, in this case Ints, which have an obvious lexicographical ordering. I don’t know how frequent that misconception would be in practice, but it does cause me to do a double-take in this contrived example.

I'm entirely puzzled that apparently large numbers of people believe lexicographical comparison, a term with a very specific mathematical definition and no colloquial use, to mean what it does not. I'd like to avoid inventing Swift-specific new terms for this particular concept which is not at all unique to Swift. The other plausible terms I can see with some other use might be "elementwise equals" or "entrywise equals" or "coordinatewise equals."

On Oct 14, 2017, at 1:04 PM, Benjamin G via swift-evolution <swift-evolution@swift.org> wrote:

To answer more precisely this request (which remains valid no matter the protocol hierarchy). I propose

"matchesSequence" ( or simply "matches" or "match", whatever is more coherent with the naming guidelines).

So
var a: [Int] = [1,2,3]
a.matchesSequence([1,2,3]) returns true.

I first thought that the verb "matching" was too heavily associated to regular expressions, but i think that it's the correct equivalent for something as general as a sequence.

On Fri, Oct 13, 2017 at 1:24 AM, Xiaodi Wu via swift-evolution <swift-evolution@swift.org> wrote:
Rename Sequence.elementsEqual

Proposal: SE-NNNN
Authors: Xiaodi Wu
Review Manager: TBD
Status: Awaiting review
Introduction

The current behavior of Sequence.elementsEqual is potentially confusing to users given its name. Having surveyed the alternative solutions to this problem, it is proposed that the method be renamed to Sequence.lexicographicallyEquals.

Motivation

As outlined by Ole Begemann, use of Sequence.elementsEqual(_:) can lead to surprising results if the sequences compared are unordered:

var set1: Set<Int> = Set(1...5)
var set2: Set<Int> = Set((1...5).reversed())

set1 == set2 // true
set1.elementsEqual(set2) // false
This result does reflect the intended and documented behavior of the elementsEqual(_:) method, which performs a lexicographical elementwise comparison. That is, the method first compares set1.first to set2.first, then (if the two elements compare equal) compares the next element stored internally in set1 to the next element stored internally in set2, and so on.

In almost all circumstances where a set is compared to another set, or a dictionary is compared to another dictionary, users should use == instead of elementsEqual(_:).

Proposed solution

The proposed solution is the result of an iterative process of reasoning, presented here:

The first and most obvious solution is to remove the elementsEqual(_:) method altogether in favor of ==. This prevents its misuse. However, because elementsEqual(_:) is a generic method on Sequence, we can use it to compare an instance of UnsafeBufferPointer<Int> to an instance of [Int]. This is a useful and non-redundant feature which would be eliminated if the method is removed altogether.

A second solution is to create overloads that forbid the use of the elementsEqual(_:) method specifically in non-generic code. This would prevent misuse in non-generic code; however, it would also forbid legitimate mixed-type comparisons in non-generic code while failing to prevent misuse in generic code. The solution also creates a difference in the behavior of generic and non-generic code calling the same method, which is potentially confusing, without solving the problem completely.

A third solution is to dramatically overhaul the protocol hierarchy for Swift sequences and collections so that unordered collections no longer have members such as first and elementsEqual(_:). However, this would be a colossal and source-breaking undertaking, and it is unlikely to be satisfactory in addressing all the axes of differences among sequence and collection types:

Finite versus infinite
Single-pass versus multi-pass
Ordered versus unordered
Lazy versus eager
Forward/bidirectional/random-access
A fourth solution is proposed here. It is predicated on the following observation:

Another method similar to elementsEqual(_:) already exists on Sequence named lexicographicallyPrecedes(_:). Like first, elementsEqual(_:), drop(while:), and others, it relies on the internal order of elements in a manner that is not completely suitable for an unordered collection. However, like first and unlike elementsEqual(_:), this fact is called out in the name of the method; unsurprisingly, like first and unlike elementsEqual(_:), there is no evidence that lexicographicallyPrecedes(_:) has been a pitfall for users.

This observation suggests that a major reason for confusion over elementsEqual(_:) stems from its name. So, it is proposed that elementsEqual(_:) should be renamed to lexicographicallyEquals(_:). The function will remain somewhat of a poor fit for unordered collections, but no more so than many other methods that cannot trivially be removed from the API of unordered collections (as discussed above). The key is that, with such a renaming, the behavior of this method will no longer be confusing.

Detailed design

extension Sequence where Element : Equatable {
  @available(*, deprecated, message: "Use '==' if possible to compare two sequences of the same type, or use 'lexicographicallyEquals' to compare two ordered sequences.")
  public func elementsEqual<Other : Sequence>(
    _ other: Other
  ) -> Bool where Other.Element == Element {
    return lexicographicallyEquals(other)
  }
  
  public func lexicographicallyEquals<Other : Sequence>(
    _ other: Other
  ) -> Bool where Other.Element == Element {
    // The body of this method is unchanged.
    var iter1 = self.makeIterator()
    var iter2 = other.makeIterator()
    while true {
      switch (iter1.next(), iter2.next()) {
      case let (e1?, e2?):
        if e1 != e2 { return false }
      case (_?, nil), (nil, _?):
        return false
      case (nil, nil):
        return true
      }
    }
  }
}
A parallel change will be made with respect to elementsEqual(_:by:); that is, it will be deprecated in favor of lexicographicallyEquals(_:by:).

Source compatibility

Existing code that uses elementsEqual will gain a deprecation warning.

Effect on ABI stability

None.

Effect on API resilience

This proposal adds new methods to the public API of Sequence and conforming types.

Alternatives considered

It is to be noted that lexicographicallyPrecedes(_:by:) and elementsEqual(_:by:) are essentially the same method, since both perform a lexicographical comparison using a custom predicate. However, there is not a good unifying name. (lexicographicallyCompares(to:by:) reads poorly.) Moreover, the predicate supplied is intended to have very different semantics, and maintaining two distinct methods may be a superior fit with the typical user's mental model of the intended behavior and may also be clearer to readers of the code. Therefore, this proposal does not seek to unify the two methods; instead, elementsEqual(_:by:) will be renamed lexicographicallyEquals(_:by:) as detailed above.

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

[xwu (Xiaodi Wu)]

The fact is, no matter how much it surprises and bothers you, there is
clear evidence from the reactions in this thread that the proposed name is
not as clear as you think it is. It doesn’t matter why.

Disagree strongly that it doesn't matter why. I'm trying to figure out what
the term is being confused for, and why people are encountering this
confusion, because that is essential to improving upon it.

This thread could be more productive if you would consider the various

other proposed names with an open mind instead of just expressing shock
that people don’t interpret the proposed name the way you would like them
to. There’s nothing you can do about that. It’s just the way it is.

Disagree here too; whether a method is understood or misunderstood can be
affected by much more than just the name; for instance, the documentation
for that method, whether the terminology is used elsewhere in similar APIs,
whether introductory materials introduce the terminology and use it
consistently, etc. All of these can be modifiable factors that can be
looked into.

Let’s see what we can come up with that more people intuitively understand.

That would be nice, but as I said, not necessarily the first priority here.
As this method is not intended to be the first-choice function for
comparison and the motivating problem is _presence of misunderstanding_
rather than _lack of understanding_, I'd like to first come up with a name
that people do not intuitively misunderstand. Given that the underlying
root cause is that the protocols are not a perfect fit for unordered types,
I am quite doubtful that there is any solution possible that many people
can intuitively understand. Therefore, it is entirely OK (to me) if the
result is something that is so obtuse as to be at first meaningless to most
people.

···

On Sun, Oct 15, 2017 at 12:18 AM, Adam Kemp <adam.kemp@apple.com> wrote:

On Oct 14, 2017, at 9:49 PM, Xiaodi Wu via swift-evolution < > swift-evolution@swift.org> wrote:

On Sat, Oct 14, 2017 at 11:25 PM, Jonathan Hull <jhull@gbis.com> wrote:

Because the mathematical term you talk about has conditions which must be
met to be used/valid. Namely:

1) The “Alphabet” of elements must be totally ordered
2) The lexicographical comparison must be applied to ordered sequences of
elements from that alphabet

Neither of those conditions are met for an unordered generic collection
(e.g. a set of equatable, but not comparable elements).

This is diametrically the opposite claim that Michael just made. Here, you
argue that the confusion stems from the extension of the term to sequences
with elements that are equatable but not comparable because there *isn't* a
total ordering for the elements. Michael just said that the term is
confusing particularly with Ints *because* they have an obvious total
ordering (i.e., they are comparable). And in fact, the apparently common
misconception is that the function would instead sort the elements of each
sequence by that ordering, which is obviously inapplicable for equatable
but not comparable elements, and such a misconception is therefore
impossible in that scenario.

_The very first result on Google_ defines lexicographical comparison
unambiguously for C++:

Lexicographical comparison is a operation with the following properties:

   - Two ranges are compared element by element.
   - The first mismatching element defines which range is
   lexicographically *less* or *greater* than the other.
   - If one range is a prefix of another, the shorter range is
   lexicographically *less* than the other.
   - If two ranges have equivalent elements and are of the same length,
   then the ranges are lexicographically *equal*.
   - An empty range is lexicographically *less* than any non-empty
   range.
   - Two empty ranges are lexicographically *equal*.

The purpose behind choosing "lexicographicallyEquals" was that it is a

term that has an established meaning, easily googled, that describes the
algorithm exactly and unambiguously in two words. If you have seen this
term in use, you will know what the Swift method does. If you have not seen
this term, then even in the absence of Swift documentation, a single search
will lead you to the correct answer. I am simply in disbelief that
apparently many people will see a term with which they are unfamiliar,
assume it means something it does not, and use the function without
consulting the documentation or looking up the term.

The underlying issue here is that the “ordering” of the sequence coming

out of a set/dictionary is undefined and may rely on internal
implementation details. Building anything on top of that is problematic
because the foundation is undefined. Lexicographical’s connotation of
applying a total order only compounds that original issue, especially if
the elements are strings or some other sequential data type.

Right, and the purpose of this proposal is to give it such a name that it
is obvious that this function is probably not what you want in comparing
two concrete sets (much as it is obvious on first glance that `first` is
probably not useful when working with concrete sets), without going down
the road of attempting to rip out the established protocol hierarchy.

On Oct 14, 2017, at 8:45 PM, Xiaodi Wu via swift-evolution < >> swift-evolution@swift.org> wrote:

On Sat, Oct 14, 2017 at 8:11 PM, Michael Ilseman <milseman@apple.com> >> wrote:

I think that “match” is a word to avoid for this, as this doesn’t have
anything to do with pattern matching, fuzzy matching, etc., while “equals”
is precisely the concept we’re using.

What about the name “sequentiallyEquals”? Highlight the fact that we’re
talking about sequential ordering, i.e. whatever order the sequence
provides, as opposed to first doing some lexicographical ordering of
elements themselves.

var a: Set<Int> = [3, 1, 2]
a.sequentiallyEquals([1,2,3]) // result depends on application of
equality in a (potentially-arbitrary) sequential ordering

Whereas I could see the following being more confusing:

var a: Set<Int> = [3, 1, 2]
a.lexicographicallyEquals([1,2,3]) // result depends on application of
equality, but what meaning does “lexicographically” convey?

It’s not immediately clear to someone new to the API that
“lexicographically” speaks to the nature of the sequence’s
(potentially-arbitrary) order, irrespective of element. It could give the
false impression that it speaks to some nature of the elements themselves,
in this case Ints, which have an obvious lexicographical ordering. I don’t
know how frequent that misconception would be in practice, but it does
cause me to do a double-take in this contrived example.

I'm entirely puzzled that apparently large numbers of people believe
lexicographical comparison, a term with a very specific mathematical
definition and no colloquial use, to mean what it does not. I'd like to
avoid inventing Swift-specific new terms for this particular concept which
is not at all unique to Swift. The other plausible terms I can see with
some other use might be "elementwise equals" or "entrywise equals" or
"coordinatewise equals."

On Oct 14, 2017, at 1:04 PM, Benjamin G via swift-evolution < >>> swift-evolution@swift.org> wrote:

To answer more precisely this request (which remains valid no matter the
protocol hierarchy). I propose

"matchesSequence" ( or simply "matches" or "match", whatever is more
coherent with the naming guidelines).

So
var a: [Int] = [1,2,3]
a.matchesSequence([1,2,3]) returns true.

I first thought that the verb "matching" was too heavily associated to
regular expressions, but i think that it's the correct equivalent for
something as general as a sequence.

On Fri, Oct 13, 2017 at 1:24 AM, Xiaodi Wu via swift-evolution < >>> swift-evolution@swift.org> wrote:

Rename Sequence.elementsEqual

   - Proposal: SE-NNNN
   <https://gist.github.com/xwu/NNNN-rename-elements-equal.md&gt;
   - Authors: Xiaodi Wu <https://github.com/xwu&gt;
   - Review Manager: TBD
   - Status: *Awaiting review*

<Rename Sequence.elementsEqual · GitHub;
Introduction

The current behavior of Sequence.elementsEqual is potentially
confusing to users given its name. Having surveyed the alternative
solutions to this problem, it is proposed that the method be renamed to
Sequence.lexicographicallyEquals.

<Rename Sequence.elementsEqual · GitHub;
Motivation

As outlined by Ole Begemann
<https://twitter.com/olebegemann/status/916291785185529857&gt;, use of
Sequence.elementsEqual(_:) can lead to surprising results if the
sequences compared are unordered:

var set1: Set<Int> = Set(1...5)var set2: Set<Int> = Set((1...5).reversed())

set1 == set2 // trueset1.elementsEqual(set2) // false

This result does reflect the *intended and documented* behavior of the
elementsEqual(_:) method, which performs a *lexicographical*
elementwise comparison. That is, the method first compares set1.first
to set2.first, then (if the two elements compare equal) compares the
next element stored internally in set1 to the next element stored
internally in set2, and so on.

In almost all circumstances where a set is compared to another set, or
a dictionary is compared to another dictionary, users should use ==
instead of elementsEqual(_:).

<Rename Sequence.elementsEqual · GitHub
solution

The proposed solution is the result of an iterative process of
reasoning, presented here:

The first and most obvious solution is to remove the elementsEqual(_:)
method altogether in favor of ==. This prevents its misuse. However,
because elementsEqual(_:) is a generic method on Sequence, we can use
it to compare an instance of UnsafeBufferPointer<Int> to an instance
of [Int]. This is a useful and non-redundant feature which would be
eliminated if the method is removed altogether.

A second solution <https://github.com/apple/swift/pull/12318&gt; is to
create overloads that forbid the use of the elementsEqual(_:) method
specifically in non-generic code. This would prevent misuse in non-generic
code; however, it would also forbid legitimate mixed-type comparisons in
non-generic code while failing to prevent misuse in generic code. The
solution also creates a difference in the behavior of generic and
non-generic code calling the same method, which is potentially confusing,
without solving the problem completely.

A third solution is to dramatically overhaul the protocol hierarchy for
Swift sequences and collections so that unordered collections no longer
have members such as first and elementsEqual(_:). However, this would
be a colossal and source-breaking undertaking, and it is unlikely to be
satisfactory in addressing all the axes of differences among sequence and
collection types:

   - Finite versus infinite
   - Single-pass versus multi-pass
   - Ordered versus unordered
   - Lazy versus eager
   - Forward/bidirectional/random-access

A fourth solution is proposed here. It is predicated on the following
observation:

*Another method similar to elementsEqual(_:) already exists on Sequence
named lexicographicallyPrecedes(_:). Like first, elementsEqual(_:),
drop(while:), and others, it relies on the internal order of elements in a
manner that is not completely suitable for an unordered collection.
However, like first and unlike elementsEqual(_:), this fact is called out
in the name of the method; unsurprisingly, like first and unlike
elementsEqual(_:), there is no evidence that lexicographicallyPrecedes(_:)
has been a pitfall for users.*

This observation suggests that a major reason for confusion over
elementsEqual(_:) stems from its name. So, *it is proposed that
elementsEqual(_:) should be renamed to lexicographicallyEquals(_:)*.
The function will remain somewhat of a poor fit for unordered collections,
but no more so than many other methods that cannot trivially be removed
from the API of unordered collections (as discussed above). The key is
that, with such a renaming, the behavior of this method will no longer be
confusing.

<Rename Sequence.elementsEqual · GitHub
design

extension Sequence where Element : Equatable {
  @available(*, deprecated, message: "Use '==' if possible to compare two sequences of the same type, or use 'lexicographicallyEquals' to compare two ordered sequences.")
  public func elementsEqual<Other : Sequence>(
    _ other: Other
  ) -> Bool where Other.Element == Element {
    return lexicographicallyEquals(other)
  }

  public func lexicographicallyEquals<Other : Sequence>(
    _ other: Other
  ) -> Bool where Other.Element == Element {
    // The body of this method is unchanged. var iter1 = self.makeIterator()
    var iter2 = other.makeIterator()
    while true {
      switch (iter1.next(), iter2.next()) {
      case let (e1?, e2?):
        if e1 != e2 { return false }
      case (_?, nil), (nil, _?):
        return false
      case (nil, nil):
        return true
      }
    }
  }
}

A parallel change will be made with respect to elementsEqual(_:by:);
that is, it will be deprecated in favor of
lexicographicallyEquals(_:by:).

<Rename Sequence.elementsEqual · GitHub
compatibility

Existing code that uses elementsEqual will gain a deprecation warning.

<Rename Sequence.elementsEqual · GitHub
on ABI stability

None.

<Rename Sequence.elementsEqual · GitHub
on API resilience

This proposal adds new methods to the public API of Sequence and
conforming types.

<Rename Sequence.elementsEqual · GitHub
considered

It is to be noted that lexicographicallyPrecedes(_:by:) and
elementsEqual(_:by:) are essentially the same method, since both
perform a lexicographical comparison using a custom predicate. However,
there is not a good unifying name. (lexicographicallyCompares(to:by:)
reads poorly.) Moreover, the predicate supplied is intended to have very
different semantics, and maintaining two distinct methods may be a superior
fit with the typical user's mental model of the intended behavior and may
also be clearer to readers of the code. Therefore, this proposal does not
seek to unify the two methods; instead, elementsEqual(_:by:) will be
renamed lexicographicallyEquals(_:by:) as detailed above.

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

[adamkemp]

···

--
Adam Kemp

On Oct 13, 2017, at 7:59 AM, Xiaodi Wu xiaodi.wu@gmail.com wrote:

On Fri, Oct 13, 2017 at 09:02 Adam Kemp adam.kemp@apple.com wrote:

Right, but if you do look it up you get a bunch of things talking about sorting words.

And that’s a perfect description of the behavior. It’s a lexicographical comparison operation!

Is it? Are we always comparing words?

How about pairwiseEqual?

A lexicographical comparison compares not merely pairwise, but in order from the first item onwards, and stops at the first unequal pair. Proceeding in order is key information, while stopping early on false is a nice-to-have. There’s already a word for this, and it’s “lexicographical.” And the analogy is universally understood: everyone has used a dictionary or index.

Clearly it’s not. You have several people telling you they don’t think it’s clear. You can argue that it’s technically correct if you want, but don’t try to tell us everyone understands it when it’s obvious that’s not true.

--
Adam Kemp

On Oct 13, 2017, at 5:17 AM, Xiaodi Wu xiaodi.wu@gmail.com wrote:

“Lexicographical comparison” is a pretty standard term, and easy to Google. We didn’t make it up for Swift :)

Since Swift names this protocol Sequence, something named “Sequence.sequenceEqual” cannot distinguish this method from ==.

On Fri, Oct 13, 2017 at 01:28 Adam Kemp adam.kemp@apple.com wrote:

I agree that the proposed name is a poor choice. If we just focus on the naming part, there is precedent in other languages for the name “sequenceEqual”. I think that name makes it a bit clearer that the result is whether the sequences match pair wise rather than whether they have the same elements irrespective of order. I don’t think it entirely solves the problem, but I like it a lot better than the proposed name.

--
Adam Kemp

On Oct 12, 2017, at 9:57 PM, Kevin Nattinger via swift-evolution swift-evolution@swift.org wrote:

–∞

1. I strongly object to the proposed name. It doesn't make it more clear to me what the method does, and is misleading at best. Among other issues, "lexicographical" is defined as alphabet order, and (1) this method applies to objects that are not Strings, and (2) this method's behavior isn't any more well-defined for Strings, so that name is even more of a lie than the original.

2. This is really just a symptom of a bigger problem. The fact that two Sets can compare equal and yet return different results for that method (among too many others) is logically inconsistent and points to a much deeper issue with Set and Sequence. It is probably about 3 releases too late to get this straightened out properly, but I'll outline the real issue in case someone has an idea for fixing it.

The root of the problem is that Set conforms to Sequence, but Sequence doesn't require a well-defined order. Since Set doesn't have a well-defined order, a significant portion of its interface is unspecified. The methods are implemented because they have to be, but they doesn't have well-defined or necessarily consistent results.

A sequence is, by definition, ordered. That is reflected in the fact that over half the methods in the main Sequence definition* make no sense and are not well-defined unless there is a well-defined order to the sequence itself. What does it even mean to dropFirst() in a Set? The fact that two objects that compare equal can give different results for a 100% deterministic function is illogical, nonsensical, and dangerous.

• 7/12 by my count, ignoring _* funcs but including the var

The current contents of Sequence can be cleanly divided into two groups; those that return SubSequence imply a specific ordering, and the rest do not.

I think those should be/should have been two separate protocols:

public protocol Iterable {

associatedtype Iterator: IteratorProtocol

func map(...) -> [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)

}

(The comments, of course, would be more sensible types once the ideas can actually be expressed in Swift)

Then unordered collections (Set and Dictionary) would just conform to Iterable and not Sequence, so ALL the methods on those classes would make logical sense and have well-defined behavior; no change would be needed for ordered collections.

Now, the practical matter. If this were Swift 1->2 or 2->3, I doubt there would be a significant issue with actually making this change. Unfortunately, we're well beyond that and making a change this deep is an enormous deal. So I see two ways forward.

1. We could go ahead and make this separation. Although it's a potentially large breaking change, I would argue that because the methods are ill-defined anyway, the breakage is justified and a net benefit.

2. We could try and think of a way to make the distinction between ordered and unordered "sequences" in a less-breaking manner. Unfortunately, I don't have a good suggestion for this, but if anyone has ideas, I'm all ears. Or eyes, as the case may be.

On Oct 12, 2017, at 4:24 PM, Xiaodi Wu via swift-evolution swift-evolution@swift.org wrote:

Rename Sequence.elementsEqual

• Proposal: SE-NNNN
• Authors: Xiaodi Wu
• Review Manager: TBD
• Status: Awaiting review

Introduction

The current behavior of Sequence.elementsEqual is potentially confusing to users given its name. Having surveyed the alternative solutions to this problem, it is proposed that the method be
renamed to Sequence.lexicographicallyEquals.

[...]

---

swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

[nnnnnnnn (Nate Cook)]

Right, but if you do look it up you get a bunch of things talking about sorting words.

And that’s a perfect description of the behavior. It’s a lexicographical comparison operation!

How about pairwiseEqual?

A lexicographical comparison compares not merely pairwise, but in order from the first item onwards, and stops at the first unequal pair. Proceeding in order is key information, while stopping early on false is a nice-to-have. There’s already a word for this, and it’s “lexicographical.” And the analogy is universally understood: everyone has used a dictionary or index.

I think the argument is that in this case, we're not performing an ordering, and we aren't looking at the elements using an ordered comparison. This stretches the understood use of "lexicographic", so while I think it's probably okay, it isn't a slam dunk. To me, the biggest benefit of lexicographicallyMatches is that it's obtuse, so most people will need to look at the docs to get what it actually does, which we can improve to call out the unexpected behavior with Set and Dictionary.

Nate

···

On Oct 13, 2017, at 9:59 AM, Xiaodi Wu via swift-evolution <swift-evolution@swift.org> wrote:

On Fri, Oct 13, 2017 at 09:02 Adam Kemp <adam.kemp@apple.com> wrote:

--
Adam Kemp

On Oct 13, 2017, at 5:17 AM, Xiaodi Wu <xiaodi.wu@gmail.com> wrote:

“Lexicographical comparison” is a pretty standard term, and easy to Google. We didn’t make it up for Swift :)

Since Swift names this protocol Sequence, something named “Sequence.sequenceEqual” cannot distinguish this method from ==.

On Fri, Oct 13, 2017 at 01:28 Adam Kemp <adam.kemp@apple.com> wrote:
I agree that the proposed name is a poor choice. If we just focus on the naming part, there is precedent in other languages for the name “sequenceEqual”. I think that name makes it a bit clearer that the result is whether the sequences match pair wise rather than whether they have the same elements irrespective of order. I don’t think it entirely solves the problem, but I like it a lot better than the proposed name.

--
Adam Kemp

On Oct 12, 2017, at 9:57 PM, Kevin Nattinger via swift-evolution <swift-evolution@swift.org> wrote:

–∞

1. I strongly object to the proposed name. It doesn't make it more clear to me what the method does, and is misleading at best. Among other issues, "lexicographical" is defined as alphabet order, and (1) this method applies to objects that are not Strings, and (2) this method's behavior isn't any more well-defined for Strings, so that name is even more of a lie than the original.

2. This is really just a symptom of a bigger problem. The fact that two Sets can compare equal and yet return different results for that method (among too many others) is logically inconsistent and points to a much deeper issue with Set and Sequence. It is probably about 3 releases too late to get this straightened out properly, but I'll outline the real issue in case someone has an idea for fixing it.

The root of the problem is that Set conforms to Sequence, but Sequence doesn't require a well-defined order. Since Set doesn't have a well-defined order, a significant portion of its interface is unspecified. The methods are implemented because they have to be, but they doesn't have well-defined or necessarily consistent results.

A sequence is, by definition, ordered. That is reflected in the fact that over half the methods in the main Sequence definition* make no sense and are not well-defined unless there is a well-defined order to the sequence itself. What does it even mean to `dropFirst()` in a Set? The fact that two objects that compare equal can give different results for a 100% deterministic function is illogical, nonsensical, and dangerous.

* 7/12 by my count, ignoring `_*` funcs but including the `var`

The current contents of Sequence can be cleanly divided into two groups; those that return SubSequence imply a specific ordering, and the rest do not.

I think those should be/should have been two separate protocols:

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)
}

(The comments, of course, would be more sensible types once the ideas can actually be expressed in Swift)

Then unordered collections (Set and Dictionary) would just conform to Iterable and not Sequence, so ALL the methods on those classes would make logical sense and have well-defined behavior; no change would be needed for ordered collections.

Now, the practical matter. If this were Swift 1->2 or 2->3, I doubt there would be a significant issue with actually making this change. Unfortunately, we're well beyond that and making a change this deep is an enormous deal. So I see two ways forward.

1. We could go ahead and make this separation. Although it's a potentially large breaking change, I would argue that because the methods are ill-defined anyway, the breakage is justified and a net benefit.

2. We could try and think of a way to make the distinction between ordered and unordered "sequences" in a less-breaking manner. Unfortunately, I don't have a good suggestion for this, but if anyone has ideas, I'm all ears. Or eyes, as the case may be.

On Oct 12, 2017, at 4:24 PM, Xiaodi Wu via swift-evolution <swift-evolution@swift.org> wrote:

Rename Sequence.elementsEqual

Proposal: SE-NNNN
Authors: Xiaodi Wu
Review Manager: TBD
Status: Awaiting review
Introduction

The current behavior of Sequence.elementsEqual is potentially confusing to users given its name. Having surveyed the alternative solutions to this problem, it is proposed that the method be renamed to Sequence.lexicographicallyEquals.

[...]

_______________________________________________

swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution