Higher-order functions

Here are three functions that look almost the same:

func sumNaturals(_ n: Int) -> Int {
    var total = 0
    for k in 1...n { total += k }
    return total
}
func sumCubes(_ n: Int) -> Int {
    var total = 0
    for k in 1...n { total += k * k * k }
    return total
}
func sumSquares(_ n: Int) -> Int {
    var total = 0
    for k in 1...n { total += k * k }
    return total
}
print(sumNaturals(5), sumCubes(5), sumSquares(5))   // 15 225 55

They differ only in what is added for each k. CS61A’s answer is to make that difference a parameter. The parameter is not a number but a function. A function that takes or returns a function is a higher-order function.

Function types

Every function has a type written from its parameters and result. square below has type (Int) -> Int: it takes one Int and returns an Int. Functions are values, so they can be bound to names like any other value:

func square(_ x: Int) -> Int { x * x }

let f: (Int) -> Int = square
print(f(7))   // 49

Note there are no parentheses after square on the second line. square is the function itself; square(7) would call it.

Functions as arguments

Now the three sums collapse into one:

func summation(_ n: Int, _ term: (Int) -> Int) -> Int {
    var total = 0
    for k in 1...n {
        total += term(k)
    }
    return total
}

func cube(_ x: Int) -> Int { x * x * x }

print(summation(5, cube))   // 225

summation knows how to add things up; cube knows what to add. Neither has to know about the other’s job.

Closure expressions

Naming a tiny function just to pass it once is clumsy. A closure expression writes a function inline. The full form spells out the types, then in, then the body:

func summation(_ n: Int, _ term: (Int) -> Int) -> Int {
    var total = 0
    for k in 1...n { total += term(k) }
    return total
}

print(summation(5, { (k: Int) -> Int in return k * k }))
print(summation(5, { k in k * k }))      // types inferred
print(summation(5, { $0 * $0 }))         // shorthand argument names
print(summation(5) { $0 * $0 })          // trailing closure

All four lines print 55. Swift can infer the closure’s types from summation’s parameter, a single-expression body returns its value, and $0 names the first argument. When the closure is the last argument, it can be written after the parentheses as a trailing closure.

let twice = { (x: Int) in x * 2 }
print(twice(twice(3)))

Functions as return values

A function can build and return a new function:

func makeAdder(_ n: Int) -> (Int) -> Int {
    return { x in x + n }
}

let addThree = makeAdder(3)
print(addThree(4))        // 7
print(makeAdder(10)(1))   // 11

The return type (Int) -> Int says makeAdder gives back a function. The closure it returns uses n, a parameter of makeAdder, even after makeAdder has returned. How that works is next lesson’s topic.

func makeAdder(_ n: Int) -> (Int) -> Int {
    return { x in x + n }
}
let addTwo = makeAdder(2)
print(addTwo(addTwo(1)), makeAdder(5)(0))

A closure that is stored or returned, and so may run after the function receiving it has returned, must be marked @escaping. Swift requires the mark so that you notice when a function holds onto one.

func compose(_ f: @escaping (Int) -> Int, _ g: @escaping (Int) -> Int) -> (Int) -> Int {
    return { x in
        f(g(x))
    }
}
let incrementThenDouble = compose({ $0 * 2 }, { $0 + 1 })
print(incrementThenDouble(5))

map, filter, and reduce

Swift’s collections come with higher-order functions built in. map applies a function to every element, filter keeps the elements for which a function returns true, and reduce combines everything into one value:

let numbers = [1, 2, 3, 4, 5]
print(numbers.map { $0 * $0 })          // [1, 4, 9, 16, 25]
print(numbers.filter { $0 % 2 == 1 })   // [1, 3, 5]
print(numbers.reduce(0, +))             // 15

reduce(0, +) starts from 0 and combines with +. Operators are functions, so + can be passed wherever a (Int, Int) -> Int is expected.

print([1, 2, 3, 4].filter { $0 % 2 == 0 }.map { $0 * 10 })
print([1, 2, 3].reduce(1, *))

Lab 3: Higher-order functions

Q1: Product

Write product(n, term), which returns term(1) * term(2) * … * term(n).

func product(_ n: Int, _ term: (Int) -> Int) -> Int {
    // your code here
}

func product(_ n: Int, _ term: (Int) -> Int) -> Int {
    var total = 1
    for k in 1...n {
        total *= term(k)
    }
    return total
}

assert(product(3, { $0 }) == 6)          // 1 * 2 * 3
assert(product(5, { $0 }) == 120)        // 5 factorial
assert(product(3, { $0 * $0 }) == 36)    // 1 * 4 * 9
assert(product(1, { $0 * 7 }) == 7)

Q2: Accumulate

summation and product share a pattern too. Write accumulate(merger, start, n, term), which merges start with term(1), …, term(n) using the two-argument function merger. Then define summation and product in one line each using accumulate.

func accumulate(_ merger: (Int, Int) -> Int, _ start: Int, _ n: Int, _ term: (Int) -> Int) -> Int {
    // your code here
}

func accumulate(_ merger: (Int, Int) -> Int, _ start: Int, _ n: Int, _ term: (Int) -> Int) -> Int {
    var total = start
    for k in 1...n {
        total = merger(total, term(k))
    }
    return total
}

func summation(_ n: Int, _ term: (Int) -> Int) -> Int { accumulate(+, 0, n, term) }
func product(_ n: Int, _ term: (Int) -> Int) -> Int { accumulate(*, 1, n, term) }

assert(accumulate(+, 0, 5, { $0 }) == 15)
assert(accumulate(+, 11, 5, { $0 }) == 26)
assert(accumulate(*, 2, 3, { $0 * $0 }) == 72)   // 2 * 1 * 4 * 9
assert(summation(5, { $0 * $0 * $0 }) == 225)
assert(product(5, { $0 }) == 120)

Q3: Make a repeater

Write makeRepeater(f, n), which returns a function that applies f to its argument n times. When n is 0, the returned function should return its argument unchanged.

func makeRepeater(_ f: @escaping (Int) -> Int, _ n: Int) -> (Int) -> Int {
    // your code here
}

func makeRepeater(_ f: @escaping (Int) -> Int, _ n: Int) -> (Int) -> Int {
    return { x in
        var result = x
        for _ in 0..<n {
            result = f(result)
        }
        return result
    }
}

assert(makeRepeater({ $0 + 1 }, 3)(5) == 8)
assert(makeRepeater({ $0 * 3 }, 5)(1) == 243)
assert(makeRepeater({ $0 * $0 }, 2)(5) == 625)
assert(makeRepeater({ $0 * 3 }, 0)(5) == 5)

What’s next

Next lesson: how a returned closure still sees the names around it, using environments, frames, and captured values.