List

February 11, 2018

Swift doesn't have a List type built in.

If you studied CS in school, you have played with lists before. If you haven't, or if it's been a while, I found this to be fun to play with.

Here I'm thinking of a list that consists of a head which is a single element and a tail which is itself a List representing the rest of the List. The tail is constructed by attaching the head to an existing List. We'll use two associated types to refer to element of type A and the List of type A. Traditionally this case is known as cons.


enum List<A> {
    case empty
    case cons(head: A, tail: List)
}

Here's today's sample code and here's the Playground it comes from so you can follow along or pause now and then to work ahead.

Since the tail is itself a List, we can then take the head and tail of the tail to continue to explore the list until the tail is the empty List and then we are done. In Swift we have to use the indirect keyword to make this work.


indirect enum List<A> {
    case empty
    case cons(head: A, tail: List)
}

Now we can create an empty list, a list containing only the number 6 (the tail is the empty list), and a list containing 2, 3, and 4.


let emptyList = List<Int>.empty

let six = List.cons(head: 6, tail: emptyList)

let twoThreeFour
    = List.cons(head: 2,
                tail: List.cons(head: 3,
                                tail: List.cons(head: 4,
                                                tail: emptyList)))

Wow, that last one was a bit of a pain.

Let's create an init that allows us to pass in zero or more elements of type A in an array of type [A] to create a list.

If we pass in no elements then we return the empty list.


extension List {
    init(_ xs: [A]) {
        if xs.isEmpty {self = List.empty}
        else {
	        // ...
        }
    }
}

If we pass in one or more elements, we make a mutable copy of xs and remove the first element. This first element will become the head and we recursively call the constructor passing in the reduced array. This will terminate when the reduced array is empty.


extension List {
    init(_ xs: [A]) {
        if xs.isEmpty {self = List.empty}
        else {
            var xs = xs
            let first = xs.removeFirst()
            self = List.cons(head: first, tail: List(xs))
        }
    }
}

Now it's much easier to create a list with multiple elements.


let fiveSixSeven = List([5,6,7])

Actually, now that I see this, I don't really like it. I'd rather create my list like this.


let fiveSixSeven = List(5,6,7)

Let's make the existing init private and expose one that takes a variadic argument instead.


extension List {
    private init(_ xs: [A]) {
        if xs.isEmpty {self = List.empty}
        else {
            var xs = xs
            let first = xs.removeFirst()
            self = List.cons(head: first, tail: List(xs))
        }
    }
    
    init(_ xs: A...){
        self.init(xs)
    }
}

We now create lists like this.


let fiveSixSeven = List(5,6,7)
let anotherEmptyList = List<Int>()

It will be easier to understand the structure of these lists with a nicer description.


extension List: CustomStringConvertible  {
    var description: String {
        switch self {
        case .empty:
            return "( )"
        case let .cons(head, tail):
            return "(\(head)" + tail.description + ")"
        }
    }
}

Look at the right side of the playground and emptyList and anotherEmptyList are represented like this ( ). six is (6( )), twoThreeFour is (2(3(4( )))), and fiveSixSeven is (5(6(7( )))).

Before we wrap up for today, take another look at the representation for fiveSixSeven and contrast it with the array [5,6,7].

In the array it is just as easy to retrieve the zeroth element as it is the second.

[5,6,7][0] is 5 and [5,6,7][2] is 7.

Getting the zeroth element of the list fiveSixSeven is trivial. We just need a method that returns the head. Let's use a computed property.

Actually, maybe this isn't trivial. We need to decide what to do if the list is empty. We could return an optional from the call to head or we could through a fatalError. I actually don't care much either way, but I've decided that, if it exists, head should return an element of type A and not of type A?.


extension List {
    var head: A {
        guard case .cons(let head, _) = self  else {
            fatalError("The list is empty.")
        }
        return head
    }
}

Now we can use it like this.


fiveSixSeven.head

This gives the expected result 5.

OK, now how do we get the second element?

First, let's add a computed property that returns the tail.

I should have mentioned it earlier, but when I say "let's", you can try it too.


extension List {
    var head: A {
        guard case .cons(let head, _) = self  else {
            fatalError("The list is empty.")
        }
        return head
    }
    var tail: List {
        guard case .cons(_, let tail) = self else {
            fatalError("The list is empty.")
        }
        return tail
    }
}

Now we can create a method to return the nth element.


extension List {
    var head: A {
        guard case .cons(let head, _) = self  else {
            fatalError("The list is empty.")
        }
        return head
    }
    var tail: List {
        guard case .cons(_, let tail) = self else {
            fatalError("The list is empty.")
        }
        return tail
    }
    func element(number n: Int) -> A {
        guard n > 0 else {return head}
        return tail.element(number: n - 1)
    }
}

We can now use it like this to get any of the elements.


fiveSixSeven.element(number: 0)
fiveSixSeven.element(number: 1)
fiveSixSeven.element(number: 2)

If we try to retrieve the next element we get a fatal error.

We've got the fundamentals of our list implementation. Next time we'll look at right and left folds.