[Proposal draft] Introducing `indexed()` collections


(Erica Sadun) #1

Gist here: 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


(Sean Heber) #2

This might just be me being silly, but is there any way to be able to do something like this instead:

for (index, value) in sequence {
}

Maybe by adding another variant of makeIterator() that only differs by the return type or something like that?

I sort of dislike that enumerated() and indexed() would co-exist and potentially lead to really subtle bugs when getting them confused. Obviously removing enumerated() would be a breaking change, though, and maybe it has valuable uses that I’m not really thinking about (although it seems to me that the index/value pair is what you want like, 99% of the time and plenty of people - myself included - have been using the index of enumerated() as an array index even though that’s technically maybe not quite ‘correct').

l8r
Sean

···

On Sep 28, 2016, at 12:55 PM, Erica Sadun via swift-evolution <swift-evolution@swift.org> wrote:

Gist here: https://gist.github.com/erica/2b2d92e6db787d001c689d3e37a7c3f2

Introducing indexed() collections

  • Proposal: TBD
  • Author: Erica Sadun, Nate Cook, Jacob Bandes-Storch, Kevin Ballard
  • 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

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@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution


#3

+1, I have been mildly surprised that this was not already present.

My workaround heretofore has been:

for idx in abc.indices {
  let val = abc[i]
  // do something with idx and val
}

Nevin

···

On Wed, Sep 28, 2016 at 1:55 PM, Erica Sadun via swift-evolution < swift-evolution@swift.org> wrote:

Gist here: 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@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution


(plx) #4

+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?).

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?

···

On Sep 28, 2016, at 12:55 PM, Erica Sadun via swift-evolution <swift-evolution@swift.org> wrote:

Gist here: 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@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution


(Colin Barrett) #5

Definitely well motivated. It seems like having both .enumerated() and .indexed() methods would still leave open the possibility of novices using .enumerated and making the same mistake as before. I realize that because of where .enumerated() sits it has to work the way it does, but is there perhaps a better design (with constrained extensions?) for a single method that can give an Int for a Sequence and an appropriate Index for a Collection?

-Colin

···

On Sep 28, 2016, at 1:55 PM, Erica Sadun via swift-evolution <swift-evolution@swift.org> wrote:

Gist here: 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@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution


(Tim Vermeulen) #6

+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


(Haravikk) #7

+1 to this idea.

On the issue of discoverability, I wonder if .enumeratedByIndex() could be an alternative name for the new method? It's a bit verbose, but would cause it to come up as an option alongside .enumarated(), while being clear of the difference.

···

On 28 Sep 2016, at 18:55, Erica Sadun via swift-evolution <swift-evolution@swift.org> wrote:

Gist here: 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@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution


(Dave Abrahams) #8

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?

Incrementing an index in some collections can be unnecessarily
costly.

Seems like it's only *unnecessarily* costly in badly implemented
collections?

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

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.

···

on Wed Sep 28 2016, Erica Sadun <swift-evolution@swift.org> wrote:

--
-Dave


(Lily Ballard) #9

That's a bunch of complexity for no benefit. Why would you ever use this as a collection? 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.

-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@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution


(Robert Widmann) #10

+1. One of those things where you wonder why this wasn't the default behavior.

~Robert Widmann

2016/09/28 14:23、Nevin Brackett-Rozinsky via swift-evolution <swift-evolution@swift.org> のメッセージ:

···

+1, I have been mildly surprised that this was not already present.

My workaround heretofore has been:

for idx in abc.indices {
  let val = abc[i]
  // do something with idx and val
}

Nevin

On Wed, Sep 28, 2016 at 1:55 PM, Erica Sadun via swift-evolution <swift-evolution@swift.org> wrote:
Gist here: https://gist.github.com/erica/2b2d92e6db787d001c689d3e37a7c3f2

Introducing indexed() collections
Proposal: TBD
Author: Erica Sadun, Nate Cook, Jacob Bandes-Storch, Kevin Ballard
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

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@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution


(Lily Ballard) #11

+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 Wed, Sep 28, 2016, at 02:27 PM, plx via swift-evolution wrote:

On Sep 28, 2016, at 12:55 PM, Erica Sadun via swift-evolution <swift- >> evolution@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@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

_________________________________________________
swift-evolution mailing list
swift-evolution@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


(plx) #12

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

···

On Sep 28, 2016, at 4:47 PM, Kevin Ballard <kevin@sb.org> wrote:
On Wed, Sep 28, 2016, at 02:27 PM, plx via swift-evolution wrote:

-Kevin

On Sep 28, 2016, at 12:55 PM, Erica Sadun via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:

Gist here: 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@swift.org <mailto:swift-evolution@swift.org>
https://lists.swift.org/mailman/listinfo/swift-evolution

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org <mailto:swift-evolution@swift.org>
https://lists.swift.org/mailman/listinfo/swift-evolution


(Lily Ballard) #13

There's more uses for enumerated() than just producing Array indices.

-Kevin

···

On Wed, Sep 28, 2016, at 05:49 PM, Colin Barrett via swift-evolution wrote:

Definitely well motivated. It seems like having both .enumerated() and
.indexed() methods would still leave open the possibility of novices
using .enumerated and making the same mistake as before. I realize
that because of where .enumerated() sits it has to work the way it
does, but is there perhaps a better design (with constrained
extensions?) for a single method that can give an Int for a Sequence
and an appropriate Index for a Collection?

-Colin

On Sep 28, 2016, at 1:55 PM, Erica Sadun via swift-evolution <swift- >> evolution@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@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

_________________________________________________
swift-evolution mailing list
swift-evolution@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


#14

I like Sean’s idea.

Nevin

···

On Wed, Sep 28, 2016 at 2:34 PM, Sean Heber via swift-evolution < swift-evolution@swift.org> wrote:

This might just be me being silly, but is there any way to be able to do
something like this instead:

for (index, value) in sequence {
}

Maybe by adding another variant of makeIterator() that only differs by the
return type or something like that?

I sort of dislike that enumerated() and indexed() would co-exist and
potentially lead to really subtle bugs when getting them confused.
Obviously removing enumerated() would be a breaking change, though, and
maybe it has valuable uses that I’m not really thinking about (although it
seems to me that the index/value pair is what you want like, 99% of the
time and plenty of people - myself included - have been using the index of
enumerated() as an array index even though that’s technically maybe not
quite ‘correct').

l8r
Sean

> On Sep 28, 2016, at 12:55 PM, Erica Sadun via swift-evolution < > swift-evolution@swift.org> wrote:
>
> Gist here: https://gist.github.com/erica/2b2d92e6db787d001c689d3e37a7c3
f2
>
> Introducing indexed() collections
>
> • Proposal: TBD
> • Author: Erica Sadun, Nate Cook, Jacob Bandes-Storch, Kevin
Ballard
> • 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
>
> 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@swift.org
> https://lists.swift.org/mailman/listinfo/swift-evolution

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution


(Jay) #15

One (potentially dumb) question...

If the actual indices are needed inside the loop, presumably this means
they will be used in the loop, perhaps to mutate it, and if the collection
is mutated won't that either invalidate (or change the relative
correspondence of) the others indices, because the collection accessed in
the loop will be the mutated one whereas the indices refer to the copy that
was taken at the start when the 'for' statement was evaluated?

···

On Wed, 28 Sep 2016 at 19:34 Sean Heber via swift-evolution < swift-evolution@swift.org> wrote:

This might just be me being silly, but is there any way to be able to do
something like this instead:

for (index, value) in sequence {
}

Maybe by adding another variant of makeIterator() that only differs by the
return type or something like that?

I sort of dislike that enumerated() and indexed() would co-exist and
potentially lead to really subtle bugs when getting them confused.
Obviously removing enumerated() would be a breaking change, though, and
maybe it has valuable uses that I’m not really thinking about (although it
seems to me that the index/value pair is what you want like, 99% of the
time and plenty of people - myself included - have been using the index of
enumerated() as an array index even though that’s technically maybe not
quite ‘correct').

l8r
Sean

> On Sep 28, 2016, at 12:55 PM, Erica Sadun via swift-evolution < > swift-evolution@swift.org> wrote:
>
> Gist here:
https://gist.github.com/erica/2b2d92e6db787d001c689d3e37a7c3f2
>
> Introducing indexed() collections
>
> • Proposal: TBD
> • Author: Erica Sadun, Nate Cook, Jacob Bandes-Storch, Kevin
Ballard
> • 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
>
> 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@swift.org
> https://lists.swift.org/mailman/listinfo/swift-evolution

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution


(Colin Barrett) #16

I’m aware, which is why I didn’t say it should be removed. (And if I hadn’t been aware, this wouldn’t have helped me discover them. :slight_smile:

···

On Sep 28, 2016, at 8:58 PM, Kevin Ballard <kevin@sb.org> wrote:

There's more uses for enumerated() than just producing Array indices.

-Kevin

On Wed, Sep 28, 2016, at 05:49 PM, Colin Barrett via swift-evolution wrote:

Definitely well motivated. It seems like having both .enumerated() and .indexed() methods would still leave open the possibility of novices using .enumerated and making the same mistake as before. I realize that because of where .enumerated() sits it has to work the way it does, but is there perhaps a better design (with constrained extensions?) for a single method that can give an Int for a Sequence and an appropriate Index for a Collection?

-Colin

On Sep 28, 2016, at 1:55 PM, Erica Sadun via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:

Gist here: 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@swift.org <mailto:swift-evolution@swift.org>
https://lists.swift.org/mailman/listinfo/swift-evolution

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org <mailto:swift-evolution@swift.org>
https://lists.swift.org/mailman/listinfo/swift-evolution


(Tim Vermeulen) #17

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.

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.

···

On 28 Sep 2016, at 22:46, Kevin Ballard <kevin@sb.org> wrote:

-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@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution


(Jacob Bandes-Storch) #18

That's a bunch of complexity for no benefit. Why would you ever use this
as a collection?

I think getting an element and an index simultaneously from, for instance,
collection.indexed().sorted(by:) or collection.indexed().first(where:)
could be quite useful.

Jacob

···

On Wed, Sep 28, 2016 at 1:46 PM, Kevin Ballard via swift-evolution < swift-evolution@swift.org> wrote:

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.

-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/2b2d92e6db787d001c689d3e37a7c3
f2
> >
> > 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@swift.org
> https://lists.swift.org/mailman/listinfo/swift-evolution
_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution


(Lily Ballard) #19

> 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

···

On Fri, Sep 30, 2016, at 08:53 PM, Dave Abrahams via swift-evolution wrote:

on Wed Sep 28 2016, Erica Sadun <swift-evolution@swift.org> wrote:


(Lily Ballard) #20

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

> 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:54 PM, Tim Vermeulen wrote:

> On 28 Sep 2016, at 22:46, Kevin Ballard <kevin@sb.org> wrote:

> 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@swift.org
>> https://lists.swift.org/mailman/listinfo/swift-evolution