[Proposal draft] Introducing `indexed()` collections

I’m fairly sure that MutableCollection mutations are not allowed to invalidate any indices (for this exact reason). It would be great if someone could confirm this.

···

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(mailto: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(mailto:swift-evolution@swift.org)>wrote:
> >
> >Gist here:indexed.md · GitHub
> >
> >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(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

This wasn’t the default behaviour because `enumerated()` is a method for the `Sequence` protocol, which doesn’t have any indices. Integers are the only thing that make sense there. But I agree that this should have been part of the standard library already.

···

+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(mailto: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(mailto:swift-evolution@swift.org)>wrote:
> > Gist here:indexed.md · GitHub
> >
> > 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(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

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.

···

On 28 Sep 2016, at 22:57, Kevin Ballard <kevin@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@sb.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.

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:indexed.md · GitHub

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

Well you kind of did say it should be removed. If we came up with a new
design that produced an Int for sequences and an Index for collections,
then you can't get an Int for collections (without wrapping the
collection in AnySequence), which is basically the same thing as just
removing enumerated() for collections.

-Kevin

···

On Wed, Sep 28, 2016, at 07:08 PM, Colin Barrett wrote:

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

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> wrote:

Gist here:
indexed.md · GitHub

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. erica (Erica Sadun) · GitHub
  2. natecook1000 (Nate Cook) · GitHub
  3. jtbandes (Jacob Bandes-Storch) · GitHub
  4. Lily Ballard · GitHub
  5. https://gist.github.com/erica/tbd

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

FWIW, it's because what Nevin did below is easy to write, but getting
integer offsets isn't easy, at least not without introducing your own
counter state.

···

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

~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: indexed.md · GitHub

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

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

--
-Dave

> Indices have a specific, fixed meaning in Swift, which are used to create valid collection
> subscripts. This proposal introduces indexed() to produce a more semantically relevant sequence

by

> pairing a collection's indices with its members. While it is trivial to create a solution in Swift,
> the most common developer approach shown here calculates indexes twice:
>
> extension Collection {
> /// Returns a sequence of pairs (*idx*, *x*), where *idx* represents a
> /// consecutive collection index, and *x* represents an element of
> /// the sequence.
> func indexed() -> Zip2Sequence<Self.Indices, Self> {
> return zip(indices, self)
> }
> }

How does this calculate indices twice?

It calculates indices twice for any collection that uses
IndexingIterator as its iterator.

Yes. Not in general; just in that particular case.

And for collections that doesn't, it still does the moral equivalent,
because it's calculating an index offset along with whatever work the
Iterator does to calculate the next element.

Indexing is supposed to be cheap; almost free. Lazy filtered
collections are an anomaly. They're arguably not even legal
Collections, because advancing an index may not be O(1). They exist
because they're useful, but you shouldn't pass them out without
understanding the consequences.

As an example, if my collection is `someArray.lazy.filter(…)` then
zip(col.indices, col) will run the filter twice over the collection.

Okay.

> Incrementing an index in some collections can be unnecessarily
> costly.

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

A collection doesn't have to be badly-implemented to have a
non-trivial cost for calculating the next element.
As above, someArray.lazy.filter(…) is a good example of such a
collection.

Its conformance to Collection is quite sketchy.

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

Which should be an exceedingly rare thing.

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?

Mostly because it's additional API complexity, the usefulness appears to
be marginal, and it's optimizing for what should be a rare corner case
(collections that don't conform to efficiency expectations).

I'm not dead-set against adding it, but ATM it doesn't seem like there
are important use-cases that will benefit substantially from having it.
Convince me this is addressing a real need, and we'll talk. In phase 2
:-).

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.

I am also concerned about introducing confusion around the difference
from enumerated(). These methods will have identical semantics for
Array.

···

on Mon Oct 03 2016, Kevin Ballard <swift-evolution@swift.org> wrote:

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:

--
-Dave

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

-Kevin

···

On Wed, Sep 28, 2016, at 02:02 PM, Tim Vermeulen wrote:

> On 28 Sep 2016, at 22:57, Kevin Ballard <kevin@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@sb.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.
>>
>> 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:indexed.md · GitHub
>>>>>
>>>>> 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
>>

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)
}

···

On 28 Sep 2016, at 23:03, Kevin Ballard <kevin@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@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@sb.org> wrote:

-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:indexed.md · GitHub

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

>>
>>
>> > Indices have a specific, fixed meaning in Swift, which are used to create valid collection
>> > subscripts. This proposal introduces indexed() to produce a more semantically relevant sequence
> by
>
>> > pairing a collection's indices with its members. While it is trivial to create a solution in Swift,
>> > the most common developer approach shown here calculates indexes twice:
>> >
>> > extension Collection {
>> > /// Returns a sequence of pairs (*idx*, *x*), where *idx* represents a
>> > /// consecutive collection index, and *x* represents an element of
>> > /// the sequence.
>> > func indexed() -> Zip2Sequence<Self.Indices, Self> {
>> > return zip(indices, self)
>> > }
>> > }
>>
>> How does this calculate indices twice?
>
> It calculates indices twice for any collection that uses
> IndexingIterator as its iterator.

Yes. Not in general; just in that particular case.

> And for collections that doesn't, it still does the moral equivalent,
> because it's calculating an index offset along with whatever work the
> Iterator does to calculate the next element.

Indexing is supposed to be cheap; almost free. Lazy filtered
collections are an anomaly. They're arguably not even legal
Collections, because advancing an index may not be O(1). They exist
because they're useful, but you shouldn't pass them out without
understanding the consequences.

Using an index is supposed to be cheap/free. Calculating the next index is not guaranteed to be so. If you want another example of something that's not lazy, try String.CharacterView. Calculating the next index may be arbitrarily complex since I can string as many combining marks together as I want, though in practice it will be pretty cheap. But even this "pretty cheap" is still work, and depending on what I'm doing in the loop, calculating character indexes may be a significant fraction of the work performed.

> As an example, if my collection is `someArray.lazy.filter(…)` then
> zip(col.indices, col) will run the filter twice over the collection.

Okay.

>> > Incrementing an index in some collections can be unnecessarily
>> > costly.
>>
>> Seems like it's only *unnecessarily* costly in badly implemented
>> collections?
>
> A collection doesn't have to be badly-implemented to have a
> non-trivial cost for calculating the next element.
> As above, someArray.lazy.filter(…) is a good example of such a
> collection.

Its conformance to Collection is quite sketchy.

But it's not the only collection where calculating indexes is non-trivial.

-Kevin Ballard

···

On Mon, Oct 3, 2016, at 02:51 PM, Dave Abrahams via swift-evolution wrote:

on Mon Oct 03 2016, Kevin Ballard <swift-evolution@swift.org> wrote:
> 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:

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

Which should be an exceedingly rare thing.

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

Mostly because it's additional API complexity, the usefulness appears to
be marginal, and it's optimizing for what should be a rare corner case
(collections that don't conform to efficiency expectations).

I'm not dead-set against adding it, but ATM it doesn't seem like there
are important use-cases that will benefit substantially from having it.
Convince me this is addressing a real need, and we'll talk. In phase 2
:-).

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

I am also concerned about introducing confusion around the difference
from enumerated(). These methods will have identical semantics for
Array.

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

···

On Wed, Sep 28, 2016, at 02:10 PM, Tim Vermeulen wrote:

On 28 Sep 2016, at 23:03, Kevin Ballard <kevin@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@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@sb.org> wrote:

-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:
indexed.md · GitHub

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

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

It’s very straight-forward to simply forward all requirements to the base collection. I just wrote it out, and it might even be less complex than the sequence approach, because we don’t need a custom iterator.

After all, you can always fall back to the slightly uglier

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

You could, but don’t forget that writing `characters.indexed().reversed()` in the case of `IndexedSequence` would still have the result you’d expect. It’s simply less efficient than necessary. Most people probably wouldn’t even realise that the more readable approach isn’t the most efficient one, here.

···

On 28 Sep 2016, at 23:44, Kevin Ballard <kevin@sb.org> wrote:
On Wed, Sep 28, 2016, at 02:10 PM, Tim Vermeulen wrote:

On 28 Sep 2016, at 23:03, Kevin Ballard <kevin@sb.org <mailto:kevin@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@sb.org <mailto:kevin@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@sb.org <mailto:kevin@sb.org>> wrote:

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:indexed.md · GitHub

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

>>

>>
>> > Indices have a specific, fixed meaning in Swift, which are used to create valid collection
>> > subscripts. This proposal introduces indexed() to produce a more semantically relevant sequence
> by
>
>> > pairing a collection's indices with its members. While it is trivial to create a solution in Swift,
>> > the most common developer approach shown here calculates indexes twice:
>> >
>> > extension Collection {
>> > /// Returns a sequence of pairs (*idx*, *x*), where *idx* represents a
>> > /// consecutive collection index, and *x* represents an element of
>> > /// the sequence.
>> > func indexed() -> Zip2Sequence<Self.Indices, Self> {
>> > return zip(indices, self)
>> > }
>> > }
>>
>> How does this calculate indices twice?
>
> It calculates indices twice for any collection that uses
> IndexingIterator as its iterator.

Yes. Not in general; just in that particular case.

> And for collections that doesn't, it still does the moral equivalent,
> because it's calculating an index offset along with whatever work the
> Iterator does to calculate the next element.

Indexing is supposed to be cheap; almost free. Lazy filtered
collections are an anomaly. They're arguably not even legal
Collections, because advancing an index may not be O(1). They exist
because they're useful, but you shouldn't pass them out without
understanding the consequences.

Using an index is supposed to be cheap/free. Calculating the next
index is not guaranteed to be so.

It's supposed to be so.

If you want another example of something that's not lazy, try
String.CharacterView. Calculating the next index may be arbitrarily
complex since I can string as many combining marks together as I want,
though in practice it will be pretty cheap. But even this "pretty
cheap" is still work, and depending on what I'm doing in the loop,
calculating character indexes may be a significant fraction of the
work performed.

Okay, you do have a point, here. Also, Dictionary and Set can have
similar cost profiles for advancing an index.

> As an example, if my collection is `someArray.lazy.filter(…)` then
> zip(col.indices, col) will run the filter twice over the collection.

Okay.

>> > Incrementing an index in some collections can be unnecessarily
>> > costly.
>>
>> Seems like it's only *unnecessarily* costly in badly implemented
>> collections?
>
> A collection doesn't have to be badly-implemented to have a
> non-trivial cost for calculating the next element.

To be clear, in those cases it is a necessary cost.

> As above, someArray.lazy.filter(…) is a good example of such a
> collection.

Its conformance to Collection is quite sketchy.

But it's not the only collection where calculating indexes is
non-trivial.

Okay. Well, I suggest we bring this up again in phase 2, when it's
actionable.

···

on Mon Oct 03 2016, Kevin Ballard <swift-evolution@swift.org> wrote:

On Mon, Oct 3, 2016, at 02:51 PM, Dave Abrahams via swift-evolution wrote:

on Mon Oct 03 2016, Kevin Ballard <swift-evolution@swift.org> wrote:
> 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:

--
-Dave