Higher-order functions 0/1

Lesson 10 of 21

Higher-order functions

Pass functions to functions, return them, and build general methods out of small ones.

Part 1 of 8 Functions as arguments

Three sums with one loop

Here are three functions that each add up a sequence of numbers: the squares 12+22+⋯+n21^2 + 2^2 + \cdots + n^2, the multiples of three 3+6+⋯+3n3 + 6 + \cdots + 3n, and the odd numbers 1+3+⋯+(2n−1)1 + 3 + \cdots + (2n - 1).

Sign up to run
def sum_squares(n):
    total = 0
    for k in range(1, n + 1):
        total = total + k * k
    return total

def sum_triples(n):
    total = 0
    for k in range(1, n + 1):
        total = total + 3 * k
    return total

def sum_odds(n):
    total = 0
    for k in range(1, n + 1):
        total = total + (2 * k - 1)
    return total

print(sum_squares(4), sum_triples(4), sum_odds(4))

Apart from their names, the three functions are the same loop. The only difference is the expression added on each pass, k * k, 3 * k or 2 * k - 1, which we'll call the term. You met this situation in Defining new functions: when copies of some code differed only in a number, you made the number a parameter. Here what differs is a rule for working out a number from k, so to make it a parameter, you need to be able to hand a function to another function.

Binding a name to a function

You can, because a function is a value. In the environment diagrams of Defining new functions, def square drew an arrow from the name square to a function object, just as pay = 135 binds pay to a number. So another name can be bound to the same function, and calling that name runs square:

Sign up to run
def square(x):
    return x * x

f = square
print(f(5))

f = square has no parentheses after square, so it does not call square; it gives the function a second name. f(5) then runs the body of square and prints 25. A parameter is a name too, so it can be bound to a function in exactly the same way.

The summation function

Now the shared loop can become one function. summation(n, term) adds up term(1), term(2) and so on up to term(n), and each caller passes in the term it wants:

Sign up to run
def summation(n, term):
    total = 0
    for k in range(1, n + 1):
        total = total + term(k)
    return total

def square(k):
    return k * k

def triple(k):
    return 3 * k

def odd(k):
    return 2 * k - 1

print(summation(4, square), summation(4, triple), summation(4, odd))

In summation(4, square), the parameter term is bound to square, so term(k) squares k. The terms are 1, 4, 9 and 16, which add up to 30. The other two calls pass triple and odd and get 30 and 16, the same answers the three copies gave. A fourth sum, such as 13+23+⋯+n31^3 + 2^3 + \cdots + n^3, now takes a two-line cube function instead of another copy of the loop.

Definition

Higher-order function

A higher-order function is a function that takes a function as an argument or returns a function as its result. summation is one; square, which takes and returns a number, is not. Functions of the second kind come later in this lesson.

Step through apply_twice

apply_twice(f, x) is about the smallest higher-order function there is. It returns f(f(x)): it applies f to x, then applies f again to the result. Step through it and watch what f holds.

Use the left and right arrow keys to step, Home for the first step and End for the last.

  1. def square(x):(line that just ran)
  2. return x * x
  3. def apply_twice(f, x):(line that runs next)
  4. return f(f(x))
  5. print(apply_twice(square, 3))

Frames

Global current
square
function func square(x)

Objects

func square(x)[parent=Global]

def creates a function and binds the name square to it.

Output

Step 1 of 9

At the step where frame f1 opens, the global name square and the parameter f point at the same function object; passing square did not copy it. Each call f(...) then opens a frame of square with its own x, first 3 and then 9. The opposite preset passes a function that returns -x, and applying it twice gives back the 5 you started with.