> On Jul 5, 2016, at 7:39 PM, Dave Abrahams via swift-evolution > <swift-evolution@swift.org> wrote: > > 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've wanted the Index protocols to be Comparable since the Swift 1 days. (Apple people, see rdar://17768142; non-Apple people, I was looking to measure distance and, under the old indexing model, the inability to determine which index came later was one of several impediments.) Going back to the beginning: > 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. You *can* have O(1) restructuring without index invalidation if you're willing to tolerate O(n) comparisons; you just walk forward from the left-hand side and return `true` if you encounter the right-hand side before reaching the end. I'm not certain, but I think there's a three-way tradeoff here: you can have any two of fast restructuring, fast comparisons, and always-valid indices. In general, though, `Collection` is not very good at modeling linked lists—for one thing, it can't model a value-typed linked list without enormous index invalidation issues. I can't quite bring myself to worry too much about linked-list handling here. > * 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. Such a Range can't actually test whether a given value is *in* the range. That basically just makes it a glorified typealias for `(lowerBound: Bound, upperBound: Bound)`. A Range without Comparable is a type without any semantics. > * A Collection with non-Comparable indices still imposes an ordering > upon the indices. And it also still needs to be able to *test* the ordering of indices. For instance, `distance(from:to:)` is a bit difficult to implement (at least in `BidirectionalCollection`) if you can't tell which index comes earlier in the collection. -- Brent Royal-Gordon Architechies _______________________________________________ swift-evolution mailing list swift-evolution@swift.org https://lists.swift.org/mailman/listinfo/swift-evolution