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

[Kevin Ballard]

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.

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

-Kevin

>> On Sep 28, 2016, at 12:55 PM, Erica Sadun via swift-evolution <swift-
>> evolution at swift.org> wrote:
>>
>> Gist here:
>> https://gist.github.com/erica/2b2d92e6db787d001c689d3e37a7c3f2
>>
>> Introducing indexed() collections


>>  * Proposal: TBD
>>  * Author: Erica Sadun[1], Nate Cook[2], Jacob Bandes-Storch[3],
>>    Kevin Ballard[4]
>>  * Status: TBD
>>  * Review manager: TBD
>> Introduction
>> This proposal introduces indexed() to the standard library, a method
>> on collections that returns an (index, element) tuple sequence.
>> Swift-evolution thread: TBD[5]
>> 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.
>> 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.
>> Impact on Existing Code
>> This proposal is purely additive and has no impact on existing code.
>> Alternatives Considered
>> Not yet
>> _______________________________________________
>> 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


Links:

  1. https://github.com/erica
  2. https://github.com/natecook1000
  3. https://github.com/jtbandes
  4. https://github.com/kballard
  5. https://gist.github.com/erica/tbd
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-evolution/attachments/20160928/6493d5a9/attachment-0001.html>