An algebraic data type is a type that’s the union of other data types. That is, it’s a type that may be one of several other types. Here’s how we would implement a linked list as an algebraic data type in Swift:
enum LinkedList<Element> {
case empty
indirect case node(data: Element, next: LinkedList)
}
This defines an enum called LinkedList that might either be .empty or a .node that points to another LinkedList. There are three interesting things to note. The first is that we’ve created a generic data type, so the type of Element is declared by the consumer of LinkedList. The second is that the .node case uses LinkedList recursively, and must therefore be marked with indirect. The third is that since the .empty case has no parameters, the parenthesis may be omitted.
Here’s how we define instances of LinkedList:
let a: LinkedList<Int> = .empty
let b: LinkedList<Int> = .node(data: 1, next: .node(data: 2, next: .empty))
To work with an algebraic data type, we deconstruct it using pattern matching. Here’s how we would print a LinkedList:
enum LinkedList<Element>: CustomStringConvertible {
'' // cases omitted for brevity
var description: String {
switch self {
case .empty:
return "(end)"
case let .node(data, next):
return "(data), (next.description)"
}
}
}
let b: LinkedList<Int> = .node(data: 1, next: .node(data: 2, next: .empty))
print("b: (b)") // => b: 1, 2, (end)
We’ve implemented the CustomStringConvertible protocol so that we can use string interpolation to print LinkedList instances. While it is possible in Swift to pattern match using an if case statement, the switch is preferable because the compiler will warn us if we’ve forgotten to handle a case. This safety is one big advantage that algebraic data types have over their classical counterparts. In a traditionally implemented linked list, you would have to remember to check if the next pointer was null to know if you were at the end. This problem gets worse as the number of cases increase in more complex data structures, such as full binary range trees with sentinels.
Note that since the description instance variable only has a getter, we do not need to use the more verbose syntax:
var description = {
get {
// etc
}
set {
// etc
}
}
Our print function was useful, but in order to do interesting things we need to be able to modify algebraic data types. Rather than mutate the existing data structure, we’ll return a new data structure that represents the result after the requested operation. Since we’re not going to mutate the original data structure, we’ll follow the Swift 3 naming convention of using a gerund for our methods. Here’s how we would add an .inserting method to LinkedList:
enum LinkedList<Element>: CustomStringConvertible {
// cases and "description" omitted for brevity
func inserting(e: Element) -> LinkedList<Element> {
switch self {
case .empty:
return .node(data: e, next: .empty)
case .node:
return .node(data: e, next: self)
}
}
}
let c = b.inserting(e: 0)
print("c: (c)") // => c: 0, 1, 2, (end)
The key is that we’re returning a new LinkedList that represents the result after the insertion. Notice how in the .node case, we do not need to pattern match on .node(data, next) because data and next are not needed in order to construct the new .node; we can simply use self as the next: node.
Finally, let’s implement the classic “reverse a linked list” interview question using our algebraic data type:
enum LinkedList<Element>: CustomStringConvertible {
// cases, "description", and "insert" omitted for brevity
func appending(_ e: Element) -> LinkedList<Element> {
switch self {
case .empty:
return .node(data: e, next: .empty)
case let .node(oldData, next):
return .node(data: oldData, next: next.appending(e))
}
}
func reversed() -> LinkedList<Element> {
switch self {
case .empty:
return self
case let .node(data, next):
return next.reversed().appending(data)
}
}
}
print("reversed c: (c.reversed())") // => reversed c: 2, 1, 0, (end)
I’ll leave it as an exercise to the reader to figure out what the running time for this algorithm is.
Here’s the Playground on GitHub
