Linked lists and trees

Recursive functions call themselves. Recursive data contains itself: a list whose rest is a smaller list, a tree whose branches are smaller trees. When the data is recursive, the functions that process it almost write themselves, because their structure follows the data’s.

Linked lists

A linked list is either empty, or a first element followed by the rest of the list, which is itself a linked list. That sentence is the type definition:

indirect enum List {
    case empty
    case node(Int, List)
}

let numbers = List.node(1, .node(2, .node(3, .empty)))

indirect tells Swift that a case contains a value of the enum’s own type, so it must store that part by reference. Without it, a List would have to contain a whole List inside itself, forever, and the compiler rejects the definition: “recursive enum ‘List’ is not marked ‘indirect’”.

Functions that follow the data

Every function over a list handles the two cases, and the node case recurses on the rest:

indirect enum List {
    case empty
    case node(Int, List)
}

func length(_ list: List) -> Int {
    switch list {
    case .empty: 0
    case .node(_, let rest): 1 + length(rest)
    }
}

func sum(_ list: List) -> Int {
    switch list {
    case .empty: 0
    case .node(let first, let rest): first + sum(rest)
    }
}

let numbers = List.node(1, .node(2, .node(3, .empty)))
print(length(numbers), sum(numbers))   // 3 6

The recursive leap of faith from Lesson 7 applies unchanged: assume the function works on rest, and combine that with first.

indirect enum List {
    case empty
    case node(Int, List)
}
func toArray(_ list: List) -> [Int] {
    switch list {
    case .empty: []
    case .node(let first, let rest): [first] + toArray(rest)
    }
}
func map(_ list: List, _ f: (Int) -> Int) -> List {
    switch list {
    case .empty: .empty
    case .node(let first, let rest): .node(f(first), map(rest, f))
    }
}
let numbers = List.node(1, .node(2, .node(3, .empty)))
print(toArray(map(numbers) { $0 * 10 }))

Linked lists make adding to the front cheap: .node(0, numbers) is a new list that shares all of numbers without copying it. Arrays are better for most everyday work; linked lists are here because they are the simplest recursive data, and the pattern carries over to trees.

Trees

A tree has a label and a list of branches, each of which is a tree. A tree with no branches is a leaf. In Swift a structure can hold an array of its own type directly:

struct Tree {
    var label: Int
    var branches: [Tree] = []

    var isLeaf: Bool { branches.isEmpty }
}

//        1
//       / \
//      2   3
//      |
//      4
let t = Tree(label: 1, branches: [
    Tree(label: 2, branches: [Tree(label: 4)]),
    Tree(label: 3),
])

branches: [Tree] = [] gives the property a default, so a leaf can be made with just Tree(label: 4).

Tree recursion over trees

A function over a tree handles the leaf, and otherwise combines the results of calling itself on every branch. map and reduce from Lesson 4 do the combining:

struct Tree {
    var label: Int
    var branches: [Tree] = []
    var isLeaf: Bool { branches.isEmpty }
}

func countLeaves(_ t: Tree) -> Int {
    t.isLeaf ? 1 : t.branches.map(countLeaves).reduce(0, +)
}

func height(_ t: Tree) -> Int {
    t.isLeaf ? 0 : 1 + t.branches.map(height).max()!
}

func sumLabels(_ t: Tree) -> Int {
    t.label + t.branches.map(sumLabels).reduce(0, +)
}

let t = Tree(label: 1, branches: [Tree(label: 2, branches: [Tree(label: 4)]), Tree(label: 3)])
print(countLeaves(t), height(t), sumLabels(t))   // 2 2 10

Passing countLeaves to map inside countLeaves looks strange at first. It is the same leap of faith: to count the leaves of this tree, count the leaves of each branch and add.

struct Tree {
    var label: Int
    var branches: [Tree] = []
}
func printTree(_ t: Tree, _ depth: Int = 0) {
    print(String(repeating: "-", count: depth) + String(t.label))
    for branch in t.branches {
        printTree(branch, depth + 1)
    }
}
printTree(Tree(label: 1, branches: [Tree(label: 2, branches: [Tree(label: 4)]), Tree(label: 3)]))

Building trees

Tree-recursive computations produce trees naturally. The tree of calls from Lesson 8’s fib can be built as data, with each label equal to that Fibonacci number:

struct Tree {
    var label: Int
    var branches: [Tree] = []
}

func fibTree(_ n: Int) -> Tree {
    if n <= 1 {
        return Tree(label: n)
    }
    let left = fibTree(n - 2)
    let right = fibTree(n - 1)
    return Tree(label: left.label + right.label, branches: [left, right])
}

print(fibTree(5).label)   // 5

struct Tree {
    var label: Int
    var branches: [Tree] = []
}
func leaves(_ t: Tree) -> [Int] {
    if t.branches.isEmpty {
        return [t.label]
    }
    return t.branches.flatMap(leaves)
}
print(leaves(Tree(label: 1, branches: [Tree(label: 2, branches: [Tree(label: 4)]), Tree(label: 3)])))

flatMap is map followed by joining the resulting arrays into one.

Lab 12: Recursive data

Q1: Build a list

Write fromArray(_:), which builds a List from an array, and toArray(_:), which does the reverse. toArray(fromArray(a)) should be a.

indirect enum List {
    case empty
    case node(Int, List)
}

func fromArray(_ values: [Int]) -> List {
    guard let first = values.first else {
        return .empty
    }
    return .node(first, fromArray(Array(values.dropFirst())))
}

func toArray(_ list: List) -> [Int] {
    switch list {
    case .empty: []
    case .node(let first, let rest): [first] + toArray(rest)
    }
}

assert(toArray(fromArray([4, 5, 6])) == [4, 5, 6])
assert(toArray(fromArray([])) == [])

Q2: Maximum path sum

Write maxPathSum(_:), the largest sum of labels along any path from the root down to a leaf.

func maxPathSum(_ t: Tree) -> Int {
    // your code here
}

struct Tree {
    var label: Int
    var branches: [Tree] = []
}

func maxPathSum(_ t: Tree) -> Int {
    t.label + (t.branches.map(maxPathSum).max() ?? 0)
}

let t = Tree(label: 1, branches: [Tree(label: 2, branches: [Tree(label: 4)]), Tree(label: 3)])
assert(maxPathSum(t) == 7)              // 1 + 2 + 4
assert(maxPathSum(Tree(label: 5)) == 5)

Q3: Has a path

Write hasPath(_:_:), which returns true if the array of labels appears as a path starting at the root and going down through branches.

func hasPath(_ t: Tree, _ labels: [Int]) -> Bool {
    // your code here
}

struct Tree {
    var label: Int
    var branches: [Tree] = []
}

func hasPath(_ t: Tree, _ labels: [Int]) -> Bool {
    guard let first = labels.first, first == t.label else {
        return false
    }
    if labels.count == 1 {
        return true
    }
    let rest = Array(labels.dropFirst())
    return t.branches.contains { hasPath($0, rest) }
}

let t = Tree(label: 1, branches: [Tree(label: 2, branches: [Tree(label: 4)]), Tree(label: 3)])
assert(hasPath(t, [1, 2, 4]))
assert(hasPath(t, [1, 3]))
assert(!hasPath(t, [1, 4]))
assert(!hasPath(t, [2]))
assert(!hasPath(t, []))

Q4: Replace a leaf

Write replaceLeaf(_:_:_:), which returns a new tree with every leaf labeled old relabeled new. Labels that are not leaves stay the same.

struct Tree {
    var label: Int
    var branches: [Tree] = []
    var isLeaf: Bool { branches.isEmpty }
}

func leaves(_ t: Tree) -> [Int] {
    t.isLeaf ? [t.label] : t.branches.flatMap(leaves)
}

func replaceLeaf(_ t: Tree, _ old: Int, _ new: Int) -> Tree {
    if t.isLeaf {
        return Tree(label: t.label == old ? new : t.label)
    }
    return Tree(label: t.label, branches: t.branches.map { replaceLeaf($0, old, new) })
}

let t = Tree(label: 4, branches: [Tree(label: 2, branches: [Tree(label: 4)]), Tree(label: 3)])
let replaced = replaceLeaf(t, 4, 40)
assert(leaves(replaced) == [40, 3])
assert(replaced.label == 4)       // the root is not a leaf
assert(leaves(t) == [4, 3])       // the original is unchanged

What’s next

Next lesson: mutation, and the difference between changing a value and changing a shared object.