The Basics of Functional Python

Many folks have jumped on the functional train lately, but Guido (Python’s benevolent dictator for life) has never seemed enthused with the idea of giving python more functional tools. But we won’t let that stand in our way, comrades! Let’s start our journey of discovery by examining how functions are written in Python.

The usual way of defining a function in Python is to use the def statement:

def printit(s):
    print s

This creates a function printit that uses a print statement to print its argument. This is the sensible and conventional way of defining a function, but to get a feel for working with functions as values, let’s play around with the other way:

Anonymous functions

You’re probably also familiar with lambda, Python’s anonymous function feature. Lambda takes its name from the Lambda Calculus, but more to the point probably adopted it from Scheme. Here’s what lambda looks like:

hello = lambda name: printit("Hello, " + name)
hello("Steve")  # => prints "Hello, Steve"

Lambda doesn’t see a lot of usage in contemporary python code. It does not allow statements, such as if or print, in its body, and it’s restricted to only one top-level expression. However, this doesn’t make it incapable. Scheme got on perfectly well without statements, and you can nest to your heart’s content in a single expression. In fact, with just a few functions wrapping statements, you can create your own little meta-language using lambda. We just need to add a few more helpers to the above example to turn if into an expression:

def iff(pred, then_fn, else_fn):
    if pred:
        return then_fn()
    else:
        return else_fn()

hello2 = lambda name=None: iff(
    name is None,
    lambda: printit("Hello World"),
    lambda: printit("Hello, " + name))

hello2()  # => prints "Hello World"
hello2("Jane")  # => prints "Hello, Jane"

And since if is now an expression, we can invert nesting a bit:

hello3 = lambda name=None: printit(
    iff(name is None,
        lambda: "Hello World",
        lambda: "Hello, " + name))

They say if you ever get into a fight, you should endeavor to prove yourself insane and capable of anything, in an attempt to intimidate your opponent into inaction. With that in mind, here’s a neat trick you can show your cowering friends and coworkers.

In combinatorics, the fixed-point combinator (usually called the “Y combinator”) allows one to define a recursive function without requiring recursion. Here is an implementation thereof using only Python’s lambdas. I will not be explaining how it works, and I encourage you not to spend too much time attempting to parse it:

Y = lambda f: (
    (lambda x: f(lambda y: x(x)(y)))(
     lambda x: f(lambda y: x(x)(y))))

You use it by declaring your function using an outer lambda which is passed a reference to self, and an inner one which does the actual computation, and passing that whole mess to Y:

fact = Y(
    lambda self: (
        lambda n: (
            iff(n <= 1,
                lambda: 1,
                lambda: self(n - 1) + self(n - 2)))))

map(fact, range(10))  #=> [1, 1, 2, 3, 5, 8, 13, 21, 34, 55]

I demonstrate this not to encourage you to start writing programs in a dialect of python composed of nested lambda expressions – there are other languages better-suited to that – but to demonstrate the flexibility of Python’s modest lambda against all odds, and to hint at the things you can accomplish (and damage you can do) given access to first-class functions.

Of course, you can use def in any scope to make a new function, so there’s little need to ever use a lambda that you can’t fit on one line. Let’s never speak of it again.

Moving along

All functions in python are first-class; they can be passed as arguments to other functions:

def fact(n):
    if n <= 1:
        return 1
    return fact(n - 1) + fact(n - 2)

map(fact, range(10))  #=> [1, 1, 2, 3, 5, 8, 13, 21, 34, 55]

This allows us to use some of the tools that mathematicians have developed to work with functions. Some of these are built-in to python, some are available in prepackaged modules, and some we’ll have to create, but all are doable.

The most basic function we can use to work with functions is compose. Think of this as adding two functions together — we can compose two functions (f1 and f2) to get another function (g). Applying g to an argument applies f1 to the result of applying f2 to that value. Or, in code:

def f1(arg):
    return arg + "-f1"

def f2(arg):
    return arg + "-f2"

def g(arg):
    return f1(f2(arg))


g("test")  # => "test-f2-f1"

Python doesn’t include a compose function to save us the trouble, but it does include the tools to write one. Let’s try.

def compose(f1, f2):
    def g(arg):
        return f1(f2(arg))
    return g

g = compose(f1, f2)
g("test2")  # => "test2-f2-f1"

Note that our compose applies its functions from right to left, and that this example only works if f1 and f2 accept exactly one argument.

As an aside, some languages, such as Haskell, even go so far as to only ever create one-argument functions. You may have seen type signatures for Haskell functions that look like add :: Int -> Int -> Int. Here, the add function accepts two integers and returns an integer, or at least it seems to. But notice that there is no grouping of the ints. That’s because, theoretically, calling add with two arguments first creates a function with one argument applied, then calls that function on the second argument to return the result. This is called “currying” because Haskell is named after a man named Haskell Curry, and we’ll learn more about it later.

A more restrictive version of this is partial application, for which Python does provide a utility (located in the functools module):

from functools import partial

def hello(name):
    return "Hello, " + name

# Create a function to greet Cathy
hellocathy = partial(hello, "Cathy")

hellocathy()  # => "Hello, Cathy"

You should find partial application to be a perfectly sufficient substitute for currying, in python, although we might come back to it a bit later.

Next article: A Different State of Mind