Functional Programming in Python

Chapter 4. Higher-Order Functions

In the last chapter we saw an iterator algebra that builds on the itertools module. In some ways, higher-order functions (often abbreviated as “HOFs”) provide similar building blocks to express complex concepts by combining simpler functions into new functions. In general, a higher-order function is simply a function that takes one or more functions as arguments and/or produces a function as a result. Many interesting abstractions are available here. They allow chaining and combining higher-order functions in a manner analogous to how we can combine functions in itertools to produce new iterables.

A few useful higher-order functions are contained in the functools module, and a few others are built-ins. It is common the think of map(), filter(), and functools.reduce() as the most basic building blocks of higher-order functions, and most functional programming languages use these functions as their primitives (occasionally under other names). Almost as basic as map/filter/reduce as a building block is currying. In Python, currying is spelled as partial(), and is contained in the functools module—this is a function that will take another function, along with zero or more arguments to pre-fill, and return a function of fewer arguments that operates as the input function would when those arguments are passed to it.

The built-in functions map() and filter() are equivalent to comprehensions—especially now that generator comprehensions are available—and most Python programmers find the comprehension versions more readable. For example, here are some (almost) equivalent pairs:

# Classic "FP-style"
transformed = map(tranformation, iterator)
# Comprehension
transformed = (transformation(x) for x in iterator)

# Classic "FP-style"
filtered = filter(predicate, iterator)
# Comprehension
filtered = (x for x in iterator if predicate(x))

The function functools.reduce() is very general, very powerful, and very subtle to use to its full power. It takes successive items of an iterable, and combines them in some way. The most common use case for reduce() is probably covered by the built-in sum(), which is a more compact spelling of:

from functools import reduce
total = reduce(operator.add, it, 0)
# total = sum(it)

It may or may not be obvious that map() and filter() are also a special cases of reduce(). That is:

>>> add5 = lambda n: n+5
>>> reduce(lambda l, x: l+[add5(x)], range(10), [])
[5, 6, 7, 8, 9, 10, 11, 12, 13, 14]
>>> # simpler: map(add5, range(10))
>>> isOdd = lambda n: n%2
>>> reduce(lambda l, x: l+[x] if isOdd(x) else l, range(10), [])
[1, 3, 5, 7, 9]
>>> # simpler: filter(isOdd, range(10))

These reduce() expressions are awkward, but they also illustrate how powerful the function is in its generality: anything that can be computed from a sequence of successive elements can (if awkwardly) be expressed as a reduction.

There are a few common higher-order functions that are not among the “batteries included” with Python, but that are very easy to create as utilities (and are included with many third-party collections of functional programming tools). Different libraries—and other programming languages—may use different names for the utility functions I describe, but analogous capabilities are widespread (as are the names I choose).

Utility Higher-Order Functions

A handy utility is compose(). This is a function that takes a sequence of functions and returns a function that represents the application of each of these argument functions to a data argument:

def compose(*funcs):
    """Return a new function s.t.
       compose(f,g,...)(x) == f(g(...(x)))"""
    def inner(data, funcs=funcs):
        result = data
        for f in reversed(funcs):
            result = f(result)
        return result
    return inner

# >>> times2 = lambda x: x*2
# >>> minus3 = lambda x: x-3
# >>> mod6 = lambda x: x%6
# >>> f = compose(mod6, times2, minus3)
# >>> all(f(i)==((i-3)*2)%6 for i in range(1000000))
# True

For these one-line math operations (times2, minus3, etc.), we could have simply written the underlying math expression at least as easily; but if the composite calculations each involved branching, flow control, complex logic, etc., this would not be true.

The built-in functions all() and any() are useful for asking whether a predicate holds of elements of an iterable. But it is also nice to be able to ask whether any/all of a collection of predicates hold for a particular data item in a composable way. We might implement these as:

all_pred = lambda item, *tests: all(p(item) for p in tests)
any_pred = lambda item, *tests: any(p(item) for p in tests)

To show the use, let us make a few predicates:

>>> is_lt100 = partial(operator.ge, 100)    # less than 100?
>>> is_gt10 = partial(operator.le, 10)      # greater than 10?
>>> from nums import is_prime          # implemented elsewhere
>>> all_pred(71, is_lt100, is_gt10, is_prime)
True
>>> predicates = (is_lt100, is_gt10, is_prime)
>>> all_pred(107, *predicates)
False

The library toolz has what might be a more general version of this called juxt() that creates a function that calls several functions with the same arguments and returns a tuple of results. We could use that, for example, to do:

>>> from toolz.functoolz import juxt
>>> juxt([is_lt100, is_gt10, is_prime])(71)
(True, True, True)
>>> all(juxt([is_lt100, is_gt10, is_prime])(71))
True
>>> juxt([is_lt100, is_gt10, is_prime])(107)
(False, True, True)

The utility higher-order functions shown here are just a small selection to illustrate composability. Look at a longer text on functional programming—or, for example, read the Haskell prelude—for many other ideas on useful utility higher-order-functions.

The operator Module

As has been shown in a few of the examples, every operation that can be done with Python’s infix and prefix operators corresponds to a named function in the operator module. For places where you want to be able to pass a function performing the equivalent of some syntactic operation to some higher-order function, using the name from operator is faster and looks nicer than a corresponding lambda. For example:

# Compare ad hoc lambda with `operator` function
sum1 = reduce(lambda a, b: a+b, iterable, 0)
sum2 = reduce(operator.add, iterable, 0)
sum3 = sum(iterable)    # The actual Pythonic way

The functools Module

The obvious place for Python to include higher-order functions is in the functools module, and indeed a few are in there. However, there are surprisingly few utility higher-order functions in that module. It has gained a few interesting ones over Python versions, but core developers have a resistence to going in the direction of a full functional programming language. On the other hand, as we have seen in a few example above, many of the most useful higher-order functions only take a few lines (sometimes a single line) to write yourself.

Apart from reduce(), which is discussed at the start of this chapter, the main facility in the module is partial(), which has also been mentioned. This operation is called “currying” (after Haskell Curry) in many languages. There are also some examples of using partial() discussed above.

The remainder of the functools module is generally devoted to useful decorators, which is the topic of the next section.

Decorators

Although it is—by design—easy to forget it, probably the most common use of higher-order functions in Python is as decorators. A decorator is just syntax sugar that takes a function as an argument, and if it is programmed correctly, returns a new function that is in some way an enhancement of the original function (or method, or class). Just to remind readers, these two snippets of code defining some_func and other_func are equivalent:

@enhanced
def some_func(*args):
    pass

def other_func(*args):
    pass
other_func = enhanced(other_func)

Used with the decorator syntax, of course, the higher-order function is necessarily used at definition time for a function. For their intended purpose, this is usually when they are best applied. But the same decorator function can always, in principle, be used elsewhere in a program, for example in a more dynamic way (e.g., mapping a decorator function across a runtime-generated collection of other functions). That would be an unusual use case, however.

Decorators are used in many places in the standard library and in common third-party libraries. In some ways they tie in with an idea that used to be called “aspect-oriented programming.” For example, the decorator function asyncio.coroutine is used to mark a function as a coroutine. Within functools the three important decorator functions are functools.lru_cache, functools.total_ordering, and functools.wraps. The first “memoizes” a function (i.e., it caches the arguments passed and returns stored values rather than performing new computation or I/O). The second makes it easier to write custom classes that want to use inequality operators. The last makes it easier to write new decorators. All of these are important and worthwhile purposes, but they are also more in the spirit of making the plumbing of Python programming easier in a general—almost syntactic—way rather than the composable higher-order functions this chapter focuses on.

Decorators in general are more useful when you want to poke into the guts of a function than when you want to treat it as a pluggable component in a flow or composition of functions, often done to mark the purpose or capabilities of a particular function.

This report has given only a glimpse into some techniques for programming Python in a more functional style, and only some suggestions as to the advantages one often finds in aspiring in that direction. Programs that use functional programming are usually shorter than more traditional imperative ones, but much more importantly, they are also usually both more composable and more provably correct. A large class of difficult to debug errors in program logic are avoided by writing functions without side effects, and even more errors are avoided by writing small units of functionality whose operation can be understood and tested more reliably.

A rich literature on functional programming as a general technique—often in particular languages which are not Python—is available and well respected. Studying one of many such classic books, some published by O’Reilly (including very nice video training on functional programming in Python), can give readers further insight into the nitty-gritty of functional programming techniques. Almost everything one might do in a more purely functional language can be done with very little adjustment in Python as well.