[Tutor] Higher-Order Function Examples

[Steven D'Aprano]

Carla Jenkins wrote:

> Hello everyone: I am new to Python and am looking for higher-order
> function programming examples.  The programming codes do not feature
> the corresponding equation so I am lost. Please help me.

The first thing you need to understand is the difference between *code* 
and *data*.

Code, or programs, or functions, is the thing that does stuff. That's a 
bit vague, but you should get the idea: you can have a function to print 
a list of telephone addresses, or control a microwave oven, or delete 
unneeded records in a database. You know,... stuff.

Data is the things that functions work on: numbers, strings, lists of 
data, addresses, and things like that. Data doesn't do anything, it just 
sits there in a file, or in a variable, waiting for a function to do 
stuff with it.

The idea for "higher-order functions" came from one simple, but radical, 
concept: the idea that functions themselves can ALSO be data. The idea 
is simple: it's like the idea of building a tool to build the tool you 
actually need. But this was quite a radical idea, because many computer 
languages enforced a strict separation of functions and data.

Fortunately Python is not one of those languages. In Python, we say that 
"functions are first-class objects" -- you can treat functions like 
numbers, or strings, or lists, or any other data. The difference is, you 
just refer to the function by name without following it with brackets:

len  # The built-in function itself.
len(x)  # Calling the function len on argument x.


So you can write one function that takes another function as argument, 
and does something useful with that function:

def draw_graph(function, x_min, x_max):
     # Draw a graph of function between x_min and x_max.
     ...

You won't believe how hard that is in languages like Pascal that don't 
have first class functions!

Here's a working example. Suppose you are doing a lot of string 
processing, using string.upper(), string.lower() etc. And you want to 
see what they do, when they get called. So you might write a function 
like this:

def pr_upper(s):
     print(s)
     return str.upper(s)  # you may be more familiar with the syntax
                          # s.upper() instead of str.upper(s)


and then instead of using str.upper, you use pr_upper instead. Now you 
want to do the same for str.lower, str.title, str.capitalize, and any 
other string functions you might have. This gets tedious and boring, 
writing all these little functions by hand. So, make a tool to make the 
tools you want! We write a *factory function* that creates new functions 
for us:

def make_pr(function):
     # Return a new function that prints the argument first.
     def inner(s):
         print(s)
         return function(s)
     return inner  # Return the inner function we just built.

pr_upper = make_pr(str.upper)
pr_lower = make_pr(str.lower)
pr_split = make_pr(str.split)

Of course, there's no reason why we're limited to built-in functions. It 
also works on our own functions:

def spammer(food):
     return "spam and %s" % food

spammer("eggs")  # returns "spam and eggs"

pr_spammer = make_pr(spammer)


make_pr is a higher-order function -- it's a function that treats other 
functions as data. Python come with at least four higher-order functions 
built in, plus some more in various libraries. I'm not going to talk 
about them all, but I'll mention three of them: map, filter and reduce.

(The fourth, apply, is obsolete and has been removed completely from 
Python 3. Don't worry about it, but if you care, you can look it up in 
the manual.)


(1) map takes a function and a sequence of values, and it applies the 
function to each value in the sequence. For example:

# convert items to strings
map(str, [1, 2, 3])  # Python 2
=> ['1', '2', '3']

In Python 3, map has been changed to be lazy. It no longer returns the 
new list all at once, but returns a special *iterator* object that gives 
one value at a time, on request. This is much more memory efficient, but 
you can get the old behaviour back by using the function list():

list(map(str, [1, 2, 3]))  # Python 3
=> ['1', '2', '3']



(2) filter takes a function and a sequence of values, and returns those 
values where function returns true. For example:

# filter only uppercase strings
filter(str.isupper, ['a', 'B', 'c', 'D'])  # Python 2
=> ['B', 'D']

Again, in Python 3, filter has become lazy.



(3) reduce is perhaps the trickiest of the built-in high-order 
functions. Again, it takes a function and a sequence of values. It grabs 
the first two values, and feeds them to the function to get a result. 
Then it takes that result, and the next value, and feeds them into the 
function to get the next result. And repeats, until there's no more values.

An example might help. Back in the old days, before Python had a sum() 
function, the easiest way to add up a list of numbers was to use reduce 
and a small function to add two numbers:

def add(x, y):
     return x+y

total = filter(add, [2, 4, 5, 9, 1])

Step by step, filter would do this:

Take the first two values, 2 and 4, and feed them to add:
add(2, 4) -> 6
Take it and the next value, 5, and feed them to add:
add(6, 5) -> 11
Take it and the next value, 9, and feed them to add:
add(11, 9) -> 20
Take it and the next value, 1, and feed them to add:
add(20, 1) -> 21
So the final result is 21.


A lot of people find reduce() too hard to understand, and so sadly in 
Python 3 it has been banished from the built-in functions into the 
functools library.



Hope this helps,




-- 
Steven