Fibonacci Sequence with Swift

The aim of this post is showing how to conform to Sequence protocol and create a custom sequence. To make it less boring, we can create a new type and call it FibonacciSequence which gets nth desired number then iterate over values.

The requirement to conform to Sequence protocol is fairly simple, you need to provide a makeIterator() method that returns an iterator. The code should look like this:

struct FibsSequence: Sequence {
    private var upTo: Int
    
    init(upTo: Int) {
        self.upTo = upTo
    }
    
    func makeIterator() -> FibsIterator {
        return FibsIterator(upTo: upTo)
    }
}

Our makeIterator() returns another custom type which conforms to IteratorProtocol. This type obliges the conformer to provide a method to supply the values of the sequence one at a time. The only method should be implemented is next() which advances to the next element and returns it, or returns nil if no next element exists:

struct FibsIterator: IteratorProtocol {
    private var state:(UInt, UInt) = (0, 1)
    private var upTo: Int
    private var counter = 0
    
    init(upTo: Int) {
        self.upTo = upTo
    }
    
    mutating func next() -> UInt? {
        guard upTo > counter else {return nil}
        guard upTo > 0 else {return nil}
        
        let upcomingNumber = state.0
        state = (state.1, state.0 + state.1)
        counter += 1
        
        return upcomingNumber
    }
}

In this type we have three private variables, which are clearly named, and a mutating function. Being mutating is not strictly necessary in general but since we want to keep track of iterator and update it, it is required here. The next() function returns optional UInt, optional because at some point we want to exit the function unless we deliberately want to make the code crash!

There are two exit points in the function, first one checks against nth element, if it is bigger than what user initially asked, it quits. The other one is to makes sure the nth element is a positive one.

Now we have a custom type which returns Fibonacci sequence up to a certain index in the series, indicated during initialization.

for (index, fib) in FibsSequence(upTo: 15).enumerated() {
    print("fib: \(fib), index: \(index + 1)")
}

****************************
fib: 0, index: 1
fib: 1, index: 2
fib: 1, index: 3
fib: 2, index: 4
fib: 3, index: 5
fib: 5, index: 6
fib: 8, index: 7
fib: 13, index: 8
fib: 21, index: 9
fib: 34, index: 10
fib: 55, index: 11
fib: 89, index: 12
fib: 144, index: 13
fib: 233, index: 14
fib: 377, index: 15

Whole code is available on github.

Update:

After posting this on reddit a user, Nobody_1707, suggested a shorter version of the code which is:

public struct FibSequence: Sequence, IteratorProtocol {
    private var state: (UInt, UInt) = (0, 1)
    public init() { }
    public mutating func next() -> UInt? {
        guard state.1 >= state.0 else { return nil }
        defer { state = (state.1, state.0 &+ state.1) }
        return state.0
    }
}

for (i, fib) in zip(0..., FibSequence().prefix(15)) {
    print("fib(\(i)) = \(fib)")
}

Leave a Comment

This site uses Akismet to reduce spam. Learn how your comment data is processed.