[swift-evolution] Dropping Comparable requirement for indices

[Xiaodi Wu]

I for one would be interested in your elaboration. Based on Dave's
comments, I'm pretty convinced that the Comparable requirement is best left
in place.
On Wed, Jul 6, 2016 at 19:19 plx via swift-evolution <
swift-evolution at swift.org> wrote:

> 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
>
>
> _______________________________________________
> swift-evolution mailing list
> swift-evolution at swift.org
> https://lists.swift.org/mailman/listinfo/swift-evolution
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-evolution/attachments/20160707/88996f3a/attachment.html>