Three sums with one loop
Here are three functions that each add up a sequence of numbers: the squares , the multiples of three , and the odd numbers .
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:
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:
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 , 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.
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.
Counting with a test function
summation adds something up for every k. Another loop you'll write again and again counts how many of the numbers have some property: how many are even, how many end in 7, how many have an odd number of digits. Once more the loop stays the same and only the check changes, so the check becomes a parameter.
The check is a function that takes a number and returns True or False. A function like that is called a test, or a predicate:
def count(n, test):
total = 0
for k in range(1, n + 1):
if test(k):
total = total + 1
return total
def is_even(x):
return x % 2 == 0
def ends_in_7(x):
return x % 10 == 7
print(count(100, is_even))
print(count(100, ends_in_7))count calls test(k) once for each k from 1 to n and adds 1 whenever the answer is true. Of the numbers 1 to 100, half are even, and ten end in 7: 7, 17, 27 and so on up to 97.
Uneven Numbers is practice for count. Your test is "has an odd number of digits". To count the digits of x, divide it by 10 until it reaches 0 and count the divisions, the way digit_sum took a number apart.
Given an integer , print how many of the positive integers up to have an odd number of digits, written in base ten without leading zeros.
Constraints
Sample 1 · Input
11
Output
9
Sample 2 · Input
136
Output
46
Sample 3 · Input
100000
Output
90909
Computing a square root by improving a guess
math.sqrt(2) is 1.4142135623730951. has no exact decimal form, so there is nothing to look up: the library has to compute it. One way to compute a square root needs only arithmetic, and it shows a second use of higher-order functions: holding a whole method of solving a problem.
Start with any guess for , say 1. The two numbers and always multiply to 2, so if is too small then is too big, and the other way round. The real root lies between them, which makes their average a better guess:
From 1, the average of 1 and 2 is 1.5. From 1.5, , and the average is . In the table below, the first wrong digit moves from the third decimal place to the sixth, then to the twelfth, so the number of correct digits roughly doubles with each step.
| Step | Guess | |
|---|---|---|
| 0 | 1 | 1 |
| 1 | 1.5 | 2.25 |
| 2 | 1.4166666666666665 | 2.006944444444444 |
| 3 | 1.4142156862745097 | 2.0000060073048824 |
| 4 | 1.4142135623746899 | 2.0000000000045106 |
This method is called iterative improvement: start from a guess and keep improving it until it is close enough. Only two things in it belong to : how to improve a guess, and how to tell that a guess is close enough. Both can be functions, so the method itself can be a higher-order function that takes them as arguments.
The improve function
def improve(update, close, guess, max_updates=100):
updates = 0
while not close(guess) and updates < max_updates:
guess = update(guess)
updates = updates + 1
return guess
def sqrt2_update(g):
return (g + 2 / g) / 2
def sqrt2_close(g):
return abs(g * g - 2) < 1e-9
print(improve(sqrt2_update, sqrt2_close, 1))Python details
1e-9 is how Python writes , which is 0.000000001.
improve knows nothing about square roots. It replaces the guess with update(guess) until close(guess) says yes, and here that took the 4 updates in the table. sqrt2_close accepts a guess once is within of 2. The last parameter, max_updates, is a default argument: it stops the loop after 100 updates in case close never says yes.
Defining a function inside a function
sqrt2_update and sqrt2_close have the number 2 written into them, so they only find . To find the square root of any number a, the update needs a. But improve calls update(guess) with one argument and has no a to give it, so adding a second parameter to the update would not help.
The way out is to define the update inside a function that already knows a. A def can go inside another function's body like any other statement:
def improve(update, close, guess, max_updates=100):
updates = 0
while not close(guess) and updates < max_updates:
guess = update(guess)
updates = updates + 1
return guess
def square_root(a):
def update(g):
return (g + a / g) / 2
def close(g):
return abs(g * g - a) < 1e-9
return improve(update, close, 1)
print(square_root(2))
print(square_root(9))
print(square_root(1000000))Python details
The stopping test measures how far g * g is from a, so this function is for numbers of ordinary size, 1 or more. For 0 or a tiny fraction the test passes while the guess is still far from the root: square_root(0) returns about 0.00003 instead of 0.
Each call to square_root makes its own update and close, which use the a of that call, and hands them to improve. square_root(9) reaches 3 after 6 updates, and square_root(1000000) reaches 1000 after 15.
Name lookup in a nested function
When update runs, it uses a, which is neither its parameter nor a global name. In Defining new functions, Python looked a name up in the call's own frame and then in the global frame. A nested function needs one more place in between.
Every function remembers the frame it was defined in, called its parent. A def at the top of a file makes a function whose parent is Global, which is why the diagrams so far have labelled every function [parent=Global]. But def update runs while the frame of square_root(9) is open, so that frame is the parent of update. A call to update looks for a in its own frame, which holds only g, and then in the parent, where a is 9.
The parent is the frame where the function was defined, not the one it was called from. improve is the function that calls update, and its frame holds guess and updates, but update never looks there. This rule is called lexical scope: you can tell where a name comes from by reading where the function sits in the program text, without running anything.
Definition
Lexical scope
A function looks a name up in its own frame, then in its parent (the frame it was defined in), then in that frame's parent, and so on up to the global frame, and finally among the built-in names such as abs.
Returning a function
Back to counting. To count the multiples of 3 up to some n, you would write a test is_multiple_of_3. For multiples of 7 you would write another, then another for 11, each a copy with a different number in it. A function can make these tests for you, if it returns the test it defines instead of calling it:
def count(n, test):
total = 0
for k in range(1, n + 1):
if test(k):
total = total + 1
return total
def multiple_of(d):
def divisible(x):
return x % d == 0
return divisible
of_three = multiple_of(3)
print(of_three(12), of_three(10))
print(count(20, of_three))
print(count(20, multiple_of(7)))multiple_of(3) defines divisible with d bound to 3 and returns it without calling it, so of_three is a test like is_even: of_three(12) is True and of_three(10) is False. Passed to count, it accepts 3, 6, 9, 12, 15 and 18, six numbers up to 20. The last line never names its test: multiple_of(7) makes one and hands it straight to count, which finds 7 and 14.
Notice what happens to the frame of multiple_of(3). The call has returned, yet every time of_three runs it still finds d = 3 in that frame. Python keeps a frame for as long as some function's parent points at it. A function together with the frame it was defined in is called a closure.
Step through multiple_of
Step through the call and watch where d lives after multiple_of returns. The second preset makes two tests.
In the two-test preset, the global frame ends with two names bound to two different functions, both called divisible. The first has parent f1, where d is 3, and the second has parent f2, where d is 5: each call to multiple_of made a frame of its own, so each test reads its own d.
Deeper read: taking arguments one at a time
multiple_of(3)(9) gives the same answer as 9 % 3 == 0, but it takes its two numbers one call at a time: the first call fixes d and returns a function, and the second call gives that function x. Rewriting a function of two arguments as a chain of one-argument functions like this is called currying, after the logician Haskell Curry. It is how a two-argument rule, such as "is x divisible by d", becomes the one-argument test that count expects.
Deeper read: functions that wrap functions
A function that takes a function can also return a new one that does a little more. nonnegative(f) returns a function that checks its argument with assert before calling f. Python has a shorthand for applying such a function: a line starting with @ above a def. The function after the @ is called a decorator:
def nonnegative(f):
def checked(x):
assert x >= 0, 'expected a number >= 0'
return f(x)
return checked
@nonnegative
def digits(x):
total = 0
while x > 0:
x = x // 10
total = total + 1
return total
print(digits(2026))@nonnegative above def digits means digits = nonnegative(digits) right after the def. The name digits ends up bound to checked, so digits(2026) prints 4, and digits(-5) stops with AssertionError: expected a number >= 0 instead of returning 0. Libraries use decorators like this to time, cache or log calls.
Lambda expressions
Some functions in this lesson exist only to be passed once, such as square for summation or is_even for count. Writing a def and inventing a name for each one gets tedious. A lambda expression writes such a function right where it is used:
def summation(n, term):
total = 0
for k in range(1, n + 1):
total = total + term(k)
return total
def count(n, test):
total = 0
for k in range(1, n + 1):
if test(k):
total = total + 1
return total
print(summation(4, lambda k: k * k))
print(count(100, lambda x: x % 2 == 0))lambda k: k * k is an expression whose value is a function: given k, it returns k * k. Its body is a single expression with no return, and the function has no name. The word comes from the lambda calculus, a notation for functions that the logician Alonzo Church introduced in the 1930s.
A function longer than one expression reads better as a def, with a name that says what it does. The name also shows up in error messages, where every lambda appears as <lambda>. A lambda suits a short function that is passed once.
A named function and a lambda
Here is apply_twice again, once with square and once with a lambda that computes the same thing. Compare the two diagrams.
Both presets print 81. The only difference is in the global frame: square has a name there, and the lambda does not. The only arrow to the lambda comes from f in f1, and once apply_twice returns, no name refers to it at all.
The problem below is practice for a lambda test. The test, "odd, with exactly eight divisors", fits in one expression once you have written a function that counts the divisors of x. is at most 200, so trying every possible divisor of every number takes at most remainder checks.
The number 105 is odd and has exactly eight positive divisors. Print how many odd numbers between 1 and , inclusive, have exactly eight positive divisors.
Constraints
- is an integer with
Sample 1 · Input
105
Output
1
Sample 2 · Input
7
Output
0
Common mistakes
Calling the function instead of passing it:
count(100, is_even(100)).- Where it breaks
is_even(100)runs first, socountreceivesTrueas its test instead of a function. Python stops withTypeError: 'bool' object is not callable; in C++ the program does not compile.- The fix
- Pass the name with no parentheses:
count(100, is_even).
Stopping an improvement loop when a float equals the answer:
return g * g == 2as theclosetest.- Where it breaks
- The guesses for settle at 1.414213562373095, whose square is 1.9999999999999996, so the test is never true.
improveruns all 100 updates, and a loop without a limit would never end. - The fix
- Compare the distance with a tolerance:
abs(g * g - 2) < 1e-9.
Defining a helper outside the function whose local name it needs, such as
updateat the top of the file usinga.- Where it breaks
- In Python, the first call to
updatestops withNameError: name 'a' is not defined, because its parent is Global. In C++, a lambda written[](double g) { return (g + a / g) / 2; }does not compile. - The fix
- Define the helper inside
square_root; in C++, capture the name with[a].
Returning a lambda that captures a local by reference (C++):
return [&d](int x) { return x % d == 0; };inmultiple_of.- Where it breaks
dstops existing whenmultiple_ofreturns, so the test reads memory that may now hold anything. On the Mac we checked this on, the test said 10 was a multiple of 3 and accepted all 30 numbers from 1 to 30.- The fix
- Capture by copy,
[d], whenever the lambda outlives the function that made it.
Writing a statement in a lambda (Python):
lambda x: return x + 1.- Where it breaks
- Python stops with
SyntaxError: invalid syntaxbefore running anything, becausereturnstarts a statement and a lambda body must be a single expression. - The fix
- Write
lambda x: x + 1, or use adef.
Recall What does `count(30, multiple_of(4))` return?
7. multiple_of(4) returns a test that accepts 4, 8, 12, 16, 20, 24 and 28, and count checks every number from 1 to 30 with it.
Recall Why does `square_root` define `update` inside itself instead of at the top of the file?
update needs a, and improve passes it only the guess. Defined inside square_root, its parent is the frame of that call, where a is bound. At the top of the file its parent would be Global, and looking up a would raise a NameError.
Key terms
| Term | Meaning |
|---|---|
| term | The value summation adds for each k, computed by the function it is passed. |
| function pointer | In C++, an older way to write a parameter that holds a plain function: int (*f)(int). |
| higher-order function | A function that takes a function as an argument or returns one. |
| test (predicate) | A function that takes a value and returns true or false. |
| iterative improvement | Starting from a guess and improving it until it is close enough. |
| lambda | A function written as an expression, with no name. |
| parent | In Python, the frame a function was defined in. |
| capture | In C++, a local name a lambda takes in when it is made: a copy with [n], the original with [&n]. |
| lexical scope | The rule that a function finds names where it was defined, not where it is called. |
| closure | A function together with the names it uses from where it was made: its parent frame (Python) or its captures (C++). |
