Experimenting with Swift Sequences and Generators

Posted by Umberto Raimondi on , 也可以阅读中文版

This post has been updated to Swift 3 here.

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.

Bind

Get the playground for this post from GitHub or zipped.

The SequenceType 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 SequenceType {
    typealias Generator : GeneratorType
	/// Return a *generator* over the elements of this *sequence*.
    ///
    /// - Complexity: O(1).
	public func generate() -> Self.Generator
	...
	...
}

The protocol contains an associated type (Swift weird way of making protocols generic) that refers to the GeneratorType protocol, we’ll need to implement this too in some way when creating a sequence. Our custom SequenceType will return a custom generator with a specific element type when generate() 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 SequenceType a bit more useful that just a type that can be used with a for each.

Let’s take a look at the GeneratorType definition:


public protocol GeneratorType {
    typealias Element
    /// Advance to the next element and return it, or `nil` if no next
    /// element exists.
    public mutating func next() -> Self.Element?
}

This simple protocol contains just a next() method, responsible for returning the next element in the sequence managed by this generator. It’s very important that the generator returns nil when the sequence ends, we’ll see why below, when we’ll build an infinite sequence.

Let’s build a simple generator that produces numbers from the well known Fibonacci sequence:


class FibonacciGenerator : GeneratorType {
    var last = (0,1)
    var endAt:Int
    var lastIteration = 0
    
    init(end:Int){
        endAt = end
    }
    
    func next() -> Int?{
        guard lastIteration<endAt else {
            return nil
        }
        lastIteration += 1
        
        let next = last.0
        last = (last.1,last.0+last.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 generator:


var fg = FibonacciGenerator(end:10)

while let fib = fg.next() {
    print(fib)
}

This way we’ll iterate on the generator elements until nil is returned.

Implementing a SequenceType for this generator is straightforward:


class FibonacciSequence : SequenceType {
    var endAt:Int
    
    init(end:Int){
        endAt = end
    }
    
    func generate() -> FibonacciGenerator{
        return FibonacciGenerator(end: endAt)
    }
}

let arr = Array(FibonacciSequence(end:10))

for f in FibonacciSequence(end: 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 generator as a separated entity, we can use the AnyGenerator<T> class to make this example more compact:


class CompactFibonacciSequence : SequenceType {
    var endAt:Int
    
    init(end:Int){
        endAt = end
    }
    
    func generate() -> AnyGenerator<Int> {
        var last = (0,1)
        var lastIteration = 0
        
        return AnyGenerator{
            guard lastIteration<self.endAt else {
                return nil
            }
            lastIteration += 1
            
            let next = last.0
            last = (last.1,last.0+last.1)
            return next
        }
    }
}

This will work exactly like the previous sequence, the only substantial difference is that the AnyGenerator<Int> returned by generate() conforms to SequenceType too now, it’s not anymore just a simple GeneratorType like the one we started with.

Not really that useful here, considering that the generator is already embedded in a sequence, but in some circumstances, a simple sequence generated with AnyGenerator(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 a generator and initializing an array with it:


var last = (2,1)
var c = 0

let lucas = AnyGenerator{
    ()->Int? in
    guard c<10 else {
        return nil
    }
    
    c += 1
    let next = last.0
    last = (last.1,last.0+last.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 = AnyGenerator{ c<10 ? luc(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 SequenceType provide, we’ll now build a derived sequence that will only return even numbers from the Lucas sequence:


c = 0
var evenCompactLucas = AnyGenerator{ c<10 ? luc(c+1): nil }.filter({$0 % 2 == 0})
let a3 = Array(evenCompactLucas) //[2, 4, 18, 76]

Notice that we are redeclaring our AnyGenerator 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 = AnyGenerator{luc(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 SequenceType 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 generator:


class InfiniteSequence :SequenceType {
    func generate() -> AnyGenerator<Int> {
        var i = 0
        return AnyGenerator{
            print("# Returning "+String(i))
            i += 1
            return i
        }
    }
}

var fs = InfiniteSequence().filter({$0 % 2 == 0}).generate()

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 a LazySequenceType (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.

Did you like this article? Let me know on Twitter!

This is the blog of Umberto Raimondi, you can reach me at me@this domain.

I'm also on Twitter and GitHub.

Subscribe via RSS or email.