Completely over-engineering "fizzbuzz" with infinite streams

Have you ever had that “fizzbuzz” interview question? It goes like this:

• Write a program that prints all the numbers from 1 to 100 but with multiples of 3 replaced by the word “fizz”, multiples of 5 replaced by the word “buzz”, and multiples of both replaced by “fizzbuzz”.

This is a silly interview question. Not because it’s easy, but because it’s common enough that people just reel off an implementation by rote.

Here’s one way to do it in Swift.

for i in (1...100) {
    if i % (3*5) == 0 {
        print("fizzbuzz")
    } else if i % 3 == 0 {
        print("fizz")
    } else if i % 5 == 0 {
        print("buzz")
    } else {
        print(i)
    }
}
// 1, 2, fizz, 4, buzz, fizz, 7, 8, fizz, buzz,
// 11, fizz, 13, 14, fizzbuzz, 16, 17, fizz, 19, buzz ...

But as we’ve come all this way for an interview, let’s waste everybody’s time and make it much more complicated.

We start by noticing that the range 1…100 is actually a subset of the infinite stream of natural numbers. So instead of just dealing with the problem at hand, let’s model infinity. You know, for future flexibility.

Infinity is big

We want to start with something like this:

let naturals = [1, 2, 3, 4, 5, 6, ...]

How can we make a data type that’s infinite? Most computers don’t like the concept. They get antsy when you tell them to allocate an infinite number of bytes just so you can store every single number in them.

We have to be a little sly. We have to trick the computer into modelling an infinite stream without it realising.

The Swift way

Swift has some useful built-in features for building infinite data structures.

Take this pretty example from Erica Sadun which produces an infinite stream of numbers through some undercover voodoo.

var n = 1
let naturalNumbers = anyGenerator{n++}

for i in naturalNumbers {
    print(i)
}
// 1, 2, 3, ...

We can apply some interesting transformations to these streams too.

let evenNumbers = lazy(naturalNumbers).map {$0 * 2}
// 2, 4, 6, ...

Even though we’re operating on an infinite stream of numbers, the computer is happy. The map function in this example is lazy; it calculates values as needed rather than all up front — uh oh, the interviewer is yawning. He’s seen this before.

Let’s demonstrate our prowess and implement infinity from scratch. Because, Not Invented Here.

The DIY way

Streams feel a bit like linked lists, so let’s start there. A stream will have just two pieces: the current value for the head of the stream; and a tail which is “the rest” of the stream. We’ll use generics so it can hold any type we like.

class Stream<T> {
    let head: T
    let tail: Stream
    
    init(head: T, tail: Stream) {
        self.head = head
        self.tail = tail
    }
}

The problem with this approach is we have to create the tail in advance, which we already know ain’t gonna fly with the computer.

    let naturalNumbers = Stream(head: 0,
        tail: Stream(head: 1,
            tail: Stream(head: 2,
                tail: ...)))

Thunks (or promises, or generators, or zero arity lambdas, …)

Since we’re only using one value at a time from the stream, there is a loophole. We don’t need to make the whole linked list in advance, we just need to have values ready when we get to them.

Instead of making the tail an actual stream, let’s make it a function that returns a stream. Since functions aren’t evaluated until we explicitly call them, it can be a promise to produce the rest of the stream on demand.

struct Stream<T> {
    let head: T
    let tail: () -> Stream
}

The type of the tail is () -> Stream which is a function that takes no arguments and returns another Stream. These kind of functions are sometimes called thunks. You should definitely drop that word into the interview.

While we’re at it, let’s extend our stream with a property that evaluates our thunk. We’ll need this so we can advance through the stream. Note the parentheses that call the tail to unwrap the stream it contains.

extension Stream {
    var next: Stream {
        return tail()
    }
}

A stream of natural numbers

Now we can use our new type to make the stream of natural numbers. We’ll do this by writing a function that takes a number as a starting point and returns a stream with that number as its head, and a thunked stream beginning at the next number for its tail.

func integersFrom(n: Int) -> Stream<Int> {
    return Stream(head: n, tail: {integersFrom(n+1)})
}

let naturals = integersFrom(1)

We’ve modelled an infinite stream of integers beginning at 1! The braces around the tail argument are critical as they make it a thunk which will not be evaluated (yet) preventing the apparent infinite loop.

Let’s take a look at some of the numbers.

extension Stream {
    func print(n: UInt) {
        if n > 0 {
            Swift.print(head)
            next.print(n-1)
        }
    }
}

naturals.print(5)
// 1, 2, 3, 4, 5

Operating on infinite streams

Being able to iterate over our infinite streams is handy but we can make real magic when we transform them.

Let’s say we want to double and print the numbers in our stream.

One approach is to write a print loop with some extra logic.

func printDoubledStream(stream: Stream<Int>, _ n: UInt) {
    if n > 0 {
        print(stream.head * 2)
        printDoubledStream(stream.next, n-1)
    }
}

printDoubledStream(naturals, 5)
// 2, 4, 6, 8, 10

Although this works, it mixes stream iteration with some custom transformation code, reducing readability. Worse, it only works with streams of ints (which incidentally is why we couldn’t make it an extension function), so we’d need to write lots of similar code to do similar things.

And besides, this is hardly over-engineered at all, and unlikely to land us this fancy new job.

An alternative is to make a new stream from the natural numbers that doubles every number.

We’ll do this by recreating the built-in map function we saw earlier. The function returns a new stream with a given function applied to the head item, and recursively mapped to the tail.

extension Stream {
    func map<U>(f: T -> U) -> Stream<U> {
        return Stream<U>(head: f(head), tail: {self.next.map(f)})
    }
}

Now we can map a doubling function to our stream, and use our existing print function to display the result.

let doubledNaturals = naturals.map {$0 * 2}

doubledNaturals.print(5)
// 2, 4, 6, 8, 10

Following a similar pattern, we can create a whole bunch of different functions which operate on our infinite streams.

This one zips two streams together with a custom function.

extension Stream {
    func zip<U, V>(other: Stream<U>, with: (T, U) -> V) -> Stream<V> {
        let zippedHead = with(head, other.head)
        let zippedTail = {self.next.zip(other.next, with: with)}
        return Stream<V>(head: zippedHead, tail: zippedTail)
    }
}

What can we do with zip? How about producing a stream of playing cards?

First we’ll need some arrays to hold the card suits and ranks (we’ll ignore picture cards for now).

let suitItems = ["♣️", "♦️", "♠️", "♥️"]
let rankItems = Array((2...10))

But how can we make a stream out of these? One way is to cycle through the elements endlessly.

extension Array {
    func cycle(index: Int = 0) -> Stream<T> {
        let head = self[index]
        let nextIndex = (index + 1) % count
        let tail = {self.cycle(nextIndex)}
        return Stream(head: head, tail: tail)
    }
}

let suits = ["♣️", "♦️", "♠️", "♥️"].cycle()
// ♣️, ♦️, ♠️, ♥️, ♣️, ♦️, ♠️, ♥️, ...

let ranks = Array((2...10)).cycle()
// 2, 3, 4, 5, 6, 7, 8, 9, 10, 2, 3, 4, ...

Now we can zip these two streams together.

First we map the ints in the ranks stream into Strings then zip the resultant stream together with the suits using the built-in string concatenation function, +.

To make our code more readable we’ll first redefine the old toString Swift function, cruelly taken from us in Swift 2.

func toString<T>(value: T) -> String {
    return String(value)
}

let cards = ranks.map(toString).zip(suits, with: +)
// 2♣️, 3♦️, 4♠️, 5♥️, 6♣️, 7♦️, 8♠️, 9♥️, 10♣️, 2♦️, 3♠️, 4♥️, ...

Er, fizzbuzz?

Right, right. We now have all the tools we need to implement our grandiose fizzbuzz and smash this interview.

We’ll make an infinite stream of numbers, fizzes, buzzes and fizzbuzzes. Then we’ll print the first 100 items in it.

We’ll start with a cycled stream where every 3rd item is a “fizz”, and another where every 5th is a “buzz”.

let fizz = ["", "", "fizz"].cycle()
// "", "", "fizz", "", "", "fizz", ...

let buzz = ["", "", "", "", "buzz"].cycle()
// "", "", "", "", "buzz", "", "", "", "", "buzz", ...

Zip these together using + and we’re starting to get somewhere.

let words = fizz.zip(buzz, with: +)
// "", "", "fizz", "", "buzz", "fizz", "", "", "fizz", "buzz",
// "", "fizz", "", "", "fizzbuzz", "", ...

Our infinite stream now has the fizzes, buzzes and fizzbuzzes in the right places, but we’re missing the numbers. Let’s create a stream of numbers and zip them in as well.

First we’ll map the numbers to strings so they’re the same type as our other stream.

let numbers = integersFrom(1).map(toString)
// "1", "2", "3", ...

Next we zip them with our words stream by choosing the word if it’s present, or the corresponding number otherwise.

let fizzbuzz = words.zip(numbers) { word, number in
	word.isEmpty ? number : word
}

Finally, we print out the first 100.

fizzbuzz.print(100)
// "1", "2", "fizz", "4", "buzz", "fizz", "7", "8", "fizz", "buzz",
// "11", "fizz", "13", "14", "fizzbuzz", "16", ...

Q.E.D.

(So we didn’t get the job… some highfalutin’ talk about YAGNI…)