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

[Xiaodi Wu]

On Sun, Oct 15, 2017 at 2:32 PM, Kevin Nattinger <swift at nattinger.net>
wrote:

> […]
> Sets, as a mathematical concept, have no intrinsic order. However,
> instances of `Set`, which can be iterated over, *do* have at least one
> order which can be said to be intrinsic in the following sense: as long as
> iteration is possible, no API design can prevent that order from being
> observed and associated with the instance. Put another way, if you can use
> an instance of a type in a for...in loop, intrinsic to that functionality
> is a publicly visible order.
>
>
> You keep saying this, I keep saying it’s only a technical “order” that is
> an implementation detail
>

You keep saying it's an implementation detail, which it emphatically is
*not*. It's a *public guarantee* by the protocol that you can use an
instance of `Set` in a `for...in` loop, thereby exposing a publicly visible
order. An implementation detail is something that could go away with an
alternative implementation. By contrast, no implementation that permits an
instance of `Set` being iterated over in a `for...in` loop can avoid
exposing at least one publicly visible order, because it's not a matter of
implementation. Put another way, by allowing iteration, a type necessarily
exposes at least one publicly visible order and thereby models a sequence
in at least one way.


> and can’t be relied upon for anything and so we shouldn’t provide methods
> that rely on it. I think this part of the discussion has reached the “agree
> to disagree” stage.
>
> […]
>>
> You’re a fan of the principal of least surprise. Tell me, which would be
>> less surprising: Set.dropFirst() actually drops a random element, or Set
>> doesn’t have a dropFirst()? And if you think dropFirst() removing an
>> element at random is not surprising, please explain why.
>>
>
> I think Set.dropFirst removing the first element that I observe on
> iteration is the least surprising answer, because Swift tells me that the
> stdlib Set models a set but that it is also a sequence.
>
>
> Your logic is backwards. You’re saying it’s “least surprising” because
> that’s how it’s currently implemented, not that it should be implemented
> that way because it’s least surprising.
>

No, I'm saying it's least surprising because any type that supports
iterated access thereby exposes an order--not as an implementation detail
but as a matter of public API--and in the absence of any other order,
"first" must refer to that order so exposed.

> […]
>>>>
>>>>
>> And that’s PRECISELY why lexicographicallyEqual does not make sense to
>> apply to unordered sets. There is no lexicographical comparison possible,
>> so why do you keep insisting they should have a method that falsely claims
>> to lexicographically compare them?
>>
>
> I agree! It doesn't make sense if no comparison is possible! But Swift
> tells me that a `Set` is a `Sequence`!
>
>
> You keep making the circular argument that a Set should do things because
> it currently does them. If you want to argue against changing things, argue
> that things shouldn’t be changed, not that the current implementation is
> correct because it is the current implementation.
>

No, I'm arguing that `Set`, by supporting iterated access, is not wrong to
conform to a protocol called `Sequence` because it does have an intrinsic
and publicly observable order, which is not an accident of a particular
implementation but is inherent to any type that supports iterated access.
Now, whether it's the *best choice* to conform `Set` to `Sequence` and
offer order-dependent functions is a matter of taste, but it isn't *wrong*.

> […]
> You will always have to account for this possibility, because Swift's
> `Equatable` explicitly allows "special values" to be not equal to
> themselves. This is, at least in part, in order to accommodate the IEEE
> decree that NaN != NaN:
>
>
> ```
> let x = [Double.nan]
> x.elementsEqual(x) // false
> ```
>
>
> NaN is special, one-shot and unordered sequences are not. Unless you think
> that all unordered and single-pass sequences should compare false for
> `elementsEqual`, this is irrelevant for any sequence that doesn’t contain
> NaN and well-defined (false) for any that does.
>

Certainly, not all single-pass sequences should compare false to
themselves, but some should: for instance, an infinite single-pass stream
of all 1's should compare true to itself, but an infinite single-pass
stream of alternating 1's and 0's should compare false to itself. If you
write generic code that calls `elementsEqual`, it is pervasively incorrect
to test for identity by assuming that elementsEqual will return true on
reflexive comparison. NaN is only one of many reasons why such code would
blow up.


>
> Changing this behavior is way beyond the scope of this thread (and has
> been the topic of hours (actually, weeks and weeks) of fun on this list
> previously).
>
>
> Yes, I’ve seen the discussion on NaN and Comparable. It’s not the same
> discussion.
>
> […]
>
>> It would be better to say that the iteration order is well-defined. That
>>> will almost always mean documented, and usually predictable though
>>> obviously e.g. RNGs and iterating in random order will not be predictable
>>> by design.
>>>
>> Wouldn't it then suffice to document, say, that a set's iteration order
> is the insertion order?
>
>
> Now this actually gave me pause. I guess it does match what I said, but I
> still take issue with the fact that two Sets could compare `==` but not
> `elementsEqual`. I think that defining iteration order as insertion order
> adds a piece of publicly documented state that goes beyond what a Set
> really is. What you describe is really an OrderedSet, just without the
> random-access manipulation.
>

a) There is no semantic requirement on the part of `==` to be equivalent to
an elementwise comparison when it is defined on a collection; in fact, one
could imagine that some exotic sequence might legitimately define equality
in a way that has nothing to do with elementwise comparison. Put another
way, `==` returning `true` does not imply `elementsEqual` returning `true`,
and `elementsEqual` returning `true` does not imply `==` returning `true`.
This applies equally to ordered collections and is independent of the
question of how to model unordered collections.

b) You keep writing that some Foo is really some Bar, but those are really
just names. What would be the harm if Swift's `Set` indeed simply models an
ordered set without random-access manipulation?

I’ll have to mull this over to see if I can come up with a coherent and
> (more) specific requirement for what makes an Iterable a Sequence, since
> clearly “documented” isn’t enough.  Perhaps something along the lines that
> any two Sequences that compare equal must iterate the same.
>
> […]
> Apple documentation calls this one of the "order-dependent" methods. It is
> surely acceptable for a type that conforms to an order-dependent protocol
> to have methods that are order-dependent; they do, however, have to be
> clearly order-dependent to avoid confusion on unordered types.
>
>
> I’m not clear on what you’re trying to get across here. It seems you’re
> saying unordered types shouldn’t have order-dependent methods, which is
> exactly what I’ve been arguing.
>

No, I'm saying, essentially, that there are no truly unordered types in
Swift; `Set` and `Dictionary` lead double lives modeling unordered
collections on the one hand and ordered collections on the other. The
order-dependent methods can continue to exist; they just need to be clearly
named so that users know when they're using an instance of `Set` in the
manner of an unordered collection and when they're using an instance of
`Set` in the manner of an ordered collection.


>
>  [...]
>
>> Then there are all the methods that imply a specific order of iteration.
>> If the “sequence” is unordered, who knows what you’ll get? It is incredibly
>> easy for an engineer to write a method that implicitly relies on a passed
>> sequence being intrinsically ordered and another engineer to pass it an
>> unordered “sequence.”  The first engineer could neglect to document the
>> dependency, or even not notice it; or the second engineer could just fail
>> to read the documentation thoroughly enough.  There is currently no way for
>> the compiler to enforce passing only an object that is (or at least claims
>> to be) intrinsically ordered.
>>
>
> It is also incredibly easy for such an engineer to use `for...in` instead
> to accomplish the same task, generic over ordered and unordered sequences
> whatever you name such distinguished protocols. I think your beef really
> still boils down to Set being compatible with `for...in` at all, as Jon
> acknowledges.
>
>
> Not providing ordered functions for unordered collections makes the
> developers think about what they actually need. If any object will do, they
> can use for…in, .makeIterator().next(), or an `anyObject()` we provide as a
> convenience. If they actually need the first from some specific order, it’s
> a reminder they need to sort the objects first to get the right one.
>

The whole point of protocol hierarchies is to enable useful generic
algorithms. Here, the purpose of having a protocol that unites both ordered
and unordered collections is to permit the writing of generic algorithms
that operate on both; a user would want the first item from an ordered
collection or an arbitrary item (but the same one on multiple passes) from
an unordered collection. The name for that is currently `first`. Brent
demonstrated a trivial one-line example of such a use.

That’s particularly useful for functions that actually need an ordered
> sequence; using OrderedSequence instead of Iterable (just as placeholders)
> would be a firm reminder not to pass in an unordered collection.
>
> […]
>>
>>
> As I said, you're welcome to tackle the protocol hierarchy, but I really
> doubt it's within the realm of realistic endpoints for Swift 5. I'm just
> trying to propose a narrowly targeted pragmatic solution to one specific
> limited harm that might be deliverable by the next point release. As a
> great man once said, Swift is a pragmatic language.
>
>
> If you want a pragmatic solution, fix the bug in functionality, don’t try
> and rename the method to something obscure to cover it up.
>

What I'm arguing is that there *is no bug in functionality*, only a naming
problem. It is true that the current protocol hierarchy would not be my
preferred design, but that's a matter of taste in terms of, again, where to
draw the line between too much modeling or not enough. But that's not
tantamount to a *bug*.


> If you want to limit the harm, override `equalObjects` on unordered
> sequences to use `==` (very strongly preferred), or always `false` (less
> desirable, but at least consistent)
>
> […]
>>
>>
> The Swift stdlib deliberately eschews modeling everything in protocol
> hierarchies with the highest level of granularity. There's some fudging,
> deliberately, to find a happy medium between obtuse and approachable,
> between too many/too specialized and not enough. For example, I pushed for
> protocols such as `Field` and `Ring` at the top of the numeric hierarchy,
> which might allow complex number types to slot into the hierarchy more
> sensibly, for example. But we have a compromise protocol `Numeric` which
> doesn't quite have the same guarantees but is much more approachable.
> Notice that we also don't break down numeric protocols into `Addable`,
> `Subtractable`, etc.; we also have that fudge factor built into
> `Equatable`, as I mentioned.
>
>
> Eh, one or two corner cases on a protocol is probably fine. What’s not
> fine is over half (Sequence) or almost all (Collection) the methods not
> being applicable.  There is a very clear gap there. We don’t need to fix
> everything, but this is something that can and should be addressed.
>

This would be based on the premise that an instance of `Set` has no
intrinsic order; I disagree for the reasons above.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-evolution/attachments/20171015/0ef0a2d6/attachment.html>