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

[plx]

> On Sep 28, 2016, at 4:47 PM, Kevin Ballard <kevin at sb.org> wrote:
> 
> On Wed, Sep 28, 2016, at 02:27 PM, plx via swift-evolution wrote:
>> +1 to have something *like* this, but a few questions.
>> 
>> Is there a specific reason `IndexedSequence` isn’t `IndexedCollection`, conforming to `Collection` (and once conditional conformances are available picking up `BidirectionalCollection` and `RandomAccessCollection` when possible?).
> 
> This is already being discussed in this thread, but the simple answer is that adds complexity and it's not obvious that it's worth the additional complexity.

As it can be done as trivial, "pass-through" boilerplate:

  struct IndexedCollection<C:Collection> :Collection {
    typealias Index = C.Index
    typealias Indices = C.Indices

    let base: C
  
    subscript(i: Index) -> (Index,C.Iterator.Element) { return (i,base[i]) }
  
}

…(and so on and so forth) it’s about as trivial to implement as any `Collection` is going to be…which is why I was a bit surprised it wasn’t part of the proposal.

If you’re worried about performance vis-a-vis lazy collections you could also store the `base.indices` and use it instead of `base` but even that should leave the implementation almost entirely boilerplate-ish.

Sure it’s a bit annoying to write it all out but I’m not seeing a lot of complexity really; I might be missing something?

> 
>> Secondly, can you provide more detail on the proposed implementation? 
>> 
>> Are you just walking the index forward and subscripting the base in the iterator, or something fancier?
> 
> Yeah, that's what it would be. Something like
> 
> sequence(state: base.indices, next: {
>     guard let idx = $0.next() else { return nil }
>     return (idx, base[idx])
> })
> 
> except done as a concrete type.

I assume the above is closer to this?

> sequence(state: base.indices.makeIterator(), next: {
>     guard let idx = $0.next() else { return nil }
>     return (idx, base[idx])
> })

The way the proposal was worried I was concerned the “only calculate each index once” bit would be a bit expensive when not really necessary, but deferring to the implementation of `indices` seems perfectly reasonable to me.

> 
> -Kevin
> 
>>> On Sep 28, 2016, at 12:55 PM, Erica Sadun via swift-evolution <swift-evolution at swift.org <mailto:swift-evolution at swift.org>> wrote:
>>> 
>>> Gist here: https://gist.github.com/erica/2b2d92e6db787d001c689d3e37a7c3f2 <https://gist.github.com/erica/2b2d92e6db787d001c689d3e37a7c3f2>
>>> 
>>> Introducing indexed() collections
>>> 
>>> Proposal: TBD
>>> Author: Erica Sadun <https://github.com/erica>, Nate Cook <https://github.com/natecook1000>, Jacob Bandes-Storch <https://github.com/jtbandes>, Kevin Ballard <https://github.com/kballard>
>>> Status: TBD
>>> Review manager: TBD
>>>  <https://gist.github.com/erica/2b2d92e6db787d001c689d3e37a7c3f2#introduction>Introduction
>>> 
>>> This proposal introduces indexed() to the standard library, a method on collections that returns an (index, element) tuple sequence.
>>> 
>>> Swift-evolution thread: TBD <https://gist.github.com/erica/tbd>
>>>  <https://gist.github.com/erica/2b2d92e6db787d001c689d3e37a7c3f2#motivation>Motivation
>>> 
>>> The standard library's enumerated() method returns a sequence of pairs enumerating a sequence. The pair's first member is a monotonically incrementing integer starting at zero, and the second member is the corresponding element of the sequence. When working with arrays, the integer is coincidentally the same type and value as an Array index but the enumerated value is not generated with index-specific semantics. This may lead to confusion when developers attempt to subscript a non-array collection with enumerated integers. It can introduce serious bugs when developers use enumerated()-based integer subscripting with non-zero-based array slices.
>>> 
>>> 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)
>>>     }
>>> }
>>> 
>>> Incrementing an index in some collections can be unnecessarily costly. 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.
>>> 
>>>  <https://gist.github.com/erica/2b2d92e6db787d001c689d3e37a7c3f2#detailed-design>Detailed Design
>>> 
>>> Our vision of indexed() bypasses duplicated index generation with their potentially high computation costs. We'd create an iterator that calculates each index once and then applies that index to subscript the collection. Implementation would take place through IndexedSequence, similar to EnumeratedSequence.
>>> 
>>>  <https://gist.github.com/erica/2b2d92e6db787d001c689d3e37a7c3f2#impact-on-existing-code>Impact on Existing Code
>>> 
>>> This proposal is purely additive and has no impact on existing code.
>>> 
>>>  <https://gist.github.com/erica/2b2d92e6db787d001c689d3e37a7c3f2#alternatives-considered>Alternatives Considered
>>> 
>>> Not yet
>>> _______________________________________________
>>> swift-evolution mailing list
>>> swift-evolution at swift.org <mailto:swift-evolution at swift.org>
>>> https://lists.swift.org/mailman/listinfo/swift-evolution
>> 
>> 
>> _______________________________________________
>> swift-evolution mailing list
>> swift-evolution at swift.org <mailto:swift-evolution at swift.org>
>> https://lists.swift.org/mailman/listinfo/swift-evolution <https://lists.swift.org/mailman/listinfo/swift-evolution>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-evolution/attachments/20160928/086d9c6f/attachment.html>