on Mon Oct 03 2016, Kevin Ballard <[email protected]> wrote:
> On Mon, Oct 3, 2016, at 02:51 PM, Dave Abrahams via swift-evolution wrote: >> >> on Mon Oct 03 2016, Kevin Ballard <[email protected]> wrote: >> >> > On Fri, Sep 30, 2016, at 08:53 PM, Dave Abrahams via swift-evolution wrote: >> >> > >> >> on Wed Sep 28 2016, Erica Sadun <[email protected]> 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 _______________________________________________ swift-evolution mailing list [email protected] https://lists.swift.org/mailman/listinfo/swift-evolution
