[swift-evolution] Dropping Comparable requirement for indices

Matthew Johnson matthew at anandabits.com
Wed Jul 6 06:46:32 CDT 2016

Sent from my iPad

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

Dmitri's suggestion removes the primary concern I had about retaining the Comparable requirement if we require all multi pass sequences to conform to Collection.  (I was focused on comparability of the iteration state itself and didn't consider other ways to meet that requirement)

I agree that the points you list above seem to point in the direction of retaining the Comparable requirement.

> Thanks!
> -- 
> Dave
> _______________________________________________
> swift-evolution mailing list
> swift-evolution at swift.org
> https://lists.swift.org/mailman/listinfo/swift-evolution

More information about the swift-evolution mailing list