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.
Agreed, and that's basically what motivated the investigation of
dropping the Comparable requirement. One thing to remember, though:
this ability to avoid invalidating indices would not apply to all
collections. The most-common (and usually best)
RangeReplaceableCollection, Array, can't support it.
The ability to maintain a stable notion of “position” in the collection
after it is restructured is a special property that only really applies
to “node-based” collections where each element gets a separate node.
Individual data structures with this property are free to provide their
own *additional* Index-like type that is less fragile.
Are there any generic algorithms over such data structures that take
advantage of index stability? I don't know of any. If they exist, it's
a potential concern for the protocol design. If they don't, it's
something we can just add to individual concrete types.
The concern that comparability may impose a performance penalty on some
data structures is a bigger one for me. However, since node-based
collections tend to have terrible locality-of-reference, I feel sort of
OK about the idea that people who care about performance will be using
data structures containing at least some contiguous allocations
(e.g. Deques, B+ trees...)
I find either decision to have some distasteful effects on the design,
but at the moment I think the effects of dropping the Comparable
requirement are worse.
It’s not amazingly convincing without more-concrete examples, but this
is all I have time for.
Thanks for making some time despite your busy schedule!
···
on Fri Jul 08 2016, plx <swift-evolution@swift.org> wrote:
On Jul 6, 2016, at 7:33 PM, Xiaodi Wu <xiaodi.wu@gmail.com> wrote:
--
Dave
