Functional programming defines a computation using expressions and evaluation—often encapsulated in function definitions. It de-emphasizes or avoids the complexity of state change and mutable objects. This tends to create programs that are more succinct and expressive. In this article, we’ll introduce some of the techniques that characterize functional programming. We’ll identify some of the ways to map these features to Python. Finally, we’ll also address some ways in which the benefits of functional programming accrue when we use these design patterns to build Python applications.

Python has numerous functional programming features. It is not a purely functional programming language. It offers enough of the right kinds of features that it confers to the benefits of functional programming. It also retains all optimization power available from an imperative programming language.

We’ll also look at a problem domain that we’ll use for many of the examples in this book. We’ll try to stick closely to Exploratory Data Analysis (EDA) because its algorithms are often good examples of functional programming. Furthermore, the benefits of functional programming accrue rapidly in this problem domain.

Our goal is to establish some essential principles of functional programming.

We’ll focus on Python 3 features in this book. However, some of the examples might also work in Python 2.

(For more resources related to this topic, see here.)

Identifying a paradigm

It’s difficult to be definitive on what fills the universe of programming paradigms. For our purposes, we will distinguish between just two of the many programming paradigms: Functional programming and Imperative programming. One important distinguishing feature between these two is the concept of state.

In an imperative language, like Python, the state of the computation is reflected by the values of the variables in the various namespaces. The values of the variables establish the state of a computation; each kind of statement makes a well-defined change to the state by adding or changing (or even removing) a variable. A language is imperative because each statement is a command, which changes the state in some way.

Our general focus is on the assignment statement and how it changes state. Python has other statements, such as global or nonlocal, which modify the rules for variables in a particular namespace. Statements like def, class, and import change the processing context. Other statements like try, except, if, elif, and else act as guards to modify how a collection of statements will change the computation’s state. Statements like for and while, similarly, wrap a block of statements so that the statements can make repeated changes to the state of the computation. The focus of all these various statement types, however, is on changing the state of the variables.

Ideally, each statement advances the state of the computation from an initial condition toward the desired final outcome. This “advances the computation” assertion can be challenging to prove. One approach is to define the final state, identify a statement that will establish this final state, and then deduce the precondition required for this final statement to work. This design process can be iterated until an acceptable initial state is derived.

In a functional language, we replace state—the changing values of variables—with a simpler notion of evaluating functions. Each function evaluation creates a new object or objects from existing objects. Since a functional program is a composition of a function, we can design lower-level functions that are easy to understand, and we will design higher-level compositions that can also be easier to visualize than a complex sequence of statements.

Function evaluation more closely parallels mathematical formalisms. Because of this, we can often use simple algebra to design an algorithm, which clearly handles the edge cases and boundary conditions. This makes us more confident that the functions work. It also makes it easy to locate test cases for formal unit testing.

It’s important to note that functional programs tend to be relatively succinct, expressive, and efficient when compared to imperative (object-oriented or procedural) programs. The benefit isn’t automatic; it requires a careful design. This design effort is often easier than functionally similar procedural programming.

Subdividing the procedural paradigm

We can subdivide imperative languages into a number of discrete categories. In this section, we’ll glance quickly at the procedural versus object-oriented distinction. What’s important here is to see how object-oriented programming is a subset of imperative programming. The distinction between procedural and object-orientation doesn’t reflect the kind of fundamental difference that functional programming represents.

We’ll use code examples to illustrate the concepts. For some, this will feel like reinventing a wheel. For others, it provides a concrete expression of abstract concepts.

For some kinds of computations, we can ignore Python’s object-oriented features and write simple numeric algorithms. For example, we might write something like the following to get the range of numbers:

s = 0
for n in range(1, 10):
    if n % 3 == 0 or n % 5 == 0:
        s += n
print(s)

We’ve made this program strictly procedural, avoiding any explicit use of Python’s object features. The program’s state is defined by the values of the variables s and n. The variable, n, takes on values such that 1 ≤ n < 10. As the loop involves an ordered exploration of values of n, we can prove that it will terminate when n == 10. Similar code would work in C or Java using their primitive (non-object) data types.

We can exploit Python’s Object–Oriented Programming (OOP) features and create a similar program:

m = list()
for n in range(1, 10):
    if n % 3 == 0 or n % 5 == 0:
        m.append(n)
print(sum(m))

This program produces the same result but it accumulates a stateful collection object, m, as it proceeds. The state of the computation is defined by the values of the variables m and n.

The syntax of m.append(n) and sum(m) can be confusing. It causes some programmers to insist (wrongly) that Python is somehow not purely Object-oriented because it has a mixture of the function()and object.method() syntax. Rest assured, Python is purely Object-oriented. Some languages, like C++, allow the use of primitive data type such as int, float, and long, which are not objects. Python doesn’t have these primitive types. The presence of prefix syntax doesn’t change the nature of the language.

To be pedantic, we could fully embrace the object model, the subclass, the list class, and add a sum method:

class SummableList(list):
    def sum( self ):
        s= 0
        for v in self.__iter__():
            s += v
        return s

If we initialize the variable, m, with the SummableList() class instead of the list() method, we can use the m.sum() method instead of the sum(m) method. This kind of change can help to clarify the idea that Python is truly and completely object-oriented. The use of prefix function notation is purely syntactic sugar.

All three of these examples rely on variables to explicitly show the state of the program. They rely on the assignment statements to change the values of the variables and advance the computation toward completion. We can insert the assert statements throughout these examples to demonstrate that the expected state changes are implemented properly.

The point is not that imperative programming is broken in some way. The point is that functional programming leads to a change in viewpoint, which can, in many cases, be very helpful. We’ll show a function view of the same algorithm. Functional programming doesn’t make this example dramatically shorter or faster.

Using the functional paradigm

In a functional sense, the sum of the multiples of 3 and 5 can be defined in two parts:

• The sum of a sequence of numbers
• A sequence of values that pass a simple test condition, for example, being multiples of three and five

The sum of a sequence has a simple, recursive definition:

def sum(seq):
    if len(seq) == 0: return 0
    return seq[0] + sum(seq[1:])

We’ve defined the sum of a sequence in two cases: the base case states that the sum of a zero length sequence is 0, while the recursive case states that the sum of a sequence is the first value plus the sum of the rest of the sequence. Since the recursive definition depends on a shorter sequence, we can be sure that it will (eventually) devolve to the base case.

The + operator on the last line of the preceeding example and the initial value of 0 in the base case characterize the equation as a sum. If we change the operator to * and the initial value to 1, it would just as easily compute a product.

Similarly, a sequence of values can have a simple, recursive definition, as follows:

def until(n, filter_func, v):
    if v == n: return []
    if filter_func(v): return [v] + until( n, filter_func, v+1 )
    else: return until(n, filter_func, v+1)

In this function, we’ve compared a given value, v, against the upper bound, n. If v reaches the upper bound, the resulting list must be empty. This is the base case for the given recursion.

There are two more cases defined by the given filter_func() function. If the value of v is passed by the filter_func() function, we’ll create a very small list, containing one element, and append the remaining values of the until() function to this list. If the value of v is rejected by the filter_func() function, this value is ignored and the result is simply defined by the remaining values of the until() function.

We can see that the value of v will increase from an initial value until it reaches n, assuring us that we’ll reach the base case soon.

Here’s how we can use the until() function to generate the multiples of 3 or 5. First, we’ll define a handy lambda object to filter values:

mult_3_5= lambda x: x%3==0 or x%5==0

(We will use lambdas to emphasize succinct definitions of simple functions. Anything more complex than a one-line expression requires the def statement.)

We can see how this lambda works from the command prompt in the following example:

>>> mult_3_5(3)
True
>>> mult_3_5(4)
False
>>> mult_3_5(5)
True

This function can be used with the until() function to generate a sequence of values, which are multiples of 3 or 5.

The until() function for generating a sequence of values works as follows:

>>> until(10, lambda x: x%3==0 or x%5==0, 0)
[0, 3, 5, 6, 9]

We can use our recursive sum() function to compute the sum of this sequence of values. The various functions, such as sum(), until(), and mult_3_5() are defined as simple recursive functions. The values are computed without restoring to use intermediate variables to store state.

We’ll return to the ideas behind this purely functional recursive function definition in several places. It’s important to note here that many functional programming language compilers can optimize these kinds of simple recursive functions. Python can’t do the same optimizations.

Using a functional hybrid

We’ll continue this example with a mostly functional version of the previous example to compute the sum of the multiples of 3 and 5. Our hybrid functional version might look like the following:

print( sum(n for n in range(1, 10) if n%3==0 or n%5==0) )

We’ve used nested generator expressions to iterate through a collection of values and compute the sum of these values. The range(1, 10) method is an iterable and, consequently, a kind of generator expression; it generates a sequence of values . The more complex expression, n for n in range(1, 10) if n%3==0 or n%5==0, is also an iterable expression. It produces a set of values . A variable, n, is bound to each value, more as a way of expressing the contents of the set than as an indicator of the state of the computation. The sum() function consumes the iterable expression, creating a final object, 23.

The bound variable doesn’t change once a value is bound to it. The variable, n, in the loop is essentially a shorthand for the values available from the range() function.

The if clause of the expression can be extracted into a separate function, allowing us to easily repurpose this with other rules. We could also use a higher-order function named filter() instead of the if clause of the generator expression.

As we work with generator expressions, we’ll see that the bound variable is at the blurry edge of defining the state of the computation. The variable, n, in this example isn’t directly comparable to the variable, n, in the first two imperative examples. The for statement creates a proper variable in the local namespace. The generator expression does not create a variable in the same way as a for statement does:

>>> sum( n for n in range(1, 10) if n%3==0 or n%5==0 )
23
>>> n
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
NameError: name 'n' is not defined

Because of the way Python uses namespaces, it might be possible to write a function that can observe the n variable in a generator expression. However, we won’t. Our objective is to exploit the functional features of Python, not to detect how those features have an object-oriented implementation under the hood.

Looking at object creation

In some cases, it might help to look at intermediate objects as a history of the computation. What’s important is that the history of a computation is not fixed. When functions are commutative or associative, then changes to the order of evaluation might lead to different objects being created. This might have performance improvements with no changes to the correctness of the results.

Consider this expression:

>>> 1+2+3+4
10

We are looking at a variety of potential computation histories with the same result. Because the + operator is commutative and associative, there are a large number of candidate histories that lead to the same result.

Of the candidate sequences, there are two important alternatives, which are as follows:

>>> ((1+2)+3)+4
10
>>> 1+(2+(3+4))
10

In the first case, we fold in values working from left to right. This is the way Python works implicitly. Intermediate objects 3 and 6 are created as part of this evaluation.

In the second case, we fold from right-to-left. In this case, intermediate objects 7 and 9 are created. In the case of simple integer arithmetic, the two results have identical performance; there’s no optimization benefit.

When we work with something like the list append, we might see some optimization improvements when we change the association rules.

Here’s a simple example:

>>> import timeit
>>> timeit.timeit("((([]+[1])+[2])+[3])+[4]")
0.8846941249794327
>>> timeit.timeit("[]+([1]+([2]+([3]+[4])))")
1.0207440659869462

In this case, there’s some benefit in working from left to right.

What’s important for functional design is the idea that the + operator (or add() function) can be used in any order to produce the same results. The + operator has no hidden side effects that restrict the way this operator can be used.

The stack of turtles

When we use Python for functional programming, we embark down a path that will involve a hybrid that’s not strictly functional. Python is not Haskell, OCaml, or Erlang. For that matter, our underlying processor hardware is not functional; it’s not even strictly object-oriented—CPUs are generally procedural.

All programming languages rest on abstractions, libraries, frameworks and virtual machines. These abstractions, in turn, may rely on other abstractions, libraries, frameworks and virtual machines. The most apt metaphor is this: the world is carried on the back of a giant turtle. The turtle stands on the back of another giant turtle. And that turtle, in turn, is standing on the back of yet another turtle.

It’s turtles all the way down.

                                                                                                            – Anonymous
There’s no practical end to the layers of abstractions.

More importantly, the presence of abstractions and virtual machines doesn’t materially change our approach to designing software to exploit the functional programming features of Python.

Even within the functional programming community, there are more pure and less pure functional programming languages. Some languages make extensive use of monads to handle stateful things like filesystem input and output. Other languages rely on a hybridized environment that’s similar to the way we use Python. We write software that’s generally functional with carefully chosen procedural exceptions.

Our functional Python programs will rely on the following three stacks of abstractions:

• Our applications will be functions—all the way down—until we hit the objects
• The underlying Python runtime environment that supports our functional programming is objects—all the way down—until we hit the turtles
• The libraries that support Python are a turtle on which Python stands

The operating system and hardware form their own stack of turtles. These details aren’t relevant to the problems we’re going to solve.

A classic example of functional programming

As part of our introduction, we’ll look at a classic example of functional programming. This is based on the classic paper Why Functional Programming Matters by John Hughes. The article appeared in a paper called Research Topics in Functional Programming, edited by D. Turner, published by Addison-Wesley in 1990.

Here’s a link to the paper Research Topics in Functional Programming:

http://www.cs.kent.ac.uk/people/staff/dat/miranda/whyfp90.pdf

This discussion of functional programming in general is profound. There are several examples given in the paper. We’ll look at just one: the Newton-Raphson algorithm for locating the roots of a function. In this case, the function is the square root.

It’s important because many versions of this algorithm rely on the explicit state managed via loops. Indeed, the Hughes paper provides a snippet of the Fortran code that emphasizes stateful, imperative processing.

The backbone of this approximation is the calculation of the next approximation from the current approximation. The next_() function takes x, an approximation to the sqrt(n) method and calculates a next value that brackets the proper root. Take a look at the following example:

def next_(n, x):
    return (x+n/x)/2

This function computes a series of values . The distance between the values is halved each time, so they’ll quickly get to converge on the value such that, which means . We don’t want to call the method next() because this name would collide with a built-in function. We call it the next_() method so that we can follow the original presentation as closely as possible.

Here’s how the function looks when used in the command prompt:

>>> n= 2
>>> f= lambda x: next_(n, x)
>>> a0= 1.0
>>> [ round(x,4) for x in (a0, f(a0), f(f(a0)), f(f(f(a0))),) ]
[1.0, 1.5, 1.4167, 1.4142]

We’ve defined the f() method as a lambda that will converge on . We started with 1.0 as the initial value for . Then we evaluated a sequence of recursive evaluations: , and so on. We evaluated these functions using a generator expression so that we could round off each value. This makes the output easier to read and easier to use with doctest. The sequence appears to converge rapidly on .

We can write a function, which will (in principle) generate an infinite sequence of values converging on the proper square root:

def repeat(f, a):
    yield a
    for v in repeat(f, f(a)):
        yield v

This function will generate approximations using a function, f(), and an initial value, a. If we provide the next_() function defined earlier, we’ll get a sequence of approximations to the square root of the n argument.

The repeat() function expects the f() function to have a single argument, however, our next_() function has two arguments. We can use a lambda object, lambda x: next_(n, x), to create a partial version of the next_() function with one of two variables bound.

The Python generator functions can’t be trivially recursive, they must explicitly iterate over the recursive results, yielding them individually. Attempting to use a simple return repeat(f, f(a)) will end the iteration, returning a generator expression instead of yielding the sequence of values.

We have two ways to return all the values instead of returning a generator expression, which are as follows:

• We can write an explicit for loop as follows:

  for x in some_iter: yield x.

• We can use the yield from statement as follows:

  yield from some_iter.

Both techniques of yielding the values of a recursive generator function are equivalent. We’ll try to emphasize yield from. In some cases, however, the yield with a complex expression will be more clear than the equivalent mapping or generator expression.

Of course, we don’t want the entire infinite sequence. We will stop generating values when two values are so close to each other that we can call either one the square root we’re looking for. The common symbol for the value, which is close enough, is the Greek letter Epsilon, ε, which can be thought of as the largest error we will tolerate.

In Python, we’ll have to be a little clever about taking items from an infinite sequence one at a time. It works out well to use a simple interface function that wraps a slightly more complex recursion. Take a look at the following code snippet:

def within(ε, iterable):
    def head_tail(ε, a, iterable):
        b= next(iterable)
        if abs(a-b) <= ε: return b
        return head_tail(ε, b, iterable)
    return head_tail(ε, next(iterable), iterable)

We’ve defined an internal function, head_tail(), which accepts the tolerance, ε, an item from the iterable sequence, a, and the rest of the iterable sequence, iterable. The next item from the iterable bound to a name b. If , then the two values that are close enough together that we’ve found the square root. Otherwise, we use the b value in a recursive invocation of the head_tail() function to examine the next pair of values.

Our within() function merely seeks to properly initialize the internal head_tail() function with the first value from the iterable parameter.

Some functional programming languages offer a technique that will put a value back into an iterable sequence. In Python, this might be a kind of unget() or previous() method that pushes a value back into the iterator. Python iterables don’t offer this kind of rich functionality.

We can use the three functions next_(), repeat(), and within() to create a square root function, as follows:

def sqrt(a0, ε, n):
    return within(ε, repeat(lambda x: next_(n,x), a0))

We’ve used the repeat() function to generate a (potentially) infinite sequence of values based on the next_(n,x) function. Our within() function will stop generating values in the sequence when it locates two values with a difference less than ε.

When we use this version of the sqrt() method, we need to provide an initial seed value, a0, and an ε value. An expression like sqrt(1.0, .0001, 3) will start with an approximation of 1.0 and compute the value of to within 0.0001. For most applications, the initial a0 value can be 1.0. However, the closer it is to the actual square root, the more rapidly this method converges.

The original example of this approximation algorithm was shown in the Miranda language. It’s easy to see that there are few profound differences between Miranda and Python. The biggest difference is Miranda’s ability to construct cons, a value back into an iterable, doing a kind of unget. This parallelism between Miranda and Python gives us confidence that many kinds of functional programming can be easily done in Python.

Summary

We’ve looked at programming paradigms with an eye toward distinguishing the functional paradigm from two common imperative paradigms in details.

For more information kindly take a look at the following books, also by Packt Publishing:

• Learning Python (https://www.packtpub.com/application-development/learning-python)
• Mastering Python (https://www.packtpub.com/application-development/mastering-python)
• Mastering Object-oriented Python (https://www.packtpub.com/application-development/mastering-object-oriented-python)

Resources for Article:

---

Further resources on this subject:

• Saying Hello to Unity and Android [article]
• Using Specular in Unity [article]
• Unity 3.x Scripting-Character Controller versus Rigidbody [article]

---