Tech Blog

Functional programming traces its history to Alonzo Church's lambda calculus. As such, it is often symbolized by a lambda.

Writing Functional Python

Recently updated on

The recent buzz surrounding Functional Programming (FP for short) is well deserved. Languages like Haskell and Clojure in use by big name companies such as Barclays CaptialAtlassian, and Walmart have helped FP ideas gain a major foothold in the industry. I am a Clojure hobbyist who has been interested in FP for some time so this is great news to me. But what exactly is FP, and why should a Python/Django programmer care?  First, understanding FP will help you bring these sought-after ideas into your Python development. Second, you will quite likely begin to recognize instances where you have already been using these concepts, unknowingly!

Programming languages have been designed using a number of paradigms as problems in the software development process needed to be solved. Although each paradigm has its own strengths and weaknesses, I'm not here to examine which is best. Instead, for the sake of comparison, let’s look at how each of these paradigms works. Here are some of the major players:

  • Imperative Programming 
    • This paradigm is characterized by a series of computational instructions that are written to describe how a task should be completed. Each instruction is typically executed sequentially and makes changes to the state of a program (values stored in variables/memory). Most imperative languages fall within the subset paradigm called Procedural Programming, which is distinct because computational steps can be grouped into "procedures" or "functions" to be called many times, improving modularity and providing better scoping. Imperative programming most closely models how the majority of computer hardware actually performs computation.
    • Languages: C, Fortran, Go
  • Object-Oriented Programming  (OOP)
    • These languages provide a way of organizing code into collections of objects that can be manipulated. Each object has its own state (set of variables) and methods that allow the programmer to alter that state. A very simple example would be a Car object with a fuelLevel variable as part of its state that can be altered with a fillTank() method.
    • Languages: Java, Smalltalk
  • Declarative Programming
    • Languages in this paradigm focus on describing what problem needs to be solved but not how to actually solve it as you would in imperative languages. The program is fed to a black-box that returns the desired result.
    • Languages: SQL, Prolog, Regular Expressions, Markup languages
  • Functional Programming (FP)
    • This style of programming revolves around decomposing problems into a series of functions. Ideally, these functions will resemble mathematical functions and avoid changing state. They merely take an input value and produce an output. This is typically referred to as avoiding "side-effects."  Writing a program in this style consists of chaining several of these "pure" functions together.
    •  Languages: Haskell, Clojure, Scheme, Erlang

Luckily for us, we are using Python which is a multi-paradigm language including elements of imperative/procedural programming, OOP, and FP.

Why is FP good? The key is in the constraint that functions ideally should not change any state. That's right -- no changing variables passed to your functions allowed. The payoff of this is that functions become trivially composable. You can feed the output of one function right to the next without having to worry about the state of the program. This leads to a mental image of a program as a single stream of data that passes through a series of functions to produce a desired result. Because we don't have to worry about state in a purely functional section of code, finding problems in your code is much easier, and debuggers (which are all about examining state) end up sitting on the shelf getting dusty. 

How does functional Python look? Take a look at this somewhat contrived un-functional function.

def remove_odd(num_list):
    for num in num_list:
        if num % 2 != 0:
            num_list.remove(num)
    return num_list

This is un-functional because it has side-effects. Any list passed to the remove_odd function is changed by the function since lists are are a mutable type in Python and are passed by reference. That is, when you pass a list to a function its contents can change. Lists, dictionaries, and sets are all mutable types and can suffer from this un-functional fate. The same is often true of user defined objects that have internal state. 

>>> a = [1, 2, 3, 4]
>>> b = remove_odd(a)
>>> b
[2, 4]
>>> a
[2, 4]

Notice how the value of the original list changed even though all we did was pass it to the function. This is what we mean when we say a function has side-effects. Calling the function has affected state outside of the function. 

Here's the same function written to be functional in style. 

def remove_odd_func(num_list):
    return [num for num in num_list if num % 2 == 0]

The list comprehension creates a new list and doesn't change the variable passed to the function. This is a "pure" function. 

>>> a = [1, 2, 3, 4]
>>> b = remove_odd_func(a)
>>> b
[2, 4]
>>> a
[1, 2, 3, 4]

Notice how even though the function gives us the correct list of values, it leaves our original list intact. This function has no side-effects. List comprehensions are a nice tool for writing more functional code. 

Iterators are another especially useful tool for writing functional Python. I had mentioned that the mental model for functional programming is a single stream of data flowing through a series of functions. Iterators are a way of representing streams of data in Python. They are implemented by providing a next() function which is called to get each item in the stream. The built-in function iter() gets the iterator for an object if it supports iteration. 

>>> a = [5, 10, 15]
>>> i = iter(a)
>>> i.next()
5
>>> i.next()
10
>>> i.next()
15
>>> i.next()
Traceback (most recent call last):
  File "<console>", line 1, in <module>
StopIteration

Lists, sets, and dictionaries all support iterators out of the box. You can also write your own iterators by implementing next() in a class, or similarly, if you want to make an object iterable you can implement __iter__() which should return an iterator.

You can use iterators to insert data streams into lists or tuples as well. This is a way to get all of the results from a functional data stream that you've been operating on.

>>> i = iter(a)
>>> b = tuple(i)
>>> b
(5, 10, 15)

Using iterators to write more functional code can be done by applying functions to an iterator. Some built-in functions that do this include max() and min().  Note that our original list has not changed at all despite these operations.

>>> i = iter(a)
>>> m = max(i)
>>> m
15

Generators expand upon the idea of iterators by allowing you to produce a new stream of data based on a stream of input. Generators make use of the yield keyword to indicate what value should be returned. Let's rewrite our remove_odd function to produce a generator.

def remove_odd_gen(iter):
    for i in iter:
        if i % 2 == 0:
            yield i

Now we can use our new generator in conjunction with an iterator to get a new stream of only even numbers.

>>> nums = [1, 2, 3, 4, 5]
>>> i = iter(nums)
>>> eveni = remove_odd_gen(i)
>>> eveni.next()
2
>>> eveni.next()
4
>>> eveni.next()
Traceback (most recent call last):
  File "<console>", line 1, in <module>
StopIteration

Generators are a powerful tool which can make your code more efficient. You'll never need to iterate over a list multiple times again! Python also provides generator expressions, which are similar to list comprehensions except they are evaluated lazily by creating a generator. They allow you to create generators like before much more concisely. Here's the same example as above written using a generator expression.

>>> nums = [1, 2, 3, 4, 5]
>>> i = iter(nums)
>>> eveni = (n for n in i if n % 2 == 0) # generator expression
>>> eveni.next()
2
>>> eveni.next()
4

It's important to clarify that iterators and generators, if written properly, will only execute to get the next item as needed. This is what is meant by saying they are evaluated lazily. This is unlike list comprehensions which will produce the entire list right way which you then iterate over, meaning you will likely iterate twice over some collection. Again, we want to think in terms of manipulating streams of data.

Python also provides some functions that are specifically intended for writing more functional code, namely map(), filter() and reduce(). These allow you to take an iterable collection of some sort (typically a list or set) apply a function to every element in different ways.

The map() function takes an iterable and a function and returns a list with the function applied to every item. 

>>> nums = [1, 2, 3, 4]
>>> def square(x):
...     return x*x
>>> map(square, nums)
[1, 4, 9, 16]

The filter() function takes an iterable and a boolean function and returns a list with only items for which the function is true. 

>>> nums = [1, 2, 3, 4, 5, 6]
>>> def multiple_of_three(n):
...     return n % 3 == 0
>>> filter(multiple_of_three, nums)
[3, 6]

Both map() and filter() have corresponding functions in the itertools module called imap() and ifilter() respectively. These function improve upon the originals by returning iterators which will evaluate lazily instead of generating an entire list right away. 

The reduce() function takes an iterable and collapses it to a single value using the provided function between each value. You can also optionally provide an initial value. Here's a more interesting example that uses reduce to do function composition -- so functional! It also makes use of Python's lambda notation which is nice syntax sugar for defining small functions inline.

>>> def call(x, f):
...     return f(x)
>>> square = lambda x : x*x
>>> increment = lambda x : x+1
>>> cube = lambda x : x*x*x
>>> decrement = lambda x : x-1
>>> funcs = [square, increment, cube, decrement]
>>> reduce(call, funcs, 2)
124

This makes it very easy to swap out or reorder the functions manipulating a stream of data. Imagine if instead of 2 as an initial value we used a generator of some sort, and the list of functions all produced subsequent generators. This pattern can be very powerful.

Your Python code will become cleaner and easier to read the more you work with and practice Functional Programming. I think you will be satisfied with the results as you bring these concepts into your development. In a follow-up article, I plan to discuss how you can use these ideas in the context of Django and where the Django framework has already made use of these concepts.

Comments

Comments are closed.