In this article I’m presenting a way of using functional programming in Python, highlighting some benefits and a few shortfalls. There are plenty of scholars out there; this is mostly a hobbyist’s perspective, so please don’t consider this to be the ultimate word.
Declarative vs imperative programming
One difference between declarative and imperative programming is that, on the former, you tell the computer what to do, while on the latter you tell it how to do it. The examples below will give more clarity on this.
Object oriented programming
OOP (for short) is one example of imperative programming. You model the data and behavior in classes and, on run time, the program instantiates classes into objects. A class can be viewed as the blueprint of the data you want to handle and how it should behave, while the objects are the data itself.
Four basic principles of OOP:1
- Abstraction: Modeling the relevant attributes and interactions of entities as classes to define an abstract representation of a system.
- Encapsulation: Hiding the internal state and functionality of an object and only allowing access through a public set of functions.
- Inheritance: Ability to create new abstractions based on existing abstractions.
- Polymorphism: Ability to implement inherited properties or methods in different ways across multiple abstractions.
Even though Python does not fully implement all principles, everything in Python is an object. For example:
>>> a=1
>>> type(a)
<class 'int'>
Which means, a is an instance of class int, therefore an object.
Functional programming
FP (for short) is one example of declarative programming. These are a few principles:
- Pure functions
- Functions must accept at least one argument
- Functions return data or another function
- No loops
- Stateless (whenever the function runs, it’s like it’s running for the first time; in other words, given the same inputs, the output will always be the same)
- No side effects (when the function runs, nothing outside of its scope will change)
- Immutable values
- Scalar variables are constant
- If a function needs, for example, to alter an array, then instead it should make an altered copy of the array and return it
- Referential transparency
- An expression is called referentially transparent if it can be replaced with its corresponding value (and vice-versa) without changing the program’s behavior. This requires that the expression be pure: its value must be the same for the same inputs and its evaluation must have no side effects. An expression that is not referentially transparent is called referentially opaque.2
Practical example #1: factorials
This is one way of defining a function to calculate the factorial of a number using imperative programming:
def factorial1(n: int) -> int:
result = 1
for i in range(2, n+1):
result *= i
return result
There are two side effects (result and i), both of which are mutable, and there is one for loop. Regardless, how does it perform?
%%timeit
factorial1(1558)
308 μs ± 12.6 μs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)
Note: 1,558 is the largest input I could find that does not break the function.
Here’s the same function, this time using functional programming principles:
def factorial2(n: int) -> int:
return 1 if n < 2 else n * factorial2(n-1)
%%timeit
factorial2(1558)
407 μs ± 13.1 μs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)
It’s roughly 25% slower.
Python allows us to define lambda functions, which also adhere to functional programming principles. Here’s one way of writing the same function:
factorial3 = lambda n: 1 if n < 2 else n * factorial3(n-1)
%%timeit
factorial3(1558)
403 μs ± 14.7 μs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)
It’s almost as fast as the previous example, and again much slower than using imperative programming. Also, we’re not measuring resource usage here, although we do know that recursion does consume memory.
Practical example #2: the Fibonacci sequence
Here’s a simple implementation using imperative programming:
def fibonacci1(n: int) -> int:
a, b = 0, 1
for i in range(n):
a, b = b, a + b
return a
Likewise, there are three side effects (a, b, and i), all of which mutable, and one for loop.
%%timeit
fibonacci1(20577)
3.67 ms ± 147 μs per loop (mean ± std. dev. of 7 runs, 100 loops each)
Once again, 20,577 is that largest input I could find that does not break the function.
Let’s try a purely functional approach to the Fibonacci sequence.
fibonacci3 = lambda n: n if n < 2 else fibonacci3(n-1) + fibonacci3(n-2)
It becomes unbearably slow, as can be seen here (I tried a smaller number just to make it palatable).
%%timeit -n 10
fibonacci3(30)
78.9 ms ± 1.55 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
For the sake of comparison, here’s the timing when using the purely imperative approach.
%%timeit -n 1000
fibonacci1(30)
928 ns ± 278 ns per loop (mean ± std. dev. of 7 runs, 1,000 loops each)
A pinch of dynamic programming
The first problem with the Fibonacci sequence is that there are two recursions: fibonacci3(n-1) and fibonacci3(n-2).
The other problem, maybe even worse, is that the function keeps recalculating the same value over and over again. As an example, what happens when we run fibonacci3(30)? It runs for 29, which runs for 28, 27, 26, etc. and then it runs for 28 AGAIN! Why can’t we reuse what has been previously calculated?
In comes dynamic programming. One of its principles is to break down a problem into smaller subproblems and solve them on at a time, and then solve the bigger one. In this case, we can use it as an optimization over plain recursion. Wherever we see a recursive solution that has repeated calls for same inputs, we can optimize it using dynamic programming. The idea is to simply store the results of subproblems, so that we do not have to re-compute them when needed later. This simple optimization reduces time complexities from exponential to polynomial.3
Here’s one implementation:
cache = {}
def fibonacci4(n: int) -> int:
if n not in cache:
cache[n] = n if n < 2 else fibonacci4(n-1) + fibonacci4(n-2)
return cache[n]
Not only cache is mutable, but it’s also a huge side effect, as it will linger forever. In Python, however, we could minimize the risk of another function to alter cache by placing it on an external file.
How does it perform? It’s hard to determine the maximum amount at which it breaks, so I’ll just use a number of my choice.
%%timeit
fibonacci4(1000)
42.5 ns ± 0.907 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
For the sake of comparison, once again I present you the timing when using the purely imperative approach.
%%timeit
fibonacci1(1000)
35.4 μs ± 1.34 μs per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
The numbers speak for themselves: the dynamic programming examples runs in a fraction of the time used by other paradigms. This is because, most of the time, the function is just returning the value that had been previously calculated.
In case you were wondering, the cache is, indeed, preserved between runs.
len(cache)
1001
Memoization
The technique we just used up here is called memoization. According to Wikipedia, “In computing, memoization or memoisation is an optimization technique used primarily to speed up computer programs by storing the results of expensive function calls to pure functions and returning the cached result when the same inputs occur again.”
Fortunately for us, Python has plenty of rabbits we can hide in our hats. A quick search online will show us a number of possibilities, some built in, others we can build ourselves without having to recreate them over and over again.
I, for one, prefer to keep things simple. On average, those who preceded me have spent significant time building effective implementations of a comprehensive solution to a problem, and the best I can do is, at the least, evaluate their solution. Let’s begin by having a look at functools.lru_cache:
from functools import lru_cache
@lru_cache
def fibonacci2a(n : int) -> int:
return n if n < 2 else fibonacci2a(n-1) + fibonacci2a(n-2)
%%timeit
fibonacci2a(1000)
38.7 ns ± 1.05 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
Another possibility is to use functools.cache. The difference is that cache doesn’t enforce a limit whilst lru_cache does.
from functools import cache
@cache
def fibonacci2b(n : int) -> int:
return n if n < 2 else fibonacci2b(n-1) + fibonacci2b(n-2)
%%timeit
fibonacci2b(1000)
37.6 ns ± 0.98 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
The other difference is that cache could be faster than lru_cache because, among other reasons, it doesn’t have to manage limits. Care must be taken, though, because resource consumption could increase significantly over time and it would be very hard to pinpoint the root cause.
By the way, did you notice that the examples using cache and lru_cache ran faster than my previous code caching intermediate results internally (fibonacci4)?
Functional programming is not perfect
Reading Athreya aka Maneshwar’s article on object oriented versus functional programming made me think of it a little bit deeper. Let’s review some principles.
Functions must accept at least one argument
In this case, we can’t have a random number generator. We can have arguments specifying the type of number, its length, or range, but depending on the implementation they aren’t always required.
Stateless
Given the same inputs, the output will always be the same. Really? For a random number generator, I definitely don’t want to have the very same output over and over again. Even if it repeats itself, eventually I must get a different number.
As for file handling, assuming I’m reading from a file that hasn’t changed, then I’m always reading the same data. If the file changes, however, we’re breaking this rule.
The same applies to databases. After someone updates the database (which is usually expected), the data being read is no longer the same.
Scalar variables are constant
All of the above is manageable and can be accepted, but if scalar variables must be constant, then there’s no way we can implement a counter, for example.
Here’s a counter class:
class Counter1:
def __init__(self) -> None:
self.counter = 0
def increment(self):
self.counter += 1
return self
def get(self) -> int:
return self.counter
The scalar variable self.counter is mutable and changes with every call to increment.
c1 = Counter1()
c1.get()
0
[c1.increment().get() for x in range(10)]
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
Subsequent calls will yield increasing numbers. No surprises here.
Let’s enforce the rule:
class Counter2:
def __init__(self, value=0) -> None:
self.counter = value
def increment(self):
return Counter2(self.counter + 1)
def get(self) -> int:
return self.counter
The scalar variable self.counter is immutable. There is no provision to change it. Calling increment will, instead, instantiate a new object with a new, immutable, incremented value.
c2 = Counter2()
c2.get()
0
c2 = c2.increment()
c2.get()
1
c2 = c2.increment()
c2.get()
2
Subsequent calls will yield increasing numbers. No surprises here either… but there’s a caveat: if we don’t reassign the new object to a variable, we’ll be working with stale data. For example:
[c2.increment().get() for x in range(10)]
[3, 3, 3, 3, 3, 3, 3, 3, 3, 3]
In this example, c2 keeps pointing to the original object instead of the updated one. That’s why it keeps returning the same value. Even worse, if we pass c2 as an argument to another object, then for as long as the object is active, it will keep operating on obsolete data.
Let’s solve this (and prove myself wrong)
Here’s one way of doing it:
class Hidden_Counter:
def __init__(self, value=0):
self.hidden_counter = value
def increment(self):
return Hidden_Counter(self.hidden_counter + 1)
def get(self):
return self.hidden_counter
class Counter3:
def __init__(self):
self.counter = Hidden_Counter()
def increment(self):
self.counter = self.counter.increment()
return self.counter
def get(self):
return self.counter.get()
You add this code to a separate source file. Wherever you need to use it, you add from <name> import Counter3, which guarantees that Hidden_Counter remains hidden. Hidden_Counter keeps reinstatiating itself for every increment while Counter3 keeps references intact.
c3 = Counter3()
c3.get()
0
[c3.increment().get() for x in range(10)]
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
You can do the same using inner classes.
class Counter4:
class Hidden_Counter:
def __init__(self, value=0):
self.hidden_counter = value
def increment(self):
return Hidden_Counter(self.hidden_counter + 1)
def get(self):
return self.hidden_counter
def __init__(self):
self.counter = Hidden_Counter()
def increment(self):
self.counter = self.counter.increment()
return self.counter
def get(self):
return self.counter.get()
c4 = Counter4()
c4.get()
0
[c4.increment().get() for x in range(10)]
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
In many programming languages, no code outside of an enclosing class has any visibility of inner classes.
The Golden Hammer antipattern
The Golden Hammer antipattern permeates from a development team’s overreliance on a single tool set, pattern, platform, or other component of the development workflow. It is a classic pitfall that any team faces when they have gained some level of expertise in a particular solution or methodology. This antipattern is appropriately summarized using the following adage: “When all you have is a hammer, everything looks like a nail.”4
One of the main advantages of functional programming is its simplicity. Given the same results for the same inputs, and given there are no side effects, it’s easy to debug. Resource consumption and execution time may be issues and must be taken into account. In my past experience as a software engineer, however, I should say that only in rare occasions I dealt with deep recursion levels. The most notable case was so many years ago, when I had to look up data in a hierarchical data structure. Resources were at a premium and my program was crashing at random intervals. My very talented data architect came to the rescue, creating a new database view for me, and my problems went away.
Or, at the least, that one.
There are purely declarative programming languages. Likewise, there are purely imperative programming languages. You may be stuck.
There are, nonetheless, multiparadigm programming languages. You’ll have the option to choose how to write your code. Against the Golden Hammer antipattern, remember that you have multiple tools and techniques at your disposal, so do yourself a favor and choose the best one for solving the problem at hand.
Revision history
- 2024-05-15: Original posting date.
- 2025-03-16: New hardware.
- 2025-03-17: Problems with functional programming.
- 2025-03-18: Correcting my own mistakes.