> 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.
So far in Swift 3 I've enjoyed the Comparable requirement on indices—it's much easier to perform bounds checks in collection algorithms as a result. However, I haven't tried implementing linked-lists or other non-linear collections since the Comparable requirement was added. I can see that requirement being a significant burden, particularly in a structure like a self-balancing tree, where managing index comparability could grow quite cumbersome. > 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. This was exactly how Ranges worked from Swift's public launch up until the collections-move-indices changes landed, so it doesn't seem like a major problem to bring this behavior back. If we can promise better/faster bounds checking for Comparable indices, hopefully most collection authors would opt into that whenever possible. > * 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. This sounds like an argument *for* removing the Comparable requirement. Is the issue that it's difficult to guarantee that the < ordering matches the collection, or is the issue that even if you drop the Comparable requirement, there's an implicit comparability anyway? > 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. I don't know that I've helped at all, but those are my thoughts. Thanks! Nate _______________________________________________ swift-evolution mailing list swift-evolution@swift.org https://lists.swift.org/mailman/listinfo/swift-evolution