[swift-evolution] Dropping Comparable requirement for indices

[Dave Abrahams]

on Wed Jul 06 2016, Brent Royal-Gordon <brent-AT-architechies.com> wrote:

>> 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. 

Yeah, but O(1) is a basic requirement of Comparable.  I consider that to
be inviolable.

> 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.

Yes, I'm not too worried about it either.  I'm more concerned about
trees, FWIW.

>> * 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)`. 

Yes.

> A Range without Comparable is a type without any semantics.

Practically speaking, yes.

>> * 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.

Well, you can make it a precondition that the indices are in order.
That's what Swift 2 did (and what C++ does with its forward and
bidirectional iterators).  It is certainly nice that Swift 3 lifts that
restriction.

-- 
Dave