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

[Kevin Ballard]

On Wed, Sep 28, 2016, at 02:10 PM, Tim Vermeulen wrote:
>
>> On 28 Sep 2016, at 23:03, Kevin Ballard <kevin at sb.org> wrote:
>>
>> On Wed, Sep 28, 2016, at 02:02 PM, Tim Vermeulen wrote:
>>>
>>>> On 28 Sep 2016, at 22:57, Kevin Ballard <kevin at sb.org> wrote:
>>>>
>>>> On Wed, Sep 28, 2016, at 01:54 PM, Tim Vermeulen wrote:
>>>>>
>>>>>> On 28 Sep 2016, at 22:46, Kevin Ballard <kevin at sb.org> wrote:
>>>>>>
>>>>>> That's a bunch of complexity for no benefit. Why would you ever
>>>>>> use this as a collection?
>>>>>
>>>>> I think there is a benefit. Something like
>>>>> `collection.indexed().reversed()` would benefit from that, and I
>>>>> think that could be useful.
>>>>
>>>> Perhaps, though you could just say
>>>> `collection.reversed().indexed()` instead.
>>>
>>> This isn’t necessarily the same though, is it? The reversed
>>> collection might use different indices than the original collection.
>>
>> Either way you write it you're dealing with reversed indices.
>
> `collection.indexed().reversed()` will contain indices from the
> original collection (but in reversed order).
> `collection.reversed().indexed()` will contain indices from the
> collection returned by `reversed()`, which may have a different type
> than `Base.Index`. It’s a distinction.
>
> This would compile:
>
> let characters = "Swift".characters
>
> for (index, character) in characters.indexed().reversed() {
>     print(characters[index], character)
> }
>
> This wouldn’t:
>
> let characters = "Swift".characters
>
> for (index, character) in characters.reversed().indexed() {
>     print(characters[index], character)
> }

Oh you're right.

Still, it's a fair amount of complexity (handling bidirectional and random-
access collections on top of the regular collection) and I'm not sure
it's worth the complexity just for reversed(). After all, you can always
fall back to the slightly uglier

for index in characters.indices.reversed() {
    let character = characters[index]
    ...
}

And it's worth pointing out that enumerated() doesn't return a
collection but nobody's been clamoring for reversed() support there.

-Kevin

>>
>> -Kevin
>>
>>>>>> The whole point is to be used in a for loop. If it was a
>>>>>> collection then you'd need to have an index for that collection,
>>>>>> so now you have an index that lets you get the index for another
>>>>>> collection, which is pretty useless because you could just be
>>>>>> using that underlying index to begin with.
>>>>>
>>>>> Rather than introducing a new index for this, we can simply use
>>>>> the index of the base collection for subscripting.
>>>>
>>>> That's actually a good idea, and if we do make it a collection this
>>>> is probably how we should handle it. But I still argue that the
>>>> ability to make something a collection doesn't mean it should be a
>>>> collection, if there's no good reason for anyone to actually try to
>>>> use it as such.
>>>>
>>>> -Kevin
>>>>
>>>>>> On Wed, Sep 28, 2016, at 01:38 PM, Tim Vermeulen via swift-
>>>>>> evolution wrote:
>>>>>>> +1 for `indexed()`, but I’m not sure about `IndexedSequence`.
>>>>>>> Why not `IndexedCollection`, which could also conform to
>>>>>>> Collection? With conditional conformances to
>>>>>>> BidirectionalCollection and RandomAccessCollection. This
>>>>>>> wouldn’t penalise the performance with respect to a simple
>>>>>>> `IndexedSequence`, would it?
>>>>>>>
>>>>>>>> Gist here:
>>>>>>>> https://gist.github.com/erica/2b2d92e6db787d001c689d3e37a7c3f2
>>>>>>>>
>>>>>>>> Introducingindexed()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
>>>>>>>>
>>>>>>>> Introduction
>>>>>>>>
>>>>>>>> This proposal introducesindexed()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)
>>>>>>>>
>>>>>>>> Motivation
>>>>>>>>
>>>>>>>> The standard library'senumerated()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 anArrayindex 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 useenumerated()-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
>>>>>>>> introducesindexed()to produce a more semantically relevant
>>>>>>>> sequence by pairing a collection'sindiceswith 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 ofindexed()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 throughIndexedSequence, similar toEnumeratedSequence.
>>>>>>>>
>>>>>>>> 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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-evolution/attachments/20160928/41bbeebc/attachment.html>