Higher-Order Functions

Why treat functions like data?

If you can pass around behavior, you can stop rewriting the same program over and over.

• Stake: less repetition, more reuse
• Destination: higher-order functions (args $+$ returns)
• Roadmap: pattern → abstraction → closures → composition → Newton's method

The repetition problem: three sums, one shape

def sum_naturals(n):
    total, k = 0, 1
    while k <= n:
        total += k
        k += 1
    return total

def sum_cubes(n):
    total, k = 0, 1
    while k <= n:
        total += k ** 3
        k += 1
    return total

def pi_sum(n):
    total, k = 0.0, 1
    while k <= n:
        a = 4 * k - 3
        total += 1.0 / (a * (a + 2))
        k += 1
    return 8 * total

• Same skeleton: accumulate + step $k$
• Different: term at $k$

Functions as arguments: the summation abstraction

def summation(n, term):
    """Return term(1) + term(2) + ... + term(n)."""
    total, k = 0, 1
    while k <= n:
        total += term(k)
        k += 1
    return total

def sum_naturals(n):
    return summation(n, lambda k: k)

def sum_cubes(n):
    return summation(n, lambda k: k ** 3)

def sum_squares(n):
    return summation(n, lambda k: k ** 2)

• Pass behavior: term
• Sigma idea: vary $f(k)$, keep the loop

The power of $\lambda$: tiny functions, right where you need them

def square_def(x):
    return x * x
square_lambda = lambda x: x * x

def apply_twice(f, x):
    return f(f(x))

if __name__ == "__main__":
    print(square_def(5), square_lambda(5))
    print(apply_twice(lambda t: t + 3, 10))

• $\lambda$ = function value, not a special cheat
• Use when: short $+$ local, not reusable name

Functions as return values: factories and closures

def make_adder(n):
    def adder(x):
        return x + n
    return adder

if __name__ == "__main__":
    add_three = make_adder(3)
    print(add_three(4))
    print(make_adder(10)(-2))

• Return value: a function
• Closure: returned function remembers $n$

Composition: building pipelines of behavior

def compose(f, g):
    def h(x):
        return f(g(x))
    return h

def make_adder(n):
    return lambda x: x + n

def square(x):
    return x * x

if __name__ == "__main__":
    f = compose(square, make_adder(1))
    print(f(5))

• New function: $h(x) = f(g(x))$
• Predict: compose(square, make_adder(1))(5)

A real application: Newton-style iterative improvement

def improve(update, close, guess, max_steps=100):
    steps = 0
    while steps < max_steps and not close(guess):
        guess = update(guess)
        steps += 1
    return guess

def newton_update(g, dg):
    """Newton's method: x - g(x)/g'(x)"""
    return lambda x: x - g(x) / dg(x)

if __name__ == "__main__":
    # sqrt(2): solve g(y) = y**2 - 2 = 0
    g = lambda y: y**2 - 2
    dg = lambda y: 2 * y
    close = lambda y: abs(g(y)) < 1e-10

update = newton_update(g, dg)

• Strategy as inputs: update, close
• Prediction: from 1.0, is the next guess above or below 1.4?

Currying: turning a two-input function into a function factory

def curry2(f):
    """Transform f(x, y) into a function that can be called as f(x)(y)."""
    return lambda x: (lambda y: f(x, y))

if __name__ == "__main__":
    curried_pow = curry2(pow)
    print(curried_pow(2)(10))

    # partial application via currying
    pow2 = curried_pow(2)
    print(pow2(5), pow2(6))

• From $f(x, y)$ to $f(x)(y)$
• Partial application: fix $x$, vary $y$

Exit ticket: predict, then explain why

• Practice: predict summation(5, lambda k: 2*k)
• Reflection: when return a function vs return a number?