[swift-evolution] Dropping Comparable requirement for indices

[plx]

My own 2c is to drop the comparable requirement.

I can elaborate if necessary, but wanted to at least cast my “+1” for removing the requirement.

> On Jul 5, 2016, at 9:39 PM, Dave Abrahams via swift-evolution <swift-evolution at swift.org> wrote:
> 
> 
> 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
> swift-evolution at swift.org
> https://lists.swift.org/mailman/listinfo/swift-evolution