A higher order function either takes a function as an input or returns a function as an output (or both). If a recipe is a function, a higher-order function is a recipe builder.
Pythonistas will tell you that in Python functions are objects. (Indeed they're tell you that in Python, everything is an object.) What does this mean? It means that functions can do what objects do.
Well, what do objects do? Let's have an example of an object. How about the int 12. What can we do with 12? We can assign it to a variable:
a_var = 12
We can pass it to a function:
a_func(12)
We an return it within a function:
def silly_func():
return 12
(silly_func is indeed very silly. It returns 12. Always. No matter what we send it. But it does prove the point that 12 can be returned.)
So, here's what makes an object an object: we can assign it to a variable, we can send it to a function, a function can return it. So let's now prove that we can do all three with a function.
First we start with a simple function. It takes a number and returns its square.
def square(x):
return x ** 2
Can we assign it to a variable? Indeed we can.
alias_of_square = square
Notice that since square has no parentheses at its end, we did not call it. Instead the value of square, which is a function, was assigned to alias_of_square. Thus alias_of_square is now a second name of the square function. Let's prove it:
>>> square(12)
144
>>> alias_of_square(12)
144
(The clever among you - which is all of you - might have noticed that square was already a variable that named a function. True, true. But I wanted to drive the point home.)
So, functions can be assigned to variables. Can they be passed to a function? Yep! Let me create a cousin of silly_func. I call it redundant_func.
def redundant_func(f, x):
# Take a function and an object
# Call the function and pass it the object
# Return the value of that function call
return f(x)
Look carefully at the body. We return the value of f(x). This means that f is a function and x the value we pass to it. But f is one of the function's parameters, and so when we call redundant_func, we must send it a function. redundant_func takes a function!
Still in doubt? Let's prove it!
>>> redundant_func(alias_of_square, 3)
9
Success! We passed alias_of_square to redundant_func where it was given the local name f. Next we called it within redundant and returned the value it returned. (That's why redundant_func is redundant. It simply returns the value another function returns. It passes the return buck as it were.)
So, we know that a function can be assigned to a variable and that a function can be passed to a function. Let's prove last that a function can be returned by a function. I'll do this in a way that will perhaps seem strange to you. I'll build a function inside a function and then have the outer function return the inner function. Here we go:
def func_maker():
def anon(y):
return y ** 3
return anon
Curious, isn't it? Immediately after def we have another def. But that's just what you should have expected! We set out to build a function inside a function.
The inner function is named anon. (More on the choice of name in a moment.) It's a function that takes a number and returns its cube. anon is then returned by func_maker. So a call to func_maker returns a function that takes a number and returns its cube. Let that sink in. func_maker builds and then returns a function.
Why call the inner function - the function built and then returned - anon? Its name appears only inside of func_maker, and so really its name is irrelevant. We can call it whatever we like. Nothing outside the function will ever see the name.
How do we use func_maker? We call it. Of course. What will we do with its value? We call it. Of course. func_maker returns a function!
>>> cube = function_maker()
>>> cube(3)
27
So there you have it. Functions can be assigned to variables. Functions can be passed to functions. Functions can be returned by functions. Thus functions are objects.
If we wish, we can dispense with the name anon in the function above. We do so with a so-called "lambda expression". Here's the rewrite:
def func_maker():
return lambda x: x ** 3
Run it and try this in the console:
>>> cube = function_maker()
>>> cube(3)
27
So apparently cube cubes its inputs. How did the lambda expression do that? Well, let's break it down.
Our expression is lambda x: x ** 3. It begins with the keyword lambda. This means that what comes after is a function. Next is the variable x. This is the function's one parameter. (It could have had many. They would have been separated by commas.) After the colon comes the expression whose value will be returned by the function once its variables have been assigned values. So the entire expression lambda x: x ** 3 can be read as "a function that takes an x and returns the cube of x". Remember this structure. After the lambda and before the colon comes the parameters; after the colon comes the function body.
So lambda expressions have much the same structure as the functions we already know (and love): parameter list and then body. The one feature that a lambda definition lacks is a name. Lambda functions are anonymous functions.
I sympathize if you're troubled by this. (I was the first time I encountered it.) Functions without names? It seems like trickery. How can we use a function that has no name? Don't we need a name to call a function?
The answer is No, we don't need a name. Let me prove it.
>>> (lambda x: x**3)(3)
27
>>> (lambda x: x**3)(33)
35937
Remember that if ever we have an expression followed immediately by parentheses, as the expression lambda x: x**3 is followed immediately by (3) above, Python treats that expression as a function and attempts to send it the value or values contained in parentheses. If that expression is not a function, we crash. But we didn't crash; we got outputs of 27 and 35937 instead. So indeed the expression lambda x: x**3 is a function.
When in the code examples below we have no need to name a function, we typically won't use anon as we did above. Instead we'll make use of lambda expressions. (The exception is when the function is of some complexity. Lambda expressions are good for short functions, not so good for ones not short.)
We need more examples of higher order functions! You'll grow strong in the ways of the function if fed a steady diet of good examples.
Let's write a function that takes a list and a function and returns the sum of the outputs of that function if it's fed the elements of that list. For instance, if it's sent the list [1, 4, 9] and the square root function, it will return the sum of the square roots of 1, 4 and 9, which is 6.
def sum_of_outputs(func, lst):
s = 0 # Initialize the sum to 0
for elem in lst:
s += func(elem) # Call func with argument elem; add output to s.
return s
Let's test it out. Recall that math.sqrt is the name of the math module's square root function.
>>> import math
>>> sum_of_outputs(math.sqrt, [1, 4, 9])
6.0
sum_of-outputs is higher order because it takes a function as input, and because it is higher order in this way, it is versatile. We could for instance send it the square function. We'll create that function ourselves.
def square(n):
return n ** 2
Back to the console:
>>> sum_of_outputs(square, [1, 4, 9])
98
Perhaps then you can begin to understand the use of higher order functions. To sum the square roots of the numbers in a list and then to sum the squares of the numbers of a list doesn't require two functions. Instead we can write a single function - sum_of_outputs above - that does both. This is an example of a point made chapters ago. Remember when I said that if we have two similar functions, we should attempt to capture what's common to them in a single function? Remember when I said to functionalize the similarities and parametermize the differences? Well, here the difference was the function used on the list. So we parameterized that. We created a function that takes a function and a list and then applies that function to all the elements of a list.
Example upon example, we grow strong in the way of the function.
Let us make a function that returns a function. This example is taken from algebra. I'm sure you'll recall it. If we're given the slope and y-intercept of a line, we can write its equation in so-called "slope-intercept form":
y = mx + b
This equation is really just a function. The input is x. The output is y. If we feed it the x-coordinate of a point on the line, it will give us back that point's y-coordinate.
Now, how do we build a function that returns a function? We'll use a lambda expression for the inner function, the function that the outer function will return. Its parameters are the x-coordinate of a point; we'll call this just x. The output is the value of the expression m*x + b. So we have this for the inner function:
lambda x: m * x + b
Here's the whole of it, inner and outer functions both:
def eq_line(m, b):
return lambda x: m * x + b
eq_line thus takes value for m and b and returns a function that takes an x and returns the value of m * x + b.
To test, we need to call eq_line, assign the output function to a variable, and then call that function by use of that variable.
>>> a_line = eq_line(1, 2)
>>> a_line(3)
5
>>> a_line(-5)
-3
>>> b_line = eq_line(-3, 7)
>>> b_line(0)
7
>>> b_line(-5)
22
a_line is the line y = x + 2. b_line is the line y = -3x + 7.
A small note before we move yet higher. I've had students who were troubled about that m and b in the definition of eq_line. They wondered how the function returned by eq_line could "know" what they are. Wouldn't we have to tell our line the values of m and b whenever we use it equation? The answer is that the m and b are as it were embedded in the function that eq_line returns. If we send eq_line a 3 and a 2, say, then it builds the function (expressed mathematically) y = 3x + 2. The 3 and the 2 are in there, carried around by the function wherever it goes. We need give them only once.
Let's now have an example of a function that takes functions and returns functions. Functions as far as the eye can see! The example is composition. Composition takes two functions and produces one.
Let's review the mathematics first. We compose two functions when the output of one is made the input of another. For instance, consider the double and add two functions. In symbols:
f(x) = 2x, g(x) = x + 2
Let's send a number through f, take the result, and send that through g. How about 12.
f(x) = 2 â‹… 12 = 24, g(24) = 24 + 2 = 26
Now, the composite of f and g is a single function, call it h, that does this work all at once as it were. It takes f's input and produces g's output.
h(x) = g(f(x))
Do be careful. In general, the composite of g and f will not equal the composite of f and g. So pay attention to the order of your f and g. It matters! (Don't believe me? Pick two positive integers. Add them and then square the result. Now square each and add the results. The final result is not the same.)
How do we express this idea in Python? What we need is a higher-order function that takes two functions and returns their composite. This is a function that takes two functions and returns a function. So. Very. Higher. Order.
How do we do that? The first line is obvious enough. Define a function that takes two functions:
def compose(f, g):
Now what? Well, we have to return a function. So we have to create a function. We'll use a lambda expression, one that takes the input x and returns the value of f(g(x)).
lambda x: f(g(x))
So all together we have:
def compose(f, g):
return lambda x: f(g(x))
Very simple, but as we will see, very powerful.
Let's put compose to use. Our first example begins with a lovely definition of absolute value: the absolute value of x is the square root of the square of x. (Never realized that? Try a few examples to convince yourself it's right.) Here's the Python for that. (Make sure you've run the compose function of the previous section before you go to the console.)
>>> sqrt = lambda x: x**(1/2)
>>> square = lambda x: x**2
>>> abs = compose(sqrt, square)
Are you surprised that we defined sqrt and square as we did? Did you expect a def? We don't need a def! Why not? Lambda expressions are functions, and they don't use a def.
Are you surprised that abs was defined as it was? Did you expect a def? We don't need a def! Why not? compose returns the composite function we want!
Let's try it out.
>>> abs(1)
1.0
>>> abs(-1)
1.0
>>> abs(0)
0.0
Success!
Wikipedia's definition:
A palindrome is a word, number, phrase, or other sequence of characters which reads the same backward as forward, such as madam or race car or the number 10801. Sentence-length palindromes may be written when allowances are made for adjustments to capital letters, punctuation, and word dividers, such as "A man, a plan, a canal, Panama!", "Was it a car or a cat I saw?" or "No 'x' in Nixon".
Let's write a function that takes a string and returns True if it's a palindrome, False if it's not. We'll make our lives easy and assume that the only non-alphanumeric characters are spaces and that all characters are lowercase.
Here's the plan:
Create a function wstrip that strips all white space from a string.
Create a function reverse that returns a string reversed.
Create a composite function rev_wstrip that strips white space and reverses.
Create a new higher-order function compare that takes two functions and returns a function that compares their outputs for a given input.
Finally, the palindrome checker function is_pali is the function returned by compare if it's given wstrip and rev_wstrip.
(Excuse the length. I began to have fun and couldn't stop. I really wanted that is_pali function defined as I have: is_pali = compare(wstrip, rev_wstrip)! How gorgeous! Poetry! Poetry I say!)
def compose(f, g):
return lambda x: f(g(x))
def compare(f, g):
# Return a Boolean-valued function
# that compares the values of f and g for a given input.
return lambda x: f(x) == g(x)
def wstrip(S):
# Strip all white space from a string S
R = ''
for c in S:
if c != ' ':
R = R + c
return R
def reverse(S):
# Reverse a string S
R = ''
for c in S:
R = c + R # Note that we added on the left
return R
rev_wstrip = compose(reverse, wstrip)
is_pali = compare(wstrip, rev_wstrip)
Test it out:
>>> is_pali('10801')
True
>>> is_pali('10811')
False
>>> is_pali('madam im adam')
True
>>> is_pali('madam im zach')
False