Looking back at the classics: Generic data types in Swift (Part 3)

Looking back at the classics: Generic data types in Swift (Part 3)

In our last couple of articles in this series, we’ve discussed many details about generic development in Swift: how to implement them and its benefits and how to express ourselves better in our newly discovered generic language. We’ve also learned about two of the basic foundation data types in computer science history: the singly-linked list and the stack, and how to implement them as generic types in Swift.

So, there’s more to talk about? Sure! As you may know, generic development keeps advancing in our iOS/MacOS development world. In last week’s WWDC, Apple announced support for generics in Objective-C (update: link removed by source). That’s big news! It means not only that our now-classic programming language isn’t dead yet, but also that old-fashioned developers get to use these features in their current Objective-C projects.

Let’s keep digging on what we can achieve with generics and we’ll also tell you about one of the most clever data-types ever created: Chris Okasaki’s Banker’s Queue.

Associated types

We’ve already seen that we can tell our generic types and functions to use types that conform to certain protocols. What if we want those protocols to declare functions that have some type requirements? The problem is that, while we can create generic functions, structs, class and enums, we can’t do the same way with protocols. That’s the whole purpose of associated types: they give us the chance to restrict the parameters we take in our generic types and functions that are declared in protocols.

Swift’s associated types have a lot in common with Scala’s abstract types. The problem associated types are trying to solve is nicely explained by Martin Odersky in this interview about Scala’s data types. To put it shortly: imagine you define a protocol for Animals. That protocol would have a method for the animal to eat. Then you create all sorts of animals: cows, birds, turtles. Cows eat grass, but birds and turtles certainly don’t like grass. How do you declare the “eat” function inside a protocol to handle this fact of nature?

We’re going to exemplify this problem with cars and fuels. There are a lot of different types of passenger cars based on the fuel they consume: electricity, gas-oil, and hybrid engines that use both. As consumers we’re faced with these and other choices when buying a new vehicle. How could we state these choices in Swift code? First, let’s start to model our different fuel types:

enum ContaminationLevel {
    case Low
    case High
    case NoWay
}

struct Gasoil {
    let contaminationLevel : ContaminationLevel = .High
}

struct Electricity {
    let contaminationLevel : ContaminationLevel = .Low
}

struct LeadedGas {
    let contaminationLevel : ContaminationLevel = .NoWay
}

Each fuel type has a contamination level, but they could have all sorts of methods like different implementions for the combustion processes. Now it’s time to implement our available vehicle models:

protocol Vehicle {
    «typealias FuelType»

    func refuel(f: FuelType)
}

class RegularCar : Vehicle {
    «typealias FuelType = Gasoil»

    func refuel(f: FuelType) {
        println("Refueling with juicy gas!")
    }
}

class ElectricalCar : Vehicle {
    typealias FuelType = Electricity

    func refuel(f: FuelType) {
        println("Refueling with electrons!")
    }
}
»typealias|The <code>typealias</code> keyword has two uses related to associated types. When declaring a new protocol, we use it to state the names of all the associated types we need.«
»typealias|But when we want to implement the protocol in a class, struct, or enum, we use <code>typealias</code> to tell our compiler what will be the actual type of the abstract type the protocol takes.«

As you can see, each kind of car conforms to the Vehicle protocol: that means that they’re required to implement a refuel function. And to do so, each one needs to specify the kind of fuel it needs to work. This is done by using the typealias reserved word. In our protocol declaration, we use typealias to declare all the different names our associated types will have. We can have as many as we want, as long as our conforming types specify them later. And that is precisely what we do in each car implementation block. For each associated type in the Vehicle protocol, we use the equals sign to tell the compiler what FuelType will mean in run-time. So RegularCar instances will use Gasoil as fuel, but ElectricalCar ones will use Electricity.

This is a really simple example, but there are associated types all over the place in Swift’s standard library. For instance, that’s how you specify the type of elements you’re running through when you conform to the SequenceType protocol (to be able to use for loops in your custom collections).

You’re probably saying: “Yadda yadda yadda, I came here to learn about generics, not that weird stuff!” Hold on, all this talk about associated types has a lot to do with generic development. We know that our generic types can conform to certain protocols, and one cool thing about that is that we can apply conditions on the protocols they conform to. To illustrate this, let’s build some generic functions that exemplify the decision-making process a consumer needs to go through while choosing a new car (based on its fuel type):

func buyCarWithoutThinkingTooMuch<T : Vehicle>(vehicle: T) {
    // ...
}

func buyEnviromentConciousCar<T: Vehicle «where» T.FuelType == Electricity>(vehicle: T) {
    // ...
}

func compareEmissionRatesOfTwoVehicles<T, S «where» T : Vehicle, S: Vehicle, T.FuelType == S.FuelType>(vehicleA: T, vehicleB: S) {
    // ...
}
»where clause|We can use the <code>where</code> clause in your generic types declaration to apply certain conditions to it. Here we're asking that our generic type of vehicle is one that has electricity as its main source of power.«
»where clause|Not only we can check if a certain vehicle uses a certain kind of fuel, but we can also check if the fuel types of two different generic types are equal.«

As you can see, our first function takes a generic type T that conforms to the Vehicle protocol. Well, that’s nice for people who won’t think too much about the contamination levels or refueling costs of their new car. Nevertheless, not all buyers are like that, so we have the buyEnviromentConciousCar function that enforces users to buy an electric car (calling the function passing a vehicle that’s not electric just won’t compile). We’ve also added another function that compares the emission rates of two vehicles that share the same power source (in case we had a set of several models to choose from), something we can achieve by using the where clause to compare the associated types of two different generic types.

While working with associated types in our generic development, the only available operation (at least for now) is to check for equality. It would have been cool to be able to negate (i.e. be able to restrict cars that use leaded gas), and we hope that this is implemented by Apple in the future. If you want to dig deeper into this matter, we highly recommend this awesome article by Russ Bishop about associated types in Swift, a must-read in our humble opinion.

Okasaki’s Banker’s Queue

Remember the singly-linked list? We didn’t use it as our first example of classic data type by chance. A lot of types have used those kind of lists as their foundation structure in the past, as we saw in our previous article in the series with our implementation of the Stack. Another fine use of the singly linked list is creating queues, which are the opposite to stacks: instead of having a LIFO (Last In First Out) we’ll handle a FIFO (First In First Out). As its name implies, queues are really useful while handling items we need to put on hold and later retrieve to perform any action in the future. Can we really implement them with singly-linked lists as we did with stacks?

Enqueuing items in the queue is analogous to the push operation in the stack, we can just prepend items to an internal list and we’re done. But dequeuing is not that easy, as we need to access the last element of the queue, and that means to run through every element over and over again in each execution of that operation. That’s not nice! So, should we drop out singly-linked lists as a feasible solution to this problem and resort to using doubly-linked ones?

Not so fast: in computer science, surrender is almost never an option. As in the Street Fighter game series, we can shout “here comes a new challenger”: Chris Okasaki and his Banker’s Queue abstract data type. Just by using two singly linked-lists working together he was able to create a queue that allows us to access the first and the last items in constant time. Well, almost constant time. His work talks about the concept of amortization (that is: if you have a really slow operation that is executed less frequently than other really fast operations, you can reach near-constant time). To learn more about the theoretical details of this concept, check out his thesis papers or watch the awesome talk by Daniel Spiewak about Functional Data Structures in Scala. The latter is a must-watch resource if you’re interested in creating your own data types.

How does it work? Basically, we’re going to be maintaining two linked-lists, a front one for dequeuing and a rear one for enqueuing. Once in a while, we’ll perform a check operation that will reverse the rear list and append it to the front one. That’s about it! Every time the user dequeues an item we check the sizes of both lists and if the front list gets smaller than the rear one, we perform this check to maintain the structure of the queue. Reversing a list and concatenating are both expensive operations, that’s for sure. But with Banker’s Queue the bigger the queue gets, the less frequent our calls to check will be. That’s the power of amortization to reduce the impact of the singly-linked list’s drawbacks.

Let’s get our hands dirty and implement our own Swift Banker’s Queue:

struct BankersQueue<T> {
    let front : List<T>
    let rear : List<T>
    let fSize : Int
    let rSize : Int

    init(fSize: Int, front: List<T>, rSize: Int, rear: List<T>) {
        self.fSize = fSize
        self.front = front
        self.rSize = rSize
        self.rear = rear
    }
}

extension BankersQueue {
    static func check(bq: BankersQueue) -> BankersQueue {
        if bq.rSize <= bq.fSize {
            return bq
        } else {
            let fSize2 = bq.fSize + bq.rSize
            // You can find the complete implementation of List's reverse and append methods in our interactive Playground :)
            let front2 = bq.front.append(bq.rear.reverse())
            return BankersQueue(fSize: fSize2, front: front2, rSize: 0, rear: List())
        }
    }

    func enqueue(item: T) -> BankersQueue {
        return BankersQueue.check(BankersQueue(fSize: self.fSize, front: self.front, rSize: self.rSize + 1, rear: self.rear.cons(item)))
    }

    func dequeue() -> (item: T?, queue: BankersQueue?) {
        switch self.front.count {
        case 0: return (nil, nil)
        default: return (self.front.head!, BankersQueue.check(BankersQueue(fSize: self.fSize - 1, front: front.tail!, rSize: self.rSize, rear: self.rear)))
        }
    }
}

As you can see above, our queue has four properties: two for the internal lists and two for their respective sizes. The enqueue operation just returns a new queue with an element prepended to the rear list. On the other hand the dequeue returns a tuple with two items: the head of the front list, and a new queue containing the tail of the front list and the current rear list. But before passing the queue to the user, we perform the maintenance operation check to keep our queue’s internal structure stable (and its implementation is really a simple translation of the logic we just talked about: reversing and concatenating). So, with really little work we have a queue that has almost no penalty by using simple singly-linked lists as the source of its data! And, of course, with the safety that provides us the use of immutability.

Chris Okasaki’s work is almost 20 years old, but even now it’s an example of how, just armed with raw cleverness, we can use data types as old as computer science itself to keep innovating. Keep in mind that, as always, you can play with the source files of this article by downloading our interactive Playground. Keep reading our future posts in the series for more generic goodies! And if you have any questions, opinions, or suggestions, just contact us through Facebook, Twitter or the comments section below.

blog comments powered by Disqus

Ensure the success of your project

47 Degrees can work with you to help manage the risks of technology evolution, develop a team of top-tier engaged developers, improve productivity, lower maintenance cost, increase hardware utilization, and improve product quality; all while using the best technologies.