SE-0203 — Rename Sequence.elementsEqual

You can rely on it if the Sequence comes from a source that you know does have those properties. For example, an Array has those properties so you can rely on it for an Array. But also any function that takes in a Sequence and gives you another Sequence that preserves the ordering can be fed into this function as long as you know the original source was ordered (like if it were an Array).

So, for instance, you could take an array, use map to convert it to a different array, and then use this function to compare the output to another array. That's useful. Not all the time, but it does come up.

It's not stable in that it depends on the order in which the elements were added, and could change from one run of the process to another. That means given two Set objects that have the same elements if you iterate over them as a Sequence you may get different orderings.

Some people are arguing that this means Set shouldn't implement Sequence, but the thing is Sequence doesn't have that requirement.

I disagree, but if you want to make a different proposal to rename Sequence then feel free. That's not this proposal, though. I'm sticking to the discussion about this proposal and reasons why it should or should not be accepted.

It's fine to acknowledge that, but as I wrote in the proposal, it's entirely outside the scope of this proposal and likely outside the scope of the current phase of Swift Evolution entirely.

1 Like

(post withdrawn by author, will be automatically deleted in 24 hours unless flagged)

Finally ;-)
So when we agree that Swifts definitions are in contradiction with fundamental mathematical terms:
Wouldn't it be sensible to have some patience and accept that a "real fix" won't make it into Swift 5 (probably... maybe it could be done rather quickly)?
I think it is, especially as Set now supports ==, which lessens the danger of elementsEqual drastically.

Actually, with your explanation, I don't disagree with anything you said, including the above, except that I come to a different conclusion:

If elementsEqual isn't meaningful in the general case, I would want to conclude that it shouldn't be defined without restriction.

Part of my reasoning is that there are very easy ways to make the same check (under the assumption that the sequence is well-enough-ordered for the specific problem at hand), so the function doesn't bring a lot of benefit.

I realize that's a judgement call, so it's ultimately a judgement others will have to make.

I don’t disagree with the mathematical definition. I disagree with your assumption that the word “sequence” has only one meaning, and it must be this particular one.

1 Like

Do you have a link to a definition of "sequence" where order isn't mentioned as a key characteristic?

I find the arguments about mathematical definitions not particularly useful here, and the comparisons to defining + as multiplication to be hyperbolic. Everyone acknowledges that there is a difference between a sequence and a set, but should also acknowledge that a set (or at least a Swift Set) can be used as a sequence by imposing some arbitrary order on the elements. For practical reasons, there is always going to be some way of using Set as a sequence, regardless of the mathematical definition, so the question is how should that functionality is exposed.

The current implementation just conforms it directly to Collection which seems like a reasonable option, though it results in a few possibly confusing or useless methods being available. Perhaps it would have been a little better to have a Collection view on Set and Dictionary that you had to explicitly invoke (though this makes things like for-in loops less ergonomic), or some more complex protocol hierarchy, but I don't think it's sufficiently better to justify the change, and I'm not aware of this causing much confusion outside of elementsEqual being an attractive nuisance when == wasn't available.

3 Likes

This is clearly a really bad name and warrants change. This is clearly a change that would be a positive step forward for the Swift language. I loathe the name that has been chosen but I cannot come up with anything better and this has the advantage of clarity.

Thank you to @xwu for addressing this

I don't think it's confusing that Set is a Collection - it's confusing that every Collection is a Sequence.
Obviously, an Iterator protocol would be sufficient to be used in for ... in, but it wouldn't have the methods that depend on the actual order.
Note that this not only includes elementsEqual but also reversed, starts(with:), lexicographicallyPrecedes and others.
Renaming one of those is like putting a warning sign in front of a big hole, and it may save some people from falling into that trap. But shouldn't it at least be evaluated if it's not better to fill that hole?

The only arguments against that have been "it has to be that way" and "this is out of scope" - and if that's enough to not even start a real discussion, imho Swift evolution has failed.

5 Likes

2 A set of related events, movements, or items that follow each other in a particular order.

If you iterate over a Set you will get a particular order. It may not be the order you want, but it will be some particular order. That’s a sequence.

As @jawbroken said, this argument is pointless. This proposal isn’t about Sequence.

1 Like

The Oxford dictionary supports my standpoint as well:
There's a difference between something can be transformed into a sequence and something is a sequence:
We can easily transform a Float into a SignedInteger. This works even better than turning a set into a sequence, because there are simple and transparent rules for that transformation, whereas the order of Set is a black box.
But would it make sense if Float conformed to SignedInteger?

I couldn't find a reference, but I always considered a protocol to be more than a bunch of methods, something that has a meaning.
Sequence should be an abstraction that enables us to write algorithms that allow its user to choose freely wether they want to store their items in an array, a linked list, or something else.
But when I use this abstraction (something like stepsHappenedInRightOrder), I automatically allow people to use my API with Set - although I know that this absolutely makes no sense!
Someone could use it with Set, could write some unit tests which succeed by coincidence, and end up with a program that is inherently wrong, just like the use of elementsEqual in the past.

1 Like

Every Collection has comparable and advanceable indices so they're all inherently sequenced, right?

I'm not sure I understand this at all. In what way is for-in loop itself not effectively a method that depends on the actual order. Or a next() method on an Iterator?

I'm not seeing great harm in any of these other methods. reversed and starts(with:) are probably not particularly useful on a Dictionary or Set, but I can't see it being common for them to be used incorrectly. Have you seen them causing confusion or bugs? lexicographicallyPrecedes seems slightly more likely to be misused, as someone might feed it two Dictionary or Set instances like elementsEqual, but it has an unusual and precise enough name that I'm not concerned.

Even if this discussion was starting from first principles I'm not sure it wouldn't end up with a similar design. Scanning the documentation, there's a lot of useful Sequence API that makes sense on Dictionary and Set, with a couple less useful parts and a single particularly harmful method with an unfortunate name. It might be simpler just to rename the harmful part than to have some more complex protocol redesign (e.g. somehow separating Sequence and Collection) or making things clunkier to use (e.g. hiding the Sequence and Collection conformances inside a view).

Questions - great! ;-)

Absolutely right - and because of the way our computers work, they can't even represent something that's truly unordered. The difference is wether that order exists because some programmer decided intentionally that he needs it (array, list...), or if that order happens more or less accidentally (set, dictionary).

Right as well. But the iterator doesn't care wether next() returns something that was put into its position consciously, or a random element.

But it makes a difference for the algorithms we write.

Let's take a simple example where the source of order matters:
It is quite useful that I can search a substring in a string, which is nothing but a bunch of ordered characters (let's ignore Unicode for a while ;-).
You could perform the same search in a set of characters... but why should you ever want to do so?
Would it be useful if CharacterSet had all methods of String, or would it be harmful and confusing?

4 Likes

If we rename this at all, then we should call it lexicographicallyEquals. We already have lexicographicallyPrecedes when Element is Comparable, and this is the natural relaxation of that to Equatable.

The objections in the proposal don’t carry water. In particular,

Right, the proper term is “equals”.

This is a good thing. We don’t want people reaching for this method when “==” is more appropriate.

Irrelevant. If I see two words (sequences of characters) in a foreign language, I may have no idea which one comes first alphabetically (so they are not Comparable to me) but I can still tell whether they are the same word.

That is, I can tell whether the words are lexicographically equal, even when I don’t know which one precedes the other.

And this is not just a statement about my ignorance. We can imagine a language which *does not have* a canonical ordering of its alphabet. So two different lexicographers in that language could arrange their dictionaries differently.

In that case, it is meaningless to ask if one word lexicographically precedes the other (except with respect to a provided dictionary), but it is *still meaningful* to ask if two words are lexicographically equal. Because equal words are equal in every dictionary, and distinct words are distinct.

No more so than the existing lexicographicallyPrecedes. I don’t think this is a real-world concern. A name like lexicographicallyEquals is sufficiently esoteric that people will consult the documentation to make sure they are using it correctly, unlike elementsEqual.

7 Likes

I appreciate that broader concerns have been brought up on this review thread. Those can be factored in to deciding whether a rename is warranted. However, changing Sequence or Collection in any way beyond what this proposal outlines — which is focused in the renaming of a single method — is very much beyond the scope of this proposal review. At this point such discussion is likely adding diminishing signal to the review of this particular proposal.

I recommend that broader discussion about the nature of the Sequence and Collection protocols — and any broader ideas about how they could be changed — should be taken off this thread and brought back to the general evolution discussion or pitches categories. I am recommending this not to shoot down ideas, but rather steer that discussion to the right place in the forums and allow this thread to focus on the specific proposed change in the review.

The review period for this proposal is almost over. What discussion on this thread should be focused on at this point is whether or not the method elementsEqual in Sequence should be renamed, and if so what justifies that change.

When considering the rename itself, I'd like to call out that we are beyond the point of just renaming methods just for the sake of polishing up APIs. Here are the source compatibility goals for Swift 5 (and hence Swift 4.2):

Source-breaking changes in Swift 5 will have an even higher bar than in Swift 4, following these guidelines:

  • The current syntax/API must be shown to actively cause problems for users.
  • The new syntax/API must be clearly better and must not conflict with existing Swift syntax.
  • There must be a reasonably automated migration path for existing code.

For those in favor of a rename, please keep in mind that this is the core criteria for any source-breaking change.

Thank you to all who have put so much energy into the review discussion!

6 Likes

Like you, I did not think that misunderstanding of the word "lexicographically" was a real-world concern. However, during the pitch phase, several users commented that they would not consult the documentation to make sure that they would use this method correctly; instead, they would confidently deduce that the method reorders elements before comparison. :man_shrugging:

Overly complex method names are likely to hide overly complex algorithms :-D

I can't confidently say that we should rename this method, given that the biggest cases of misuse (i.e. set equality) have been dealt with by conditional conformances. There are obviously a lot of other potential danger zones here, I don't think it is that common in reality though.

If you just look at the name in isolation, ignoring the source-compatibility and migration costs, it definitely should be renamed as it is not as clear as it could be. To that effect, I'd throw my hat in the ring in support of sequentiallyEquals(by:) or lexicographicallyEquals(by:), backing up suggestions from others upthread.

In short, I guess this is a +0.5 to the overall proposal? I apologise for sort-of sitting on the fence on this one.

2 Likes

That sounds a little bit like "security by obscurity"... afaics, the current name is absolutely fine as long as you only use the method on "real" sequences.
I don't think it's necessary to irritate people who want to compare an array with a list (I also don't think it's necessary to break their code ;-).