[swift-evolution] Dropping Comparable requirement for indices

[Matthew Johnson]

Sent from my iPad

> On Jul 6, 2016, at 7:33 PM, Xiaodi Wu via swift-evolution <swift-evolution at swift.org> wrote:
> 
> 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.

+1

>> 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
> _______________________________________________
> 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/20160706/4d169691/attachment.html>