Swift Stack for fun

The other day I had some spare time and I started exploring the idea of a Stack in Swift using protocols. For what? For fun.

A Stack is a data structure that stores a collection of elements. It defines two essential operations: push and pop.

protocol Stack {
    typealias Element

    mutating func push(value: Element)
    mutating func pop() -> Element?
}

That’s all you need to have a stack. But usually is useful to have a couple more operations in a stack: top (also called peek) and isEmpty. The cool part is that this are non-essential operations, meaning that they can be implemented using the essential ones. This allows us to implement them in a extension protocol, and make them available for free to any concrete implementation of a Stack.

extension Stack {

    mutating func isEmpty() -> Bool {
        if let value = pop() {
            push(value)
            return false
        } else {
            return true
        }
    }

    mutating func top() -> Element? {
        let top = pop()
        if let value = top {
            push(value)
        }
        return top
    }

}

With this in place we can write some Stack implementations by just implementing the two essential functions.

For example we can easily wrap an array:

struct ArrayStack<T>: Stack {
    typealias Element = T

    private var contents = Array<Element>()

    mutating func push(value: Element) {
        contents.append(value)
    }

    mutating func pop() -> Element? {
//        return isEmpty() ? .None : contents.removeLast() // calling isEmpty from here crashes the compiler
        return contents.isEmpty ? .None : contents.removeLast()
    }
}

And now we have available an ArrayStack type that has all four functions, by just implementing two.

var arr = ArrayStack<Int>() // []
arr.push(1) // [1]
arr.push(2) // [1, 2]
arr.pop() // 2
arr.isEmpty() // false // calling isEmpty here works just fine!
arr.top() // 1
arr.top() // 1
arr.pop() // 1
arr.isEmpty() // true

This is the approach that the Swift standard library uses and seems like a really cool way of solving problems and defining types that other clients of the API can extend as they wish.

One obvious caveat of the default implementation of the non-essential methods is that they are not optimized at all. For example the top function does a pop and then a push to let the stack unmodified.

But Swift has us covered here. Remember that those implementations are used by any Stack that doesn’t provide it’s own implementations. Meaning that, for example, our ArrayStack can easily implement the isEmpty method using it’s internal array.

mutating func isEmpty() -> Bool {
    return contents.isEmpty
}

This is really nice. Making available default but unoptimized implementations for any type that implements our Protocol is nice, but having the ability to refine those implementations and provide optimized ones is huge.

For fun I implemented EnumStack, an enum based Stack; and ClassStack a reference type Stack. There are other fancy ways you can implement it but I stopped here.

I then tried to add more things to the Protocol to make it work better with the rest of the language but I’ve found some problems (Xcode 7b6).

You can read in the pop function of the ArrayStack how calling isEmpty from there just crashes the compiler.

Then I wanted to add the ability to Stack to be created as an Array using the nice ArrayLiteralConvertible protocol. (I created a Gist with this problem for feedback)

extension Stack: ArrayLiteralConvertible {}

This just doesn’t compile because Extension of protocol ‘Stack’ cannot have an inheritance clause. Fair enough. I’ve also found the same issue when trying to give default implementations for CustomStringConvertible to any Stack.

I then tried another approach.

extension Stack where Self: ArrayLiteralConvertible  {

    init(arrayLiteral elements: Self.Element...) {
        self.init()
        for value in elements {
            push(value)
        }
    }

}

extension ArrayStack: ArrayLiteralConvertible {}

I feel like this should be enough. It’s not really magic because we don’t have the ability to give it to any Stack automatically but it could work. But then using it just crashes (in b5 it just get stuck).

print("before")
var tin: ArrayStack<Int> = [1, 2, 3] // EXC_BAD_ACCESS
print("after") // never gets printed

If I try to specify the ArrayLiteralConvertible inheritance in the protocol itself, and then add a default implementation via a extension the compiler also gives an error:

Initialiser requirement 'init(arrayLiteral:)' can only be satisfied by a 'required' initialised in the definition of a non-final class.

I’m sure I’m missing something but I don’t know what. Any help would be appreciated.

Don’t be too powerful

On my way to having fun with protocols I thought in making Stack conform to SequenceType. That would automatically give a lot of nice features to the Stack but then I realized the trouble that it could make.

In my opinion the main characteristic of an Stack is that it’s a restricted data structure. And restrictions are good. You want to use a Stack to keep a LIFO order, and adding more features to that just makes the intention unclear. In my opinion if I wanted to use any of those features I would be using a simple Array, not a Stack.

This is one of those things that can get easily really wrong if it’s implemented for example like the Java Stack does.

Class Stack<E>
java.lang.Object
    java.util.AbstractCollection<E>
        java.util.AbstractList<E>
            java.util.Vector<E>
                java.util.Stack<E>
All Implemented Interfaces:
Serializable, Cloneable, Iterable<E>, Collection<E>, List<E>, RandomAccess

Having a Stack and being able to access any element or even remove any element is a little useless in my opinion. I always like to use the correct types to express what I want to allow.

That’s all. If you want to check the rest of the code check out the playground. Stack.playground