On Mon, Oct 16, 2017 at 15:31 Greg Parker <gpar...@apple.com> wrote: > On Oct 16, 2017, at 1:08 PM, Xiaodi Wu via swift-evolution < > swift-evolution@swift.org> wrote: > > On Mon, Oct 16, 2017 at 13:15 David Sweeris <daveswee...@mac.com> wrote: > > >> On Oct 16, 2017, at 09:21, Michael Ilseman <milse...@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 gpar...@apple.com Runtime Wrangler > > >
_______________________________________________ swift-evolution mailing list swift-evolution@swift.org https://lists.swift.org/mailman/listinfo/swift-evolution