Experimenting with Swift 3 Sequences and Iterators
Posted on November 12, 2015 中文版
Update 02/17: Improved the code snippets, with less cryptic variable names.
Update 10/16: This post has been updated to Swift 3.
In this article, part of a series on Swift and the functional approach, we’ll explore what we need to do to build our own sequences in Swift 2, discuss the differences between finite and infinite sequences and examine what we can do with them in a few example scenarios.
Get the playground for this post from GitHub or zipped.
The Sequence standard protocol is defined in the documentation simply as a type that can be iterated with a for…in loop. The section of the protocol definition relevant to our custom implementation is in the top half:
public protocol Sequence {
/// A type that provides the sequence's iteration interface and
/// encapsulates its iteration state.
associatedtype Iterator : IteratorProtocol
/// Returns an iterator over the elements of this sequence.
func makeIterator() -> Iterator
...
...
}
The protocol contains an associated type (Swift weird way of making protocols generic) that refers to the IteratorProtocol protocol, we’ll need to implement this too in some way when creating a sequence. Our custom Sequence will return a custom iterator with a specific element type when makeIterator() is called.
Sequences also provide many other interesting methods, already implemented via protocol extensions, like map, flatmap (check out my in-depth article on map and flatMap), filter, reduce, subsequence functions and others.
Having these for free makes Sequence a bit more useful that just a type that can be used with a for each.
Let’s take a look at the IteratorProtocol definition:
public protocol IteratorProtocol {
/// The type of element traversed by the iterator.
associatedtype Element
...
...
/// - Returns: The next element in the underlying sequence if a next element
/// exists; otherwise, `nil`.
mutating func next() -> Element?
}
This simple protocol contains just a next() method, responsible for returning the next element in the sequence managed by this iterator. It’s very important that the iterator returns nil when the sequence ends, we’ll see why below, when we’ll build an infinite sequence.
Let’s build a simple iterator that produces numbers from the well known Fibonacci sequence:
class FibonacciIterator : IteratorProtocol {
var nextValues = (0,1)
var stopsAt:Int
var iterationsCount = 0
init(iteratorLength:Int){
stopsAt = iteratorLength
}
func next() -> Int?{
guard iterationsCount<stopsAt else {
return nil
}
iterationsCount += 1
let next = nextValues.0
nextValues = (nextValues.1,nextValues.0+nextValues.1)
return next
}
}
To return a finite sequence we need an additional constructor that we’ll use to specify the sequence length and return nil instead of a new element when we reach it. There is not much else to see here other than the tuple swap trick that save us a few lines, but let’s see how to use this iterator:
var fg = FibonacciIterator(iteratorLength:10)
while let fib = fg.next() {
print(fib)
}
This way we’ll iterate on the elements until nil is returned.
Implementing a Sequence for this iterator is straightforward:
class FibonacciSequence : Sequence {
var stopsAt:Int
init(sequenceLength:Int){
stopsAt = sequenceLength
}
func makeIterator() -> FibonacciIterator{
return FibonacciIterator(iteratorLength: stopsAt)
}
}
let arr = Array(FibonacciSequence(sequenceLength:10))
for f in FibonacciSequence(sequenceLength: 10) {
print(f)
}
The sequence can be used in a foreach as expected but can also be used to create other sequences like an array as seen above.
But there is no need to declare the iterator as a separated entity, we can use the AnyIterator<T> class to make this example more compact:
class CompactFibonacciSequence : Sequence {
var stopsAt:Int
init(sequenceLength:Int){
stopsAt = sequenceLength
}
func makeIterator() -> AnyIterator<Int> {
var nextValues = (0,1)
var iterationsCount = 0
return AnyIterator{
guard iterationsCount<self.stopsAt else {
return nil
}
iterationsCount += 1
let next = nextValues.0
nextValues = (nextValues.1,nextValues.0+nextValues.1)
return next
}
}
}
This will work exactly like the previous sequence, the only substantial difference is that the AnyIterator<Int> returned by makeIterator() conforms to Sequence too now, it’s not anymore just a simple object implementing IteratorProtocol like the one we started with.
Not really that useful here, considering that the iterator is already embedded in a sequence, but in some circumstances, a simple sequence generated with AnyIterator(body:) could be more than enough for what we want to do.
For instance, we could create a sequence with the first 10 numbers of the Lucas sequence, a numeric series similar to Fibonacci that starts with 2,1 instead of 0,1 generating a quite different sequence (i.e. 2, 1, 3, 4, 7, 11, 18, 29, etc…) , using just an iterator and initializing an array with it:
var nextValues = (2,1)
var iterationsCount = 0
let lucas = AnyIterator{
()->Int? in
guard iterationsCount<10 else {
return nil
}
iterationsCount += 1
let next = nextValues.0
last = (nextValues.1,nextValues.0+nextValues.1)
return next
}
let a = Array(lucas) //[2, 1, 3, 4, 7, 11, 18, 29, 47, 76]
Definitely not bad, we removed a lot of boilerplate, but since we can improve our algorithm further with a formula involving the golden ratio, let’s do it:
import Darwin
let Phi = (sqrt(5)+1.0)/2
let phi = 1/Phi
func luc(n:Int)->Int {
return Int(pow(Phi, Double(n))+pow(-phi,Double(n)))
}
c = 0
var compactLucas = AnyIterator{ c<10 ? luc(n: c+1): nil }
let a2 = Array(compactLucas) //[2, 1, 3, 4, 7, 11, 18, 29, 47, 76]
Does it really work? Yes, feel free to play around with it using the playground (zip).
To try out some of the functional(ish) facilities that Sequence provide, we’ll now build a derived sequence that will only return even numbers from the Lucas sequence:
c = 0
var evenCompactLucas = AnyIterator{ c<10 ? luc(n: c+1): nil }.filter({$0 % 2 == 0})
let a3 = Array(evenCompactLucas) //[2, 4, 18, 76]
Notice that we are redeclaring our AnyIterator because the previous one has already been used up and it will return no more elements, it has reached the end of the sequence it was able to generate and from now on it will return only nil. But this aside, you can also notice how easily we modified the original sequence to return a modified set of objects. We could perform even bolder transformations using map methods.
Infinite Sequences
But now, what it we remove the nil termination requirement described above to build an infinite sequence of all the possible Lucas numbers?
c = 0
var infiniteLucas = AnyIterator{luc(n: c+1)}
Converting the original finite sequence we had was easy, and now we have a new sequence that does not have any limit to the number of results it can generate, but it’s also easy to understand that we’ll now need a way to limit the number of elements it generates to be able to traverse the sequence using the usual control flow constructs.
And luckily the Sequence protocol comes to the rescue with one of its methods:
let a4 = Array(infiniteLucas.prefix(10)) //[2, 1, 3, 4, 7, 11, 18, 29, 47, 76]
for var f in infiniteLucas.prefix(10){
print(f)
}
This way we’ll extract 10 elements from the sequence into a newly created sequence and use it like we were used to from the previous examples.
But let’s go a step further and again apply a filter to our sequence, to obtain a sequence of even Lucas numbers:
var onlyEvenLucas = infiniteLucas.filter({$0 % 2 == 0})
for var f in onlyEvenLucas.prefix(10){
print(f)
}
Well… this will not work as expected.
Assuming you are using a playground, you’ll see an error where we declared onlyEvenLucas that will highlight that a stack overflow happened. If you wrote that in an application, you’ll see your application likely crashing instead.
The reason why this happens is related to how filter works on normal sequences, as you could already know. When we apply a filter to the original sequence the filtering is carried out instantly and all the elements of the sequence consumed eagerly, but without the terminating nil we have no way to specify when this operation should complete.
Let’s see visually what’s happening using a more verbose infinite sequence of integers that will print some text every time a value is requested from the iterator:
class InfiniteSequence :Sequence {
func makeIterator() -> AnyIterator<Int> {
var i = 0
return AnyIterator{
print("# Returning "+String(i))
i += 1
return i
}
}
}
var fs = InfiniteSequence().filter({$0 % 2 == 0}).makeIterator()
for i in 1...5 {
print(fs.next())
}
If you run this you’ll verify the behavior described above, the filtering on InfiniteSequence will start consuming the sequence… until it will not be able to proceed anymore a few minutes/hours later.
Luckily, obtaining the behavior we expected is again quite easy, we just need to lazily evaluate the infinite Lucas sequence:
var onlyEvenLucas = infiniteLucas.lazy.filter({$0 % 2 == 0})
for var f in onlyEvenLucas.prefix(10){
print(f)
}
Retrieving .lazy from the original sequence, we’ll get a new LazySequenceType on which operations such as map, flatMap, reduce or filter will be executed lazily and the real evaluation will be performed on demand only when a terminal operation (other languages call them this way) down the chain such as next or something that needs the whole sequence content will be performed.
Making your infinite sequences lazy is a required step, since Swift sequences are not lazy by default (they were in the first few releases of Swift 1.0). Detailed information about how to implement directly LazySequenceProtocol (that most of the times could be the right approach) are available in the documentation, and it’s likely I’ll do a future post on it.
Note: Thanks to Rennie for his suggestion of making the samples a bit less concise :)
Did you like this article? Let me know on Twitter!