[swift-evolution] [Proposal draft] Introducing `indexed()` collections

[Dave Abrahams]

on Mon Oct 03 2016, Kevin Ballard <swift-evolution at swift.org> wrote:

> On Mon, Oct 3, 2016, at 02:51 PM, Dave Abrahams via swift-evolution wrote:
>> 
>> on Mon Oct 03 2016, Kevin Ballard <swift-evolution at swift.org> wrote:
>> 
>> > On Fri, Sep 30, 2016, at 08:53 PM, Dave Abrahams via swift-evolution wrote:
>> >> 
>
>> >> on Wed Sep 28 2016, Erica Sadun <swift-evolution at swift.org> wrote:
>> >> 
>> >> > Indices have a specific, fixed meaning in Swift, which are used to create valid collection
>> >> > subscripts. This proposal introduces indexed() to produce a more semantically relevant sequence
>> > by
>> >
>> >> > pairing a collection's indices with its members. While it is trivial to create a solution in Swift,
>> >> > the most common developer approach shown here calculates indexes twice:
>> >> >
>> >> > extension Collection {
>> >> >     /// Returns a sequence of pairs (*idx*, *x*), where *idx* represents a
>> >> >     /// consecutive collection index, and *x* represents an element of
>> >> >     /// the sequence.
>> >> >     func indexed() -> Zip2Sequence<Self.Indices, Self> {
>> >> >         return zip(indices, self)
>> >> >     }
>> >> > }
>> >> 
>> >> How does this calculate indices twice?
>> >
>> > It calculates indices twice for any collection that uses
>> > IndexingIterator as its iterator. 
>> 
>> Yes.  Not in general; just in that particular case.
>> 
>> > And for collections that doesn't, it still does the moral equivalent,
>> > because it's calculating an index offset along with whatever work the
>> > Iterator does to calculate the next element.
>> 
>> Indexing is supposed to be cheap; almost free.  Lazy filtered
>> collections are an anomaly.  They're arguably not even legal
>> Collections, because advancing an index may not be O(1).  They exist
>> because they're useful, but you shouldn't pass them out without
>> understanding the consequences.
>
> Using an index is supposed to be cheap/free. Calculating the next
> index is not guaranteed to be so. 

It's supposed to be so.

> If you want another example of something that's not lazy, try
> String.CharacterView. Calculating the next index may be arbitrarily
> complex since I can string as many combining marks together as I want,
> though in practice it will be pretty cheap. But even this "pretty
> cheap" is still work, and depending on what I'm doing in the loop,
> calculating character indexes may be a significant fraction of the
> work performed.

Okay, you do have a point, here.  Also, Dictionary and Set can have
similar cost profiles for advancing an index.

>> > As an example, if my collection is `someArray.lazy.filter(…)` then
>> > zip(col.indices, col) will run the filter twice over the collection.
>> 
>> Okay.
>> 
>> >> > Incrementing an index in some collections can be unnecessarily
>> >> > costly. 
>> >> 
>> >> Seems like it's only *unnecessarily* costly in badly implemented
>> >> collections?
>> >
>> > A collection doesn't have to be badly-implemented to have a
>> > non-trivial cost for calculating the next element. 

To be clear, in those cases it is a necessary cost.

>> > As above, someArray.lazy.filter(…) is a good example of such a
>> > collection.
>> 
>> Its conformance to Collection is quite sketchy.
>
> But it's not the only collection where calculating indexes is
> non-trivial.

Okay.  Well, I suggest we bring this up again in phase 2, when it's
actionable.

-- 
-Dave