# 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.