Use Functional Programming In Python
$\huge \lambda$
Consider the following code:
x = 1 + 1
x = 2 * x # Your math teacher would be very angry
In elementary school, your teacher would tell you that $1 + 1 = 2$, and $2 \neq 2 \times 2$.
Reassigning values is common practice in the world of programming. And as we try to build solutions that are easy to change, somewhere in the depths of our program’s structure we may observe some unexpected behavior:
multiply_by_two(1) # 4
Quite strange. As we dig deeper, the strange behavior can be traced back to multiply_by_two – which seems to be reaching out to the global variable x – the one we had just updated:
# Somewhere deep down in our program
def multiply_by_two(y):
return x * y
And now the function returns 4 rather than 2.
For you as a developer, mutations and unreliable functions may result in many hours of debugging, many context switches, and a heavy cognitive load.
In this post we will have a look at how Functional Programming – a paradigm that relies on pure functions and immutable data – can really make your code more robust, and a lot easier to reason about.
Topics
1. Purity
Functions that are deterministic and don’t have side effects, are called “pure functions”.
Pure functions are mathematical functions:
They associate each element of a set with exactly one element of another set (possibly the same set). Let’s have a look at this example:
$$f(x) = x^x$$
This function $f$ associates the input $2$ with the output $4$, that’s the only thing it does, and this association is always the same:
def f(x):
return x**x
f(2) # 4
f(2) # 4
Why does this matter?
It matters because these properties make the functions: cacheable, self documenting, testable, trivial to parallelize, and most importantly; reasonable.
It literally tells you what the function is operating on. And it guarantees that you’ll get a predictable answer. This makes the function very easy to use, and allows you to reason about the function locally. Let’s demonstrate the difference with a small example.
Here’s a function that gives us the last element of a list:
l = [1, 2, 3]
def last():
return l.pop()
last() # 3
This function works perfectly fine, but look what happens if we call it a second time:
last() # 2
last() # 1
l # []
It returns a different value each time we call last(). And on top of that, it removes all elements from our original list as a side effect. The function is absolutely impure!
An arguably better way to implement the same function would be, as a mathematical function:
l = [1, 2, 3]
def last(l):
return l[-1]
last(l) # 3
We can safely call this function numerous times with the guarantee that we obtain the exact same result as before:
last(l) # 3
l # [1, 2, 3]
And as you can see: no side effects; our original list is left untouched. We can say that pure functions are referentially transparent:
l = [1, 2, 3]
x, y = l, l
if x == y:
print(last(x) == last(y)) # True
We can safely replace all expressions last(l) with the output value, without changing the program’s behavior. But beware, this only holds if our list l is not mutated behind our backs!
If all functions involved in an expression are pure functions, and the arguments to the functions are immutable, then the entire expression is said to be referentially transparent.
2. Immutability
Another cornerstone of Functional Programming is immutability. As our pure functions are deterministic, we may memoize the result for a given input value. But if our function accepts a mutable list l as an argument twice, how do we know that l is the same thing the second time around? It could’ve changed in the meantime:
l = [1, 2, 3]
def outer(l):
def last():
return l[-1]
return last
last = outer(l)
Imagine that we have two threads in our program, and one of them calls a function last, passing a list l as an argument. Then in another thread, we mutate the list. What would happen to the return value of last?
last() # 3
l[2] = 45
l # [1, 2, 45]
last() # 45
The argument just points to a location in memory, and the value in that location has changed. Even the purest function can’t promise you anything if the arguments that are passed are mutable. Instead, we could make our list immutable. This can be achieved by freezing, or by converting to any immutable built-in data structure, such as: int, bool, float, str, tuple, or frozenset:
l = [1, 2, 3]
t = tuple(l)
t # (1, 2, 3)
t[0] = 45 # TypeError: 'tuple' object does not support item assignment
Memoization conceptually only works if the arguments to a function are “hashable”. In python that means that the argument object has a dunder method __hash__ that helps us figure out whether the object is still the same. All immutable built-in python objects are hashable:
l = [1, 2, 3]
t = tuple(l)
hash(t) # 529344067295497451
dictionary = {}
dictionary[t] = 'This is a tuple'
dictionary[l] = 'This is a list' # TypeError: unhashable type: 'list'
Now that we’ve converted our list into a tuple, we’re be able to apply memoization:
# from functools import lru_cache <- what you'd normally import
def lru_cache(f):
"""Memoize (just for showcase)."""
cache = {}
def inner(*args, **kwargs):
key = (*args, tuple(sorted(kwargs.items())))
if key not in cache:
cache[key] = f(*args, **kwargs)
return cache[key]
return inner
Let’s see this in action:
from time import sleep
@lru_cache # decorate our `last` function
def last(l):
sleep(2) # let's pretend that our computer is doing stuff
return l[-1]
When we call the function twice:
last(t) # ... 3 (after 2 seconds)
last(t) # 3 (instantly)
As you can see, the second time we call last, passing the same immutable value t, we receive the cached result, rather than recomputing the result all over.
3. Complexity
At this point you may be wondering: these things are all very nice, but how do we build big complex programs using functions? Why do we need functions anyway? Can’t we just write one big program? Loops, if statements, and assignments.
We really need functions, so that we can structure our program, decompose and recompose it. ~Bartosz Milewski
In order to do that, we need a language that supports first-class functions, so we can store them in variables and pass them around.
Here we call outer with the argument 10, it returns a function inner along with an environment, and we store that in variable f:
def outer(a):
def inner(b):
return a + b
return inner
f = outer(10)
This is called a closure, capturing the local free variable a:
# In python you can inspect the closure
f.__closure__[0].cell_contents # 10 (this is our `a`)
And finally, we can use our inner function, by calling f:
f(5) # 15
The term “first class” is closely related to “higher order”, which is more of a mathematical term to denote that an individual function operates on functions.
We can generalize this concept, and take existing functions, apply currying and function composition to create brand new ones. The cell below will give you an idea of how curry is implemented, but it is advised to use functional library like toolz instead:
# from toolz import curry <- what you'd normally import
from functools import wraps, partial
from re import search
def curry(f):
"""Curry (just for showcase)."""
@wraps(f)
def inner(*a, **kw):
try:
return f(*a, **kw)
except TypeError as e:
pattern = '[\w]?missing \d required positional'
if not search(pattern, str(e)):
raise
return wraps(f)(curry(partial(f, *a, **kw)))
return inner
The term “currying” is a reference to logician Haskell Curry.
Using the function above, we can create curried functions, with which we can create new functions by passing less arguments than the function actually requires:
@curry
def add(x, y):
return x + y
add_three = add(3) # our new function
add_three(2) # 5
As you can see, we receive a new function if we don’t pass all the required arguments. But if the last argument is supplied, the function is evaluated:
@curry
def add(x, y, z):
return x + y + z
add(1, 2, 3) # 6
add(1, 2)(3) # 6
add(1)(2, 3) # 6
add(1)(2)(3) # 6
Besides currying, function composition is an operation that takes two functions $f$ and $g$ and produces a function $h$ such that $h(x) = g(f(x))$. Bear in mind that the types, domains and codomains of the arguments and return values must line up, so that $f:X\rightarrow Y$ and $g:Y\rightarrow Z$ are composed into a function $h:X\rightarrow Z$.
Here’s a helper function that allows us to compose multiple functions at once:
# from toolz import compose <- what you'd normally import
from functools import reduce
def compose(*fs):
"""Compose (just for showcase)."""
def identity(x):
return x
def compose2(f, g):
return lambda x: g(f(x))
return reduce(compose2, fs, identity)
Let’s create the composition $g$ after $f$, also denoted as $g \circ f$:
def f(x):
return x * 100
def g(y):
return y + .5
h = compose(f, g)
And our happy new pure function $h$ is born:
h(0) # 0.5
h(1) # 100.5
We can combine these techniques to make very specific complex functions:
import re
sub = curry(re.sub)
snakecase = compose(sub(' ', '_'),
sub('[^A-Za-z_]+', ''),
str.lower)
snakecase('Hello World!') # hello_world
Awesome right?
4. Iteration
Pure functional languages don’t support control flow such as for and while loops. Instead, iteration is achieved via recursion.
def fibo(n, x=0, y=1):
if n < 1:
return y
return fibo(n - 1, y, x + y)
fibo(5) # 8
Not all languages support tail call optimization:
fibo(1000000) # RecursionError: maximum recursion depth exceeded in comparison
Each function call creates a stack frame, and it is destroyed whenever when the function exits or raises an exception. Or, until you reach the recursion limit:
import sys
sys.getrecursionlimit() # 3000
sys.setrecursionlimit(2147483647)
fibo(1000000) # [1] 3288 segmentation fault (core dumped) python
Our stack is overflowing!
Some languages recycle the current execution frame whenever a tail call is made. Guido van Rossum (author of python) tried to explain the reason why python doesn’t have tail call optimization.
However, if you’re really persistent, you can implement it yourself:
def bet(func):
"""Y-combinator, thanks to baruchel.
See: https://github.com/baruchel/tco
"""
b = (lambda f: (lambda x: x(x))(lambda y:
f(lambda *args: lambda: y(y)(*args))))(func)
def wrapper(*args):
out = b(*args)
while callable(out):
out = out()
return out
return wrapper
@bet
def fibo(f):
def inner(n, x=0, y=1):
return y if n < 1 else f(n - 1, y, x + y)
return inner
fibo(1000000) # 316047687386689873445841912205309135498634108...
We’ve only scratched the surface, but I hope you feel inspired to further investigate this subject!
