[swift-evolution] Dropping Comparable requirement for indices

[Dave Abrahams]

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