The Swift Standard Library ships with many collections such as Arrays, Dictionaries and Sets. In addition to its English Language meaning, Collection also means a Swift protocol that inherits from the Sequence protocol. If you already know the differences between a Sequence and a Collection, stop right here and go back to your regularly scheduled programming. If not, in today’s blog post, we will create our own contrived sequence in the hope that this knowledge will lay the foundation for creating our own Collections in a (near) future post.
Sequence vs Collection
A Sequence is any bunch of values that can be traversed through, sequentially, at least once. There is no requirement about multiple traversals or a second traversal starting from the beginning or from where it was left off, or being able to directly access a value somewhere in the middle. In other words, the traversal could be destructive. If we satisfy the Sequence protocol, we can use the for-in loop construct and we get a lot of stuff of free, such as map or the contains method.
Collection imposes an additional requirement in that we should be able to traverse through the same sequence multiple times to get the same values in the same order. The well known Arrays and Dictionaries of the world are Collections, not plain old Sequences. Traversals are non-destructive.
Sequence
The sequence protocol requirement – which I gathered by ctrl-command-clicking by way through Sequence in Xcode, looks like this
protocol Sequence {
associatedType Element where Self.Element == Self.Iterator.Element
associatedType Iterator: IteratorProtocol
func makeIterator() -> Self.Iterator
}It is a generic protocol and the associated types will be filled in by conforming types. The Element associated type, for example, refers to the type of elements in the sequence, and it should be the same type as its iterator’s elements. We will revisit this constraint later.
Iterator, on the other hand, is constrained to IteratorProtocol whose definition is:
protocol IteratorProtocol {
associatedType Element
func next() -> Element?
}This has an associatedType Element as well (mind you, it could be called anything), and it imposes one requirement – the next() function which returns a value of that type, or nil.
When you write a for loop over a sequence, two things happen
- The iterator for the sequence is obtained by calling “makeIterator()”. Remember that this method is a sequence requirement
- Then a
while let nextValue = obtainedIterator.next() { }is done. The next() method is a requirement on the iterator.
The for loop terminates when the next method returns nil.
Armed with this knowledge, let’s revisit the generic constraint Iterator.Element == Self.Element. If the sequence values are supposed to be of type Int, it would be quite stupid (and a compiler error) for its iterator to return Strings!
It is now time to build our contrived Sequence, as I promised. We will create the ability to traverse over the mutliples of any integer!
struct Multiples: Sequence {
private let base: Int
init(base: Int) {
self.base = base
}
func makeIterator() -> MultipleIterator {
return MultipleIterator(base: self.base)
}
}
struct MultipleIterator: IteratorProtocol {
private let base: Int
private var currentMultiplier = 1
init(base: Int) {
self.base = base
}
mutating func next() -> Int? {
defer { currentMultiplier += 1 }
return base * currentMultiplier
}
}The associated types are filled in by type inference. Luckily both the Elements are inferred to Int (by the fact that the next() method in the iterator returns an Int and the makeIterator() method returns such an iterator). They could have been made explicit by saying typealias Element = Int and typealias Iterator = MultipleIterator inside the conforming types. If the MultipleIterator returned Doubles instead, both the Element associated types would have been inferred to Double. It is possible to trigger a compiler error by saying typealias Element = Int inside theMultiple sequence because it doesn’t match the inferred Double of MultipleIterator.
Putting any “double” thoughts aside and taking into account the code written above, what do you think happens when you
let multiplesOf3 = Multiples(base: 3)
for i in multiplesOf3 {
print(i)
if i == 81 { break }
}It prints the numbers from 3 through 81. It would have been an infinite loop if we didn’t break out of the shackles.
What if the previous code is immediately followed by another for loop?
for i in multiplesOf3 {
print(i)
if i == 90 { break }
}If you think it only prints 84, 87 and 90, you would be wrong! The new for loop calls the makeIterator method again, which returns a new instance of MultipleIterator and that starts from 3. To fix (or unfix, depending on your viewpoint) this, you can just return the same copy of the iterator every time makeIterator() is called.
Bonus!
Frankly speaking, it is slightly confusing to have two separate types for the sequence and the iterator, so we can just make the sequence its own iterator as well, by implementing the next() method inside Multiples
struct Multiples: Sequence, IteratorProtocol {
private let base: Int
private var currentMultiplier = 1
init(base: Int) {
self.base = base
}
mutating func next() -> Int? {
defer { currentMultiplier += 1 }
return base * currentMultiplier
}
}If you were paying any attention at all, you might have noticed that the above code omits the makeIterator() entirely! How does it still work? Let’s wormhole our way straight into the standard library. The relevant portion is quoted below
// Provides a default associated type witness for Iterator when the
// Self type is both a Sequence and an Iterator.
extension Sequence where Self: IteratorProtocol {
// @_implements(Sequence, Iterator)
public typealias _Default_Iterator = Self
}
/// A default makeIterator() function for `IteratorProtocol` instances that
/// are declared to conform to `Sequence`
extension Sequence where Self.Iterator == Self {
/// Returns an iterator over the elements of this sequence.
@inlinable
public __consuming func makeIterator() -> Self {
return self
}
}Though I don’t really understand associated type witnesses, I am assuming the iterator is automatically set to Self if it conforms to both protocols and there is a default implementation of makeIterator() provided if Self.Iterator == Self, which returns self.
Conclusion
Like I mentioned earlier, most of the well known collections in Swift are “Collections”, and we will take a closer look at them SoonTM. Until that time, can you think of any Sequences that are not Collections in the standard library?
