[swift-evolution] Dropping Comparable requirement for indices

Dave Abrahams dabrahams at apple.com
Thu Jul 7 17:45:55 CDT 2016

on Wed Jul 06 2016, David Sweeris <swift-evolution at swift.org> wrote:

>> On Jul 6, 2016, at 20:41, Dave Abrahams via swift-evolution <swift-evolution at swift.org> wrote:
>> There is no way, AFAIK, to implement important algorithms like rotate
>> binarySearch and several others, without having some representation of
>> position within a collection.
> Do you need indices to be explicitly comparable for that, or will
> simply being able to test for equality and being within a "range"
> work? 

Equality is all that's needed for most of these algorithms.
I don't know what you mean about testing for being within a "range."
Doing that efficiently comes down to index ordering comparison AFAICT.

> I realize that in most cases, testing an index for being in a range
> implies comparable, but what about multi-dimensional indices?
> Comparison isn't well defined for, say, 2D points, but in theory all
> the points within a circle or something could be the indices for
> something.

If you have to do something like that, you wrap them so they're ordered
by angle or something.

Multi-dimentionsal indices only fit into our model of collection insofar
as they are linearizable.  The only place I've seen this come up is in
linear algebra libraries, where indices in matrices have a linear order
that depends on storage format, and .row and .column properties that you
can read to get the two-dimensional position.


More information about the swift-evolution mailing list