Functional abstraction

A function is an abstraction when you can use it without knowing how it works. max(3, 9) is 9; you have never needed to see its body. This lesson is about writing functions that others can use the same way: general enough to reuse, with a clear promise about what they do.

Generalizing

Lesson 4 turned three sums into one summation by making the varying part a parameter. The same function handles much less obvious terms. This sum converges, very slowly, to π:

8/(1·3) + 8/(5·7) + 8/(9·11) + ⋯

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

func piSum(_ n: Int) -> Double {
    summation(n) { k in 8.0 / Double((4 * k - 3) * (4 * k - 1)) }
}

print(piSum(1000))   // 3.141092653621038

summation now adds Doubles, and piSum only has to say what the kth term is.

Iterative improvement

Many numerical methods follow one pattern: start with a guess, and keep improving it until it is close enough. The pattern itself can be a function that takes the two varying parts, how to improve and how to judge, as arguments:

func improve(_ update: (Double) -> Double, _ close: (Double) -> Bool, _ guess: Double = 1) -> Double {
    var guess = guess
    while !close(guess) {
        guess = update(guess)
    }
    return guess
}

// The golden ratio is the positive number x with x * x == x + 1.
let golden = improve({ x in 1 / x + 1 }, { x in abs(x * x - (x + 1)) < 1e-10 })
print(golden)   // 1.6180339887802426

guess: Double = 1 gives the parameter a default value, so callers can leave it out.

Newton’s method is an improvement rule for square roots: a better guess for √a is the average of x and a / x.

func improve(_ update: (Double) -> Double, _ close: (Double) -> Bool, _ guess: Double = 1) -> Double {
    var guess = guess
    while !close(guess) { guess = update(guess) }
    return guess
}

func squareRoot(_ a: Double) -> Double {
    improve({ x in (x + a / x) / 2 }, { x in abs(x * x - a) < 1e-10 })
}

print(squareRoot(2))     // 1.4142135623746899
print(squareRoot(256))   // 16.00000000000039

The second result is not exactly 16: close accepts any guess whose square is within 10⁻¹⁰ of 256. Floating-point answers are compared with a tolerance, never with ==.

func improve(_ update: (Double) -> Double, _ close: (Double) -> Bool) -> Double {
    var guess = 1.0
    while !close(guess) {
        guess = update(guess)
    }
    return guess
}
let golden = improve({ 1 / $0 + 1 }, { abs($0 * $0 - ($0 + 1)) < 1e-10 })
print(golden > 1.618 && golden < 1.619)

A function’s contract

To use a function without reading its body, you need to know three things: what it takes, what it returns, and anything it assumes. Swift writes the first two in the signature. The rest belongs in a documentation comment, written with /// directly above the function:

/// Returns the number of ways to choose `k` items from `n`.
///
/// - Precondition: `0 <= k` and `k <= n`.
func choose(_ n: Int, _ k: Int) -> Int {
    precondition(0 <= k && k <= n, "k must be between 0 and n")
    var result = 1
    for i in 0..<k {
        result = result * (n - i) / (i + 1)
    }
    return result
}

print(choose(5, 2))   // 10

Xcode and other editors show these comments when you use the function. The precondition line turns the assumption into a check: if a caller breaks the contract, the program stops right there, instead of returning a meaningless number.

func half(_ n: Int) -> Int {
    precondition(n % 2 == 0, "n must be even")
    return n / 2
}
print(half(half(10)))

Tests as examples

CS61A writes examples as doctests. In Swift, assert lines play the same role in a lab file: assert(choose(5, 2) == 10) does nothing when the answer is right and stops the program when it is wrong. In Unit 3 we will move to Swift’s testing library.

Functions that wrap functions

A higher-order function can add behavior to any function without changing it. trace prints each argument before calling the function it wraps, which is handy when debugging:

func trace(_ f: @escaping (Int) -> Int) -> (Int) -> Int {
    return { x in
        print("->", x)
        return f(x)
    }
}

let tracedSquare = trace { $0 * $0 }
print(tracedSquare(3))

func trace(_ f: @escaping (Int) -> Int) -> (Int) -> Int {
    return { x in
        print("->", x)
        return f(x)
    }
}
let t = trace { $0 + 1 }
print(t(t(1)))

Searching

search finds the smallest non-negative integer for which a condition holds:

func search(_ condition: (Int) -> Bool) -> Int {
    var x = 0
    while !condition(x) {
        x += 1
    }
    return x
}

print(search { $0 * $0 > 30 })   // 6

func search(_ condition: (Int) -> Bool) -> Int {
    var x = 0
    while !condition(x) {
        x += 1
    }
    return x
}
print(search { $0 % 7 == 3 && $0 > 10 })

Lab 5: Abstraction

Q1: Inverse

Using search, write inverse(f): given a function f that is increasing on the non-negative integers, return a function g such that g(f(x)) == x.

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

func search(_ condition: (Int) -> Bool) -> Int {
    var x = 0
    while !condition(x) { x += 1 }
    return x
}

func inverse(_ f: @escaping (Int) -> Int) -> (Int) -> Int {
    return { y in search { x in f(x) == y } }
}

let squareRoot = inverse { $0 * $0 }
assert(squareRoot(16) == 4)
assert(squareRoot(144) == 12)
let halve = inverse { $0 * 2 }
assert(halve(10) == 5)

Q2: Count the calls

Write countCalls(f), which returns two functions in a tuple: call, which behaves exactly like f, and count, which returns how many times call has been called.

func countCalls(_ f: @escaping (Int) -> Int) -> (call: (Int) -> Int, count: () -> Int) {
    // your code here
}

func countCalls(_ f: @escaping (Int) -> Int) -> (call: (Int) -> Int, count: () -> Int) {
    var calls = 0
    let call = { (x: Int) -> Int in
        calls += 1
        return f(x)
    }
    return (call, { calls })
}

let counted = countCalls { $0 * 10 }
assert(counted.count() == 0)
assert(counted.call(2) == 20)
assert(counted.call(3) == 30)
assert(counted.count() == 2)

Q3: Cube roots

Using improve from this lesson, write cubeRoot(_:) with Newton’s update for cube roots: a better guess for ∛a is (2x + a / x²) / 3. Stop when |x³ − a| < 10⁻¹⁰.

func improve(_ update: (Double) -> Double, _ close: (Double) -> Bool, _ guess: Double = 1) -> Double {
    var guess = guess
    while !close(guess) { guess = update(guess) }
    return guess
}

func cubeRoot(_ a: Double) -> Double {
    improve({ x in (2 * x + a / (x * x)) / 3 }, { x in abs(x * x * x - a) < 1e-10 })
}

assert(abs(cubeRoot(27) - 3) < 1e-9)
assert(abs(cubeRoot(2) * cubeRoot(2) * cubeRoot(2) - 2) < 1e-9)

What’s next

Next lesson: recursion, where a function’s body calls the function itself.