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

[Xiaodi Wu]

On Mon, Oct 16, 2017 at 15:31 Greg Parker <gparker at apple.com> wrote:

> On Oct 16, 2017, at 1:08 PM, Xiaodi Wu via swift-evolution <
> swift-evolution at swift.org> wrote:
>
> On Mon, Oct 16, 2017 at 13:15 David Sweeris <davesweeris at mac.com> wrote:
>
>
>> On Oct 16, 2017, at 09:21, Michael Ilseman <milseman at apple.com> wrote:
>>
>>
>> Sets are values. If you add, remove, or mutate any elements you have a
>> different Set and thus a potentially different ordering of elements.
>>
>>
>> From the “value semantics” PoV, yes. But from the “unordered collection
>> of values” PoV, Sets/Dictionaries, being unordered, are semantically free
>> to rearrange the in-memory ordering of their elements *without* user
>> intervention.
>>
>
> No, they are not semantically free to do so. The semantics of Collection
> forbid it, because the iteration order must be multi-pass. As long as the
> value is unchanged, the iteration order is unchanged. That is a documented,
> public guarantee of the API.
>
>
> Even if a Set value has a fixed order, a copy of that value may have a
> *different* order. How many generic algorithm implementations are going to
> be confused by that?
>

Is that so? That would be, on reflection, either a hole in the semantic
guarantees of Collection itself or a problematic conformance of Set to
Collection.

Some months ago, Dave A. and others sent out a draft about some refinements
to `Equatable`. There, we enunciated the notion that `==` should compare
equivalence in all "salient" respects, but not necessarily all publicly
observable behaviors. This is why, for instance, it is semantically
acceptable that `+0.0 == -0.0`; we are declaring that the sign of zero is
not a "salient" respect for the purposes of equivalence of floating point
types. However, this relaxed notion of equivalence/substitutability
*cannot* be acceptable for the purposes of copying a value. Take, for
instance:

```
func f<T>(x: T) {
  print(x)
}

print(-0.0) // It is *not OK* if this prints "+0.0".
```

To my simplistic thinking, a copy of an instance of a value type must be
indistinguishable from the original value with respect to all public APIs
(with the only and obvious exception of APIs that inquire into memory
location/layout). When Collection guarantees that conforming types are
multi-pass sequences, it *ought* to guarantee (if it does not do so already
on a proper interpretation of the semantic requirements) that copies are
indistinguishable in iteration order. If it did not do so, then so many
non-trivial algorithms that already operate on generic Collections are
assuming semantics that aren't guaranteed and would in fact pervasively
blow up when given a specially crafted but conformant Collection. This
would apply whether or not Sequence and Collection are modified to exclude
Set and Dictionary, as an "intrinsically ordered" collection type may not
have an intrinsic *linear* order over its elements, and there is no
semantic requirement that the *iteration order* (necessarily linear)
corresponds in any particular way to the "intrinsic order."

Now, if we agree that Collection does in fact (or ought to) guarantee the
stability of iteration order over copies, then the question is, does
today's `Swift.Set` properly meet those guarantees? If indeed, as you say,
copies of an instance of `Set` may internally rearrange its iteration order
on copy, then we do have a problem with the conformance of `Set` to
`Collection`.


>
> --
> Greg Parker     gparker at apple.com     Runtime Wrangler
>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-evolution/attachments/20171016/f3ac1a26/attachment.html>