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

[Kevin Ballard]

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. 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.

As an example, if my collection is `someArray.lazy.filter(…)` then zip(col.indices, col) will run the filter twice over the collection.

> > 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. As above, someArray.lazy.filter(…) is a good example of such a collection.

> > In a lazy filtered collection, an index increment is potentially
> > O(N). We feel this is better addressed introducing a new function into
> > the Standard Library to provide a more efficient design that avoids
> > the attractive nuisance of the "obvious" solution.
> 
> I am generally opposed to adding this.  The usual solution developers
> will reach for here is:
> 
>     for i in x.indices {
>         somethingWith(x[i])
>     }
> 
> zip(indices, self) is only suboptimal for lazy filtered sequences, which
> should be used with care anyhow (see the note here:
> http://swiftdoc.org/v3.0/type/LazyFilterCollection/).

It's suboptimal for any collection with a non-trivial index.

> If you really need a lazy sequence of pairs that's optimal with lazy
> filtered sequences, 
> 
>     x.indices.lazy.map { ($0, x[$0]) }
> 
> is a good solution and pretty easy to write.

And yet people will write zip(x.indices, x) instead because it's shorter and not immediately obvious that it may be suboptimal depending on the collection.

Why are you opposed to adding this? The ability to work around its lack doesn't mean it doesn't have value, and the fact that the simplest workaround is not the best one is I think a good reason to make the easiest solution into the best one (by providing .indexed()). Add to that the fact that a lot of people probably use .enumerated() to produce indexes when working with arrays, and this is a pitfall when working with other types, such as ArraySlice which still has Int indexes but is no longer zero-based.

-Kevin Ballard