[swift-evolution] [Review] SE-0065 A New Model for Collections and Indices

[Dave Abrahams]

Thanks for your comments, Brent!

on Sun Apr 10 2016, Brent Royal-Gordon <swift-evolution at swift.org> wrote:

>> 	https://github.com/apple/swift-evolution/blob/master/proposals/0065-collections-move-indices.md
>
> Some questions and comments:
>
>> 		• Two for ranges that additionally conform to
>> RandomAccessCollection (requiring bounds that are Strideablewith
>> Stride conforming to Integer): CountableRange<T> and
>> CountableClosedRange<T>. These types can be folded into Range and
>> ClosedRange when Swift acquires conditional conformance capability.
>
> Does this mean that once we have conditional conformances,
> HalfOpenRangeProtocol and ClosedRangeProtocol will most likely go
> away?

I'm not sure, honestly.

>> We also introduce three new protocols:
>> 
>> 	• RangeProtocol
>> 	• HalfOpenRangeProtocol
>> 	• ClosedRangeProtocol
>> 
>> These protocols mostly exist facilitate implementation-sharing among
>> the range types, and would seldom need to be implemented outside the
>> standard library.
>
> If these types are for implementation sharing, should they be
> underscored to discourage their use? Or is the position they occupy in
> the type hierarchy important because Range and ClosedRange will
> eventually occupy them?

Underscoring hides names from users completely, and IMO that would not
be appropriate here.  If we underscored them, it would be mysterious
where an implementation of various methods came from.

> It seems to me that RangeProtocol is unlike the other two in that it's
> a sensible thing to constrain a parameter to. Does the
> "implementation-sharing" comment not really apply to it? 

That could be argued either way, I think.  One can't know for sure
without doing a redesign using a hypothetical more-capable Swift
language, which we don't have today.

> On the other hand, it's not like the SubSequence subscript now takes a
> RangeProtocol. Should it?

No; subscript can't be generic (language limitation).

> (Has any thought been given to allowing you to close protocols to
> outside conformances the way that resilience seems to suggest we'll
> eventually allow you to close classes?)

I don't know who else might have thought about it, but personally I
don't think we want to do that.

>> • Two for general ranges (whose bounds are Comparable): Range<T> and
>> ClosedRange<T>. Having a separate ClosedRange type allows us to
>> address the vexing inability of the old Range to represent a range
>> containing the maximal value of its bound.
>
> I notice that ClosedRange uses a ClosedRangeIndex to, essentially, add
> one extra value for "larger than all values of this type". Could this
> solution be applied to Range to allow us to unify Range and
> ClosedRange, or are there other obstacles to that?

Performance is one such obstacle.  Half-open ranges should be your go-to
range, and can be implemented more simply.  There's also the problem of
how to decide whether the upper bound is part of the range.  I'd rather
not have a dynamic check to select the comparison.

> (There likely are. I just wanted to make sure the idea wasn't left unexplored.)
>
>> func successor(of i: Index) -> Index
>
> Two things:
>
> 1. I would really like a version of this which returns Optional and is
> guaranteed to go `nil` once it hits `endIndex`. 

The primary question to answer when exploring this idea is, IMO, “what
does that do to the code in algorithms?”  I can't imagine writing binary
search, partition, or rotate if I had to check for nil every time I
moved an index.

> There can be a non-optional version too, or it might even be a feature
> of the `index` family of methods instead of `successor` itself, but I
> think it would be valuable to let the collection worry about the
> bounds check.

Why would that be valuable?

> It seems silly to check the index before calling `successor(of:)` when
> `successor(of:)` is going to immediately perform the same check again
> as a precondition.

Preconditions are not necessarily checked.  We don't promise to trap
every precondition violation.  We promise memory and type safety in the
absence of data races, and some precondition failures will trap in order
to ensure that.  Others will trap, where we think it is affordable, just
to provide a better programmer experience.

> (Actually, in general, I'm a little bit dismayed that the collection
> API does so little to help you include bounds checks in your
> code. Especially when iterating through a collection, bounds checks
> are absolutely mandatory, and the collection API's solution to the
> problem is "eh, just use `<`, it's not like you might mess something
> like that up".)

What do you mean?  Could you show an example of what you think should be
better supported?

> 2. There is a very strong parallel between this method and a
> generator's `next()` method—the generator's `next()` calls
> `successor(of:)` to get the index it should use—which makes me wonder
> if this method should also be called `next(_:)` instead of
> `successor(of:)`. 

We had that in the code for a while. Certain people disliked it a lot.
Personally I think successor(of:) is still better, considering that
these methods end up getting thrown into the mix with all the other
methods on collections (e.g. sort()).

> On the other hand, I have no good suggestion for a
>
>> func index(n: IndexDistance, stepsFrom i: Index) -> Index
>
> Oof, I am really not a fan of this name. `steps` is sort-of a label on
> the `n` parameter, but it's attached to `i`. 

Yes, it's an awkward thing to name.  Better suggestions most welcome.

> Other collection APIs use `distance`, not `steps` (although "steps"
> does appear in the documentation of the `Distance` associated
> type). `index` puts it in a method family with `index(predicate:)` and
> `index(of:)`, but those two are user-facing while this one is part of
> the collection API. Even the word `index` itself is redundant with the
> method return type.
>
> I do understand how this is kind of parallel to `index(of:)` and
> `index(predicate:)`, in that they all return an index calculated from
> the parameters, but I think these methods are more different than they
> are similar.
>
> Compared to this:
>
> 	collection.index(5, stepsFrom: i)
>
> I would prefer any of these (ordered from least favorite to most):
>
> 	collection.index(distance: 5, from: i)

I'm OK with this one, but am not sure it's an improvement over the
proposal.  I'd like to hear other peoples' arguments on this.

> 	collection.index(5, from: i)

I don't think this one reads clearly enough.

> 	collection.traveling(5, from: i)
> 	collection.striding(5, from: i)
> 	collection.advancing(i, by: 5)

None of the “ing” names work, IMO because that suffix suggests you're
returning a modified version of the receiver.

> A word on `striding(_:from:)` appearing in that list: Although
> redesigning Strideable is not directly in scope for this proposal,
> I've noticed that our discussions on modernizing Strideable seem to be
> trending towards the idea that it operates on collections (or rather,
> on an as-yet-unnamed supertype of `BidirectionalCollection` or
> `RandomAccessCollection`) and strides by repeatedly calling a method
> with the same semantics as this one. Thus, there seems to be an
> intimate connection between this operation and Strideable. I think we
> ought to choose a method name which suits that, and I don't think
> `index` is it.
>
>> func index(n: IndexDistance, stepsFrom i: Index, limitedBy limit: Index) -> Index
>
> I have a few issues with this API.
>
> 1. As aforementioned, I'm not a big fan of using `index` as the base method name.
>
> 2. This method can move the index either forwards or backwards, but
> only one limit is specified. Would we be better off having the `limit`
> be a range?

That would add a cost for checking that one doesn't want to pay in
algorithms that need this method.

> 3. What is the use case for returning the `limit` instead of returning
> the fact that we crossed it? I have a hard time thinking of a case
> where I would want to just bump up against the limit and use it rather
> than *detect* that I've hit the limit (which would probably call for a
> return type of `Index?`). Are there common needs that I'm just not
> thinking of? 

Sure, for example

  x[i..<x.index(n, stepsFrom: i, limitedBy: x.endIndex)].sort()


> Should we offer both?

Definitely not, IMO!  They are utterly redundant, are they not?

>
>> 	* What is your evaluation of the proposal?
>
> Despite my criticisms, this is fundamentally a very good design. It
> will not only improve the language, it will also open the door to
> further improvements.
>
>> 	* Is the problem being addressed significant enough to warrant a change to Swift?
>
> Yes. I believe this change is complicating in the short run but
> actually simplifying in the long run, eliminating concepts like the
> Index protocols which represented several overlapping semantics.
>
>> 	* Does this proposal fit well with the feel and direction of Swift?
>
> Yes.
>
>> 	* If you have you used other languages or libraries with a similar feature, how do you feel that this proposal compares to those?
>
> Nothing with a collection design as rich as Swift's.
>
>> 	* How much effort did you put into your review? A glance, a quick reading, or an in-depth study?
>
> Somewhere between the latter two. I wouldn't call it in-depth when
> it's such a big change, but I feel like I have too much background to
> say it's a quick reading, either.

-- 
Dave