Why are (almost?) all the Standard Library iterators also sequences?

When I browse the Standard Library's code, it seems that all the IteratorProtocol-conforming types add conformance to Sequence. Is there a reason for this, maybe based on how the iterator/generator/sequence protocols worked before Swift 3? I have some wrapping iterator defined such that it looks like a bad idea if it also gratuitously is a sequence.

Perhaps there's some clue in here:

1 Like

Do you happen to know if that pitch went anywhere? I read through it and the feedback was mostly positive so I'm curious if a proposal was ever made? I'm betting that with the new ABI stable 5.0 that the ship has probably sailed for something like that. :confused:

No, I don't know.

If you're going to dump a 70+ article thread on me, give me at least some clue where to look (implying you at least took a glance for the relevant information yourself).

I hope that pitch goes nowhere; besides compatibility issues, it's a fundamentally bad idea. An indexing scheme assumes it's trivial to get a value from an index; that may not always be the case.

1 Like

I see the compatibility issues, but would you be able to elaborate on why you feel it is a fundamentally bad idea? I don't see how this change means that it would not be possible take an index and get a value through non-trivial means? My understanding is that you can still implement your own iterator through the IteratorProtocol which would allow you to do this.

Not all stdlib iterators conform to Sequence -- many data structures provide iterators that aren't sequences: see Set.Iterator, Dictionary.Iterator, Dictionary.Values.Iterator, String.Iterator, etc. (There aren't any technical reasons these couldn't be sequences, though.) The big exception is the default Collection iterator, IndexingIterator, which does conform to Sequence.

I consider Sequence conformance on an IteratorProtocol type to be mostly a convenience feature. Its most visible effect is that it allows you to use the iterator directly in a for loop, as well as in generic contexts constrained to Sequence.

let array: Array<Int> = [1, 2, 3, 4]
let i = array.makeIterator()
for value in i { // OK; IndexingIterator is a Sequence
  print(value) // ⟹ 1, 2, 3, 4

let set: Set<Int> = [1, 2, 3, 4]
let j = set.makeIterator()
for value in j { // error: type 'Set<Int>.Iterator' does not conform to protocol 'Sequence'

This is a relatively shallow convenience feature with marginal utility. We can always use a while loop to iterate, or we can wrap the iterator in an IteratorSequence:

var j = someSequence.makeIterator()
while let value = j.next() { // OK

var j = someSequence.makeIterator()
for value in IteratorSequence(j) { // OK

Sequence conformance does somewhat imply to me that it is safe to save any iterator value and restart the iteration from that point, without affecting the state of the other live iterators. However, this is not an explicit requirement, and some types may violate it. (Hopefully none in the stdlib.)

let i = someSequence.makeIterator() // Start first pass over `someSequence`.
var j = i
let value1 = j.next()

var k = i.makeIterator() // Start first pass over the sequence `i`.
let value2 = k.next()

print(value1 == value2) // I expect this should print true

An example: the Fibonacci sequence.

It's easy to imagine it as an (infinite) Sequence. Initialize the "previous" register to 0, and the "current" to 1. For each next(), return current, set previous to current, and set current to the sum of (the previous) previous and current. If you look at the Wikipedia article, there is an iterative formula, but it involves square roots, powers, and fractions. It would need floating-point processing for something we know is an integer result, and it'll probably be less accurate and take more time. (For (inner) example: if you use repeated multiplications for the powers, then indexing indirectly becomes O(n).) It's not worth it.

1 Like

I consider it to be a bug ;)

1 Like

This is not what that pitch is about. The pitch notes that the full iterator state of a multi-pass sequence (along with an integer offset from the start and perhaps a cached "current" value) would make a workable Index type for a Collection implementation, then extends this idea to also support single-pass sequences, by remembering all previously generated elements.

There are also several prototypes for the (simpler) multi-pass case. @nnnnnnnn had a SequenceIndex implementation that I can't find now; here is a variant by Dave that doesn't include a copy of the "current" element.

By simply adding an empty conformance to MultipassSequence to FibonacciSequence, you automagically get a working Collection implementation, complete with a index type satisfying all Collection requirements. There is no need to invoke the golden ratio.

1 Like
Terms of Service

Privacy Policy

Cookie Policy