Tag: functional programming

Functional Programming in Python

Leave a comment

Before I get started I should acknowledge a number of sources that form the basis for this post. First and foremost, Guido van Rossum and Fred Drake, Jr.’s excellent ‘Functional Programming HOWTO’ for Python 2.6.2, and secondly David Mertz’s book ‘Text Processing in Python’, which both served to convince me of the benefits of functional programming. Check them out, they’re freely available and both extremely well written (although neither is really suitable for beginners). Also the Abelson and Sussman text ‘Structure and Interpretation of Computer Programs’ from which I borrow a couple of examples.

The programming languages I started out learning were mostly procedural: in C, a program solves a problem by having the computer execute a set of instructions in a particular order. I then moved on to object-oriented programming in languages like VB, Ruby and Python – solving a problem is accomplished by designing, reading and changing the internal state of objects which model the problem. Both of these models are imperative, in that they are characterised by telling the computer to do something. There is typically a lot of assignment to the different variables which make up the state machine of the program. For a very simple example, the function sum_to below finds the sum of integers up to the argument n (the nth trianglular number):

def sum_to(n):
  a = 0
  for x in range(n + 1):
    a += x
  return a

>>> sum_to(10)
55

This relies on the repeated assignment of new values to the variable a, which holds the value which is eventually returned. The state of the variables x and a is maintained throughout the program’s execution.

Functional programming, as the name suggests, is centred on functions – a program written in a functional style relies on the evaluation of functions, which turn input into output without the need to waste code on maintaining internal state. The sum_to function could be rewritten in a functional style as follows:

def sum_to(n):
  return sum(range(n+1))

>>> sum_to(10)
55

Python fully supports writing functional code, although as the examples above illustrate, you don’t have to. So why would you? No doubt there is some advantage to not having to maintain a potentially complex internal state machine, which does make functional code easier to write IMO; I guess potentially also there is some performance advantage to be gained by not having so much clutter in the namespace. However, I find the two best reasons for using functional code are

  1. It encourages functional decomposition. This is a good thing. Rather than make the classic mistake of trying to solve a complex problem with a single monolithic procedure (which is of course usually possible but which will probably have those who maintain your code cursing your name for years to come), the program flow will ideally go from input through a series of small, easily debugged functions to eventual output. This is an approach which I think appeals to me at least in part because it’s similar to what I do when I construct a spreadsheet model. In fact, worksheet functions in any spreadsheet are a very good example of purely functional programming – each function simply takes input and produces output. It also appeals because it improves code reusability and composability.
  2. Higher-order functions. These are like function constructors: functions which take functions as arguments and return functions as outputs. This is an extremely convenient abstraction, as it enables you to concentrate on the concepts involved in the problem, rather than getting lost in the detail of how the concepts are handled.

Python has a lot of builtin tools to support higher-order functions: generator expressions and list comprehensions provide concise statements for large structures, and the reduce() function iteratively applies a function to an sequence. To take an example from SICP, a useful functional abstraction is the summation of a series of terms. We can construct a ‘function factory’ for the general series, which takes as  arguments the function used to construct the terms, and the iterator that supplies the argument to that function:

def sum_terms(term, objIter):
  '''
  sum_terms: function constructor
  Usage: term is a function taking a single argument
         objIter is an iterable object returning the arguments for term
  Returns: a function to calculate a sum of terms in a series
  '''
  return sum([term(x) for x in objIter])

Because this abstracts out the process of summation, the problem of constructing a large series is decomposed nicely into two smaller sub-problems. So, for instance, I can construct the triangular sum function from earlier by splitting the task into the construction of the term (the identity function) and the range to apply it to (for an argument n, the range of integers from 1 to n):

>>> identity = lambda x: x
>>> inc = lambda n: range(1, n + 1)
>>> sum_triangle = lambda x: sum_terms(identity, inc(x))
>>> sum_triangle(10)
55

I can also create a function for summing a series of cubes: \sum_{i=1}^n i^3

>>> cube = lambda x: x**3
>>> sum_cubes = lambda x: sum_terms(cube, inc(x))
>>> sum_cubes(10)
3025

A slightly more complex series can give an approximate numerical solution for the definite integral of a function over an interval:

\int_a^b f(x) \, dx = \delta*\sum_{k=1}^{(b-a)/\delta} f(a+\delta/2 +k*\delta)

In this case, the arguments a and b determine the length of the interval and dx sets the width of the subintervals used:

def integral(func, a, b, dx):
  def rng(a, b, dx): 
    return ((a + dx/2 + k*dx) for k in range(int((b-a)/dx)))
  return dx*sum_terms(func, rng(a, b, dx))

This then returns an integration function which can be applied to any function. Testing it out on the cube function:

>>> integral(cube, 0, 1, 0.01)
0.24998750000000006

which evaluates exactly to 1/4.