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