Why does Swift distinguish between Sequence and IteratorProtocol

Sequence protocol requires a method called makeIterator that returns an Iterator protocol.
IteratorProtocol in turn defines one method next that brings the next element or nil if done.

Why not just have Sequence have the next method?

I'm sure there are benefits, I'm just not sure what.
I can imagine you can, for example, return different iterators for the same sequence?

Iterators are single use, but Sequence can be iterated over multiple times by making multiple iterators out of it

(Unfortunately there are some sequences that are single-use)

1 Like

You shouldn't expect to traverse an arbitrary Sequence more than once. Collection is for sets of items that can be traversed multiple times.

5 Likes

Consider Array, which conforms to Sequence. If next were a method on Sequence, it would have to remove the first element of the Array, which is O(N). So a for-in loop over an Array would be O(N2) instead of O(N).

This could be fixed if Array, like ArraySlice, could have a startIndex other than zero. Then next could be O(1). This would have the added benefit of eliminating the need for ArraySlice. But it would also require Array to store its startIndex and perhaps it would have a performance impact when indexing or subscripting an Array. I assume that's why ArraySlice is a separate type.

Separating Array.Iterator from Array means that extra word only needs to be stored while the iterator exists, and the next method can be O(1).

6 Likes

It was thought to be potentially useful at the time (back when IteratorProtocol was known as GeneratorType, and Sequence was known as SequenceType), but it turns out not to be useful in practice. Unfortunately we’re stuck with it.

Iterators are definitely single-pass.
Collections are definitely multi-pass.

As @christopherweems says, an unknown Sequence may be either - it is not specified whether it is single- or multi-pass.

So why does Sequence exist? So that you can write algorithms which only need one pass (e.g. map, contains), and have those algorithms available on both single-pass and multiple-pass data, without duplicating your algorithm.

For example, Array should conform to Collection and should not conform to IteratorProtocol. If we wrote a version of map which used IteratorProtocol, it would not be available on Array.

It's not a flawless design, but it's the best we have given what the language was able to express when it was introduced.

3 Likes

a sequence can have the next method, because a type can conform to both Sequence and IteratorProtocol at the same time. this is what i usually do when i have a single-pass sequence.