[swift-evolution] Dropping Comparable requirement for indices

[plx]

> On Jul 6, 2016, at 7:33 PM, Xiaodi Wu <xiaodi.wu at gmail.com> 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.

I am short on time (and will remain so for several more weeks) so this should be seen as essentially a fire-and-forget message. 

I'll preface the rest with the disclaimer that I don't think any of the assessments already made are *wrong* on the facts...I simply (a) disagree on what to make of them and also (b) think there is more cost to requiring  `Comparable` than has been noted so far.

For (a), I agree with the following pair of facts:

- there are "collections" for which the "natural" choice of index is awkward to make `Comparable` (thus making conformance to `Collection` awkward)...
- such "non-comparable indices" can easily be made comparable when needed, e.g. by stapling an `Int` onto each "natural" index (or via some similar augmentation)

...but to me this argues in favor of dropping the requirement:

- dropping it allows more "collections" to become proper `Collection`s (while still using the "natural" index)
- when you specifically need comparable indices, they are easy to add (so why not *not* pay for comparability except when you specifically need it)

For (b), I think that the long-term costs of techniques like "`Int`-stapling" are actually rather more severe than just the overhead of the stapled-on `Int` (etc.); to illustrate this, consider linked-lists, since they've already been brought up.

I'll state without proof that the following are reasonable:

- if we only need `Equatable` indices:
  - the list nodes are the natural choice of "index"
  - the list nodes are *robust* indices (very few updates invalidate them)
- if we instead need `Comparable` indices:
  - the easiest index is a pair like `(list-node, counter)`
  - these indices are *fragile* indices (invalidated after most updates)

...and proceed to my point:

It's not hard to imagine at some point introducing a protocol for a mutable collection with *robust* indices -- e.g., behaving like the "natural" indices we could get away with here if we only needed `Equatable` -- and providing either (or both):

- improved generic implementations of standard mutation operations
- additional mutation operations that are only practical with robust indices

...and the unfortunate consequence of the `Comparable`-index requirement is that our linked-list would **not** be able to adopt such a protocol -- and benefit from such algorithms, etc. -- b/c that requirement means that the `Index` it will expose in a generic setting is the more-fragile, “stapled index” instead of the more-robust, “natural index” we could have used otherwise. 

This has been discussing linked-lists but I think it generalizes; e.g. for other things that “could be ‘collections’” without the `Comparable`-`Index` requirement, you can easily make indices that *do* satisfy the `Comparable` requirement…at the cost of winding up with comparatively-fragile indices that are a bit pessimal for use with mutation operations. I’ll speculate that the issues being alluded-to for trees are roughly similar: it’s not that it’s hard to make the tree indices comparable, it’s that there’s no good way to do that without making the resulting indices “artificially” fragile.

And so on. 

So to conclude, I don’t really disagree that the issues raised by non-comparable indices are real issues, but I *do* think the cost/benefit analysis should include the cost of having "locked-in" the use of fragile, easily-invalidated indices vis-a-vis what might otherwise have been used. It’s not amazingly convincing without more-concrete examples, but this is all I have time for.