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.