[swift-evolution] [Pre-proposal] Forward/Reverse Only Indexing Methods

[Dave Abrahams]

Sorry, I can't seem to find the original message.

on Tue May 31 2016, Thorsten Seitz <swift-evolution at swift.org> wrote:

>> Am 31.05.2016 um 14:46 schrieb Haravikk via swift-evolution
>> <swift-evolution at swift.org>:
>> 
>> So for Swift 3 we’re going to have the great new indexing model that
>> performs index manipulation through the collection to which an index
>> belongs.
>> 
>> However, it retains one of the things I didn’t like about the old
>> model, which is that the distinction between forward/backward only
>> types is a bit fuzzy, since the single advancedBy() method, now the
>> index(:offsetBy:) method, was used for both forward and backward
>> movement, which seems contradictory compared to the forward/backward
>> only single-step methods.
>> 
>> Anyway, I’m wondering what people’s thoughts would be on tweaking
>> the formula slightly such that there are methods that only work in a
>> particular direction, i.e- we’d have three main variations of the
>> methods like so:
>> 
>>     public func index(_ index:Index, advancedBy:Index.Distance) ->
>> Index { … } // Available on forward and bidirectional collections
>>     public func index(_ index:Index, reversedBy:Index.Distance) ->
>> Index { … } // Available on reverse and bidirectional collections
>>     public func index(_ index:Index, offsetBy:Index.Distance) ->
>> Index { … } // Available only on bidirectional collections
>> 
>> (note, the naming isn’t definite, as reversed may not be clear
>> enough, it’s just an example for now)
>> 
>> There are three reasons I’d prefer this:
>> 
>> The first is that I can pass the same distance into either of the
>> first two methods, and any negation etc. is handled internally. In
>> essence I shouldn’t have to handle negative distances at all when
>> working with the first two methods. So if I’m working with a step
>> size of 5, I can just pass that into the appropriate method, I never
>> have to do anything with it the value itself.

I don't understand why that's an advantage.  The Distance is required to
be a signed integer type, so you can always negate it.

>> The second benefit is that there should be no uncertainty about the
>> capabilities of the type you’re using; if it doesn’t have the
>> index(:reversedBy:) method then you can’t go backwards, same as
>> index(before:) and index(after:).

That's nice... but then you *don't* propose to handle negation
internally in that case?

>> The third and main benefit is that the methods are just more
>> explicit about what they do, and what direction you can go in;
>> passing negatives into either of the first two would produce errors
>> outright, allowing you to pick on mistakes in these cases.
>> 
>> The other main thing is that offsetBy doesn’t indicate whether a
>> type supports forward-only offsets, you have to read the
>> documentation to determine this either in the method itself or the
>> type, whereas the presence or absence of the first two variants are
>> pretty clear.

Yes, we are not entirely pleased with the fact that there is no
syntactic differentiation between BidirectionalCollection and
RandomAccessCollection.  We think protocol refinements are easier to
understand when they introduce new requirements.  On the other hand, it
is important to have a function, somewhere, that advances an index by N
steps, as efficiently as possible based on the collection's traversal
capability.  The natural place for that function is in a protocol
requirement.

>> Currently the offsetBy, and the previous advancedBy(), methods
>> require forward-only types to produce fatal errors if handed a
>> negative distance, 

[Nit: actually they don't; your conforming forward-only Collection can
legally produce any result it likes when asked to traverse backward.]

>> and vice versa for backward-only types, 

There's no such thing as a backward-only collection.  If you had one, you
might as well exchange the meaning of forward and backward.

>> which can only produce errors at runtime, whereas the presence or
>> absence of the first two methods can be handled during
>> development. You could still pass a negative value and end up with a
>> runtime error instead of course, but for the types of common uses
>> they’re intended for you should be unlikely to produce one.
>> 
>> The offsetBy form would still exist for bidirectional collections,
>> but would only really be used when you need to do more complex
>> index/distance manipulation outside of the type where a calculation
>> might produce either positive or negative values (e.g- if you're
>> calculating the distance and don’t know where two indices are in
>> relation to each other), the rest of the time you should try to use
>> the more specific, single-direction forms as they clarify your
>> intent and can help to catch mistakes if you’ve incorrectly
>> generated a distance for example.
>> 
>> 
>> Just curious what other people’s thoughts are about this?

In general, indexing is a fairly low-level means of access to a
collection, as it fundamentally exposes difficult semantics (distinct
index instances can refer to the same element, and indices can become
invalid).  It is important to make indexing usable, but I'm not very
sure the changes you're proposing would help.  To evaluate that, we
should see how your changes affect the writing of algorithms that do
indexing, like those in the standard library and in
https://github.com/apple/swift/blob/master/test/Prototypes/Algorithms.swift

I suggest you try your changes in the standard library and show us what
happens to the algorithms.  Are they clearer?  Would your changes be
likely to have prevented a bug?

>> 
>> I intended to mention this a lot sooner (to change advancedBy), but
>> then I find out about the new indexing model so thought I’d wait
>> until afterwards, then completely forgot =)
>> _______________________________________________
>> 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
>

> I like this idea. The problem is that it would require that we have an
> Index.NonNegativeDistance as argument to really make it statically
> safe. And we would have to have methods producing these, probably as
> optional return values.
> Otherwise we won't have achieved statically safety but effectively
> just better documentation about the capabilities of the respective
> collection.

As of today, negative index distances have meaning even in a forward
collection, since all indices are comparable.  So you can measure the
distance between any two indices as long as they are valid in the same
collection.  [I'm beginning to regret making all indices comparable a
little, but that's a separate discussion...]

-- 
-Dave