<div dir="ltr"><div><br><div class="gmail_quote"><div dir="auto">On Mon, Oct 16, 2017 at 15:31 Greg Parker <<a href="mailto:gparker@apple.com" target="_blank">gparker@apple.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div style="word-wrap:break-word;line-break:after-white-space"><div><blockquote type="cite"><div>On Oct 16, 2017, at 1:08 PM, Xiaodi Wu via swift-evolution <<a href="mailto:swift-evolution@swift.org" target="_blank">swift-evolution@swift.org</a>> wrote:</div><div><div><br><div class="gmail_quote"><div dir="auto"><blockquote type="cite"></blockquote></div></div></div></div></blockquote><div><div><div class="gmail_quote"><div dir="auto"><blockquote type="cite">On Mon, Oct 16, 2017 at 13:15 David Sweeris <<a href="mailto:davesweeris@mac.com" target="_blank">davesweeris@mac.com</a>> wrote:<br></blockquote></div></div></div></div></div></div><div style="word-wrap:break-word;line-break:after-white-space"><div><blockquote type="cite"><div><div><div class="gmail_quote"><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="auto"><br><div>On Oct 16, 2017, at 09:21, Michael Ilseman <<a href="mailto:milseman@apple.com" target="_blank">milseman@apple.com</a>> wrote:<br></div><blockquote type="cite"><div><div><br></div><div>Sets are values. If you add, remove, or mutate any elements you have a different Set and thus a potentially different ordering of elements.</div></div></blockquote><br></div></blockquote></div></div></div></blockquote></div></div><div style="word-wrap:break-word;line-break:after-white-space"><div><blockquote type="cite"><div><div><div class="gmail_quote"><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="auto"><div>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 <i>without</i> user intervention.</div></div></blockquote></div></div></div></blockquote></div></div><div style="word-wrap:break-word;line-break:after-white-space"><div><blockquote type="cite"><div><div><div class="gmail_quote"><div dir="auto"><br></div><div dir="auto">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.</div></div></div></div></blockquote></div></div><div style="word-wrap:break-word;line-break:after-white-space"><div><blockquote type="cite"><div><div><div class="gmail_quote"></div></div></div></blockquote><br></div><div><div>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?</div></div></div></blockquote><div dir="auto"><br></div><div dir="auto">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.</div><div dir="auto"><br></div><div>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:</div><div><br></div><div>```</div><div>func f<T>(x: T) {</div><div> print(x)<br></div><div>}</div><div><br></div><div>print(-0.0) // It is *not OK* if this prints "+0.0".<br></div><div>```</div><div><br></div><div>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."</div><div><br></div><div>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`.<br></div><div dir="auto"><br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div style="word-wrap:break-word;line-break:after-white-space"><div><div></div><div><br></div><div><br></div></div></div><div style="word-wrap:break-word;line-break:after-white-space"><div>-- </div><div>Greg Parker <a href="mailto:gparker@apple.com" target="_blank">gparker@apple.com</a> Runtime Wrangler</div><div><br></div><div><br></div></div></blockquote></div></div></div>