[swift-evolution] Dropping Comparable requirement for indices

[Brent Royal-Gordon]

> On Jul 5, 2016, at 7:39 PM, Dave Abrahams via swift-evolution <swift-evolution at 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