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 [email protected] https://lists.swift.org/mailman/listinfo/swift-evolution
