<html><head><meta http-equiv="content-type" content="text/html; charset=utf-8"></head><body dir="auto"><div><br><br>Sent from my iPad</div><div><br>On Jul 6, 2016, at 7:33 PM, Xiaodi Wu via swift-evolution &lt;<a href="mailto:swift-evolution@swift.org">swift-evolution@swift.org</a>&gt; wrote:<br><br></div><blockquote type="cite"><div>I for one would be interested in your elaboration. Based on Dave's comments, I'm pretty convinced that the Comparable requirement is best left in place.<br></div></blockquote><div><br></div><div>+1</div><br><blockquote type="cite"><div><div class="gmail_quote"><div dir="ltr">On Wed, Jul 6, 2016 at 19:19 plx via swift-evolution &lt;<a href="mailto:swift-evolution@swift.org">swift-evolution@swift.org</a>&gt; wrote:<br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">My own 2c is to drop the comparable requirement.<br>
<br>
I can elaborate if necessary, but wanted to at least cast my “+1” for removing the requirement.<br>
<br>
&gt; On Jul 5, 2016, at 9:39 PM, Dave Abrahams via swift-evolution &lt;<a href="mailto:swift-evolution@swift.org" target="_blank">swift-evolution@swift.org</a>&gt; wrote:<br>
&gt;<br>
&gt;<br>
&gt; I've already raised the question here of whether we should weaken the<br>
&gt; requirement that Collection.Index be Comparable to merely being<br>
&gt; Equatable.<br>
&gt;<br>
&gt; Part of the motivation was to support data structures that otherwise<br>
&gt; would be expensive or impossible to implement.&nbsp; For example, with<br>
&gt; Comparable indices, you can't build a linked list that supports<br>
&gt; restructuring (e.g. insert, delete, splice) in O(1) without invalidating<br>
&gt; indices... not even an unsafe linked list with reference semantics.<br>
&gt; [While I don't think linked lists are terribly good data structures for<br>
&gt; most things, they are still useful in teaching, and it bothered me that<br>
&gt; we were ruling them out.]&nbsp; Even if you take away the index invalidation<br>
&gt; restriction, you have to store a counter in the index, which is an awkward inefficiency.<br>
&gt; Supporting Comparable indices for a tree data structure requires<br>
&gt; encoding the path from the root to the node.&nbsp; It's only one or two words<br>
&gt; in practice, but it's another awkward inefficiency.<br>
&gt;<br>
&gt; Over the weekend, I tried lifting the restriction to see what kind of<br>
&gt; effect it would have on the standard library.<br>
&gt; <a href="https://github.com/apple/swift/pull/3325" rel="noreferrer" target="_blank">https://github.com/apple/swift/pull/3325</a><br>
&gt;<br>
&gt; Although I *had* been leaning strongly toward making this change, having<br>
&gt; looked at the effects, I am now more ambivalent:<br>
&gt;<br>
&gt; * A Range&lt;T&gt;, where T is not Comparable, could be constructed with any<br>
&gt;&nbsp; pair of Equatable T instances.&nbsp; We'd only detect that the Range may be<br>
&gt;&nbsp; invalid when T happened to also be Comparable.&nbsp; However, the fact that<br>
&gt;&nbsp; you are creating a Range already sort of implies an underlying<br>
&gt;&nbsp; ordering.<br>
&gt;<br>
&gt; * A Collection with non-Comparable indices still imposes an ordering<br>
&gt;&nbsp; upon the indices.<br>
&gt;<br>
&gt; * In a Collection with Comparable indices, the ordering implied by &lt;<br>
&gt;&nbsp; needs to match the ordering of indices in the collection.&nbsp; Otherwise,<br>
&gt;&nbsp; there would be no way to form Ranges (for use in slicing, for example)<br>
&gt;&nbsp; without causing a trap.&nbsp; This is *weird*!&nbsp; There's little precedent<br>
&gt;&nbsp; for imposing stronger semantic requirements on an associated type if<br>
&gt;&nbsp; it conforms to a particular protocol (Comparable in this case), except<br>
&gt;&nbsp; where the requirement is part of the protocol.<br>
&gt;<br>
&gt; Also, Dmitri reminded me that even with a Comparable requirement on<br>
&gt; indices, there is still no problem converting an equatable iteration<br>
&gt; state into an index; you just need to augment it with an integer<br>
&gt; counter.&nbsp; So it's still trivial to create a Collection from nearly<br>
&gt; everything that is today a multipass Sequence.&nbsp; It does make indexing<br>
&gt; slightly more expensive, but it's likely we'd optimize that overhead<br>
&gt; away in many critical situations.<br>
&gt;<br>
&gt; Anyway, the thoughts of the community on this topic would be interesting<br>
&gt; to us.&nbsp; We need to make a decision about this very soon.<br>
&gt;<br>
&gt; Thanks!<br>
&gt;<br>
&gt; --<br>
&gt; Dave<br>
&gt;<br>
&gt; _______________________________________________<br>
&gt; swift-evolution mailing list<br>
&gt; <a href="mailto:swift-evolution@swift.org" target="_blank">swift-evolution@swift.org</a><br>
&gt; <a href="https://lists.swift.org/mailman/listinfo/swift-evolution" rel="noreferrer" target="_blank">https://lists.swift.org/mailman/listinfo/swift-evolution</a><br>
<br>
<br>
_______________________________________________<br>
swift-evolution mailing list<br>
<a href="mailto:swift-evolution@swift.org" target="_blank">swift-evolution@swift.org</a><br>
<a href="https://lists.swift.org/mailman/listinfo/swift-evolution" rel="noreferrer" target="_blank">https://lists.swift.org/mailman/listinfo/swift-evolution</a><br>
</blockquote></div>
</div></blockquote><blockquote type="cite"><div><span>_______________________________________________</span><br><span>swift-evolution mailing list</span><br><span><a href="mailto:swift-evolution@swift.org">swift-evolution@swift.org</a></span><br><span><a href="https://lists.swift.org/mailman/listinfo/swift-evolution">https://lists.swift.org/mailman/listinfo/swift-evolution</a></span><br></div></blockquote></body></html>