13
Functional Programming
Controlling complexity is the essence of computer programming.
Brian Kernighan
In This Chapter
As you have seen so far in this book, a Python program, at its most basic, is composed of a series of statements, which can be simple or compound. The way in which you organize these statements has ramifications for performance, readability, and ease of modification. Some approaches that have been widely adopted are procedural programming, functional programming, and object-oriented programming. This chapter introduces some of the concepts of functional programming, including comprehensions and generators, both of which were borrowed from purely functional languages.
Introduction to Functional Programming
Functional programming is based on the mathematical definition of functions. A function, in this sense, maps an input to an output. For any input, there can only be a single output; in other words, the output for a distinct input will always be the same. Some programming languages, such as Haskell and Erlang, adhere to this limitation strictly. Python is flexible enough that it can adopt some functional concepts without the strictness. Functional programming in Python is sometimes referred to as functional light programming.
Scope and State
The state of a program comprises names, definitions, and values that exist at a certain time in that program, including function definitions, modules imported, and values assigned to variables. State has what’s known as a scope—the area of the program for which the state holds. Scopes are hierarchical. When you indent a block of code, this code has a nested scope. It inherits scope from the unindented code around it but does not directly change the outer scope.
Listing 13.1 sets values for the variables a and b in the outer scope. Then the code block of the function sets a to a different value and prints both variables. You can see that when the function is called, it uses its own definition of the variable a but inherits that definition for b from the outer scope. In the outer scope, the value assigned by the function to a is ignored, as it is out of scope.
Listing 13.1 Inheriting Scope
a = 'a outer'
b = 'b outer'
def scoped_function():
a = 'a inner'
print(a)
print(b)
scoped_function()
a inner
b outer
print(a)
a outer
print(b)
b outer
Depending on Global State
The code in this book up until now has mostly been presented using the procedural approach. In this approach, the current state is defined by the statements that have run on the lines before the present one. This state is shared through the program and modified throughout. This means that a function that uses the state to determine its output could have a different output with the same input. Let’s look at some examples contrasting the procedural approach with a functional one.
Listing 13.2 creates a function, describe_the_wind(), which returns a sentence using a variable, wind, defined in the outer scope. You can see that the output of this function will be different depending on this variable.
Listing 13.2 Depending on Outer Scope
wind = 'Southeast'
def describe_the_wind():
return f'The wind blows from the {wind}'
describe_the_wind()
'The wind blows from the Southeast'
wind = 'North'
describe_the_wind()
'The wind blows from the North' f
A more functional approach is to pass the variable as an argument. In this way, the function will return the same value for a value passed to it, regardless of the outer state:
def describe_the_wind(wind):
return f'The wind blows from the {wind}'
describe_the_wind('Northeast')
'The wind blows from the Northeast'
Changing State
In addition to not relying on outside state, a functional function should not directly change outside state. Listing 13.3 shows a program that changes an outer state variable, WIND, within the function change_wind(). Notice the use of the keyword global, which indicates to change an outer state variable rather than define a new variable in the inner state.
Listing 13.3 Modifying Outer Scope
WINDS = ['Northeast', 'Northwest', 'Southeast', 'Southwest']
WIND = WINDS[0]
def change_wind():
global WIND
WIND = WINDS[(WINDS.index(WIND) + 1)%3]
WIND
'Northeast'
change_wind()
WIND
'Northwest'
for _ in WINDS:
print(WIND)
change_wind()
Northwest
Southeast
Northeast
Northwest
A more functional approach to getting the same output is to move the winds variable into the inner state and have the function change_wind() take an argument to determine the output, as shown in Listing 13.4.
Listing 13.4 Not Modifying Outer Scope
def change_wind(wind_index):
winds = ['Northeast', 'Northwest', 'Southeast', 'Southwest']
return winds[wind_index]
print( change_wind(0) )
Northeast
print( change_wind(1) )
Northwest
print( change_wind(2) )
Southeast
print( change_wind(3) )
Southwest
Changing Mutable Data
A more subtle way of changing outside state is by passing mutable objects. Remember that mutable objects are objects, such as lists and dictionaries, whose contents can be changed. If you set a variable in an outer state, pass it as an argument to a function, and then change its value in the function’s inner state, the outer state version of the variable will retain its original value. Here is an example:
b = 1
def foo(a):
a = 2
foo(b)
print(b)
1
However, if you pass a mutable object, such as a dictionary, as an argument to a function, any change made to that object in the function will be reflected in the outer state as well. The following example defines a function that takes a dictionary as an argument and changes one of its values:
d = {"vehicle": "ship", "owner": "Joseph Bruce Ismay"}
def change_mutable_data(data):
'''A function which changes mutable data.'''
data['owner'] = 'White Star Line'
change_mutable_data(d)
print(d)
{'vehicle': 'ship', 'owner': 'White Star Line'}
You can see that the dictionary, d, when passed to this function, had its value changed in the outer state.
Changing the outside scope of mutable objects in this manner can lead to subtle bugs. One way to avoid this, if your data structure isn’t too big, is to make a copy in the inner scope, and manipulate the copy:
d = {"vehicle": "ship", "owner": "Joseph Bruce Ismay"}
def change_owner(data):
new_data = data.copy()
new_data['owner'] = 'White Star Line'
return new_data
changed = change_owner(d)
changed
{'owner': 'White Star Line', 'vehicle': 'ship'}
By working on the copy, it is much easier to see where the values are changed.
Functional Programming Functions
Three built-in Python functions that come from the functional programming world are map(), filter(), and reduce().
The map() function applies to a sequence of values and returns a map object. The input sequence can be any iterable type—that is, any object that can be iterated, such as a Python sequence. The map object returned is an iterable also, so you can loop through it or cast it to a list to view the results:
def grow_flowers(d):
return d * "❀"
gardens = map(grow_flowers, [0,1,2,3,4,5])
type(gardens)
map
list(gardens)
['', '❀', '❀❀', '❀❀❀', '❀❀❀❀', '❀❀❀❀❀']
You can supply map() with a function that takes multiple arguments and supply multiple sequences of input values:
l1 = [0,1,2,3,4]
l2 = [11,10,9,8,7,6]
def multi(d1, d2):
return d1 * d2
result = map(multi, l1, l2)
print( list(result) )
[0, 10, 18, 24, 28]
Notice in this example that one of the input sequences is longer than the other. The map() function stops when it reaches the end of the shortest input sequence.
The reduce() function also takes a function and an iterable as arguments. It then uses the function to return a single value, based on the input. For example, if you want to subtract an amount from an account balance, you can do it with a for loop, like this:
initial_balance = 10000
debits = [20, 40, 300, 3000, 1, 234]
balance = initial_balance
for debit in debits:
balance -= debit
balance
6405
You could achieve the same result by using the reduce() function, like this:
from functools import reduce
inital_balance = 10000
debits = [20, 40, 300, 3000, 1, 234]
def minus(a, b):
return a - b
balance = reduce(minus, debits, initial_balance)
balance
6405
The operator module provides all the standard operators as functions, including functions for the standard mathematical operations. You can use the operator.sub() function as an argument to reduce() as a replacement for the minus() function:
from functools import reduce import operator initial_balance = 10000 debits = [20, 40, 300, 3000, 1, 234] reduce(operator.sub, debits, initial_balance) 6405
The filter() function takes a function and an iterable as arguments. The function should return True or False, based on each item. The result is an iterable object of only input values that causes the function to return True. For example, to get only the capital letters from a string, you can define a function that tests whether a character is capitalized and pass it and the string to filter():
charles = 'ChArlesTheBald'
def is_cap(a):
return a.isupper()
retval = filter(is_cap, charles)
list(retval)
['C', 'A', 'T', 'B']
One of the few times I really recommend using lambda functions is when you’re using the map(), filter(), and reduce() functions. When you are doing a simple comparison—such as for all the numbers less than 10 and greater than 3—you can use a lambda function and range() in a clean and easy-to-read way:
nums = filter(lambda x: x > 3, range(10)) list(nums) [4, 5, 6, 7, 8, 9]
List Comprehensions
List comprehensions are syntax borrowed from the functional programming language Haskell (see https://docs.python.org/3/howto/functional.html). Haskell is a fully functional programming language implemented with syntax that lends itself to a purely functional approach. You can think of a list comprehension as a one-line for loop that returns a list. Although the source of list comprehensions is in functional programming, their use has become standard in all Python approaches.
List Comprehension Basic Syntax
The basic syntax for a list comprehension is as follows:
[ <item returned> for <source item> in <iterable> ]
For example, given a list of names for which you want to change the names to title capitalization (so that the first letter is uppercase), you use x.title() as the item returned and each name as a source item:
names = ['tim', 'tiger', 'tabassum', 'theodora', 'tanya'] capd = [x.title() for x in names] capd ['Tim', 'Tiger', 'Tabassum', 'Theodora', 'Tanya']
This would be the equivalent process using a for loop:
names = ['tim', 'tiger', 'tabassum', 'theodora', 'tanya']
capd = []
for name in names:
capd.append(name.title())
capd
['Tim', 'Tiger', 'Tabassum', 'Theodora', 'Tanya']
Replacing map and filter
You can use list comprehensions as replacements for the map() and filter() functions. For example, the following code maps the numbers 0 through 5, with a function that inserts them into a string:
def count_flower_petals(d):
return f"{d} petals counted so far"
counts = map(count_flower_petals, range(6))
list(counts)
['0 petals counted so far',
'1 petals counted so far',
'2 petals counted so far',
'3 petals counted so far',
'4 petals counted so far',
'5 petals counted so far']
You can replace this code with the following much simpler list comprehension:
[f"{x} petals counted so far" for x in range(6)]
['0 petals counted so far',
'1 petals counted so far',
'2 petals counted so far',
'3 petals counted so far',
'4 petals counted so far',
'5 petals counted so far']
You can also add a conditional to a list comprehension, using the following syntax:
[ <item returned> for <source item> in <iterable> if <condition> ]
By using a conditional, you can easily duplicate the functionality of the filter() function. For instance, the following filter() example returns only uppercase letters:
characters = ['C', 'b', 'c', 'A', 'b', 'P', 'g', 'S']
def cap(a):
return a.isupper()
retval = filter(cap, characters)
list(retval)
['C', 'A', 'P', 'S']
You can replace this function with the following list comprehension that uses a conditional:
characters = ['C', 'b', 'c', 'A', 'b','P', 'g', 'S'] [x for x in characters if x.isupper()] ['C', 'A', 'P', 'S']
Multiple Variables
If the items in a source iterable are sequences, you can unpack them by using multiple variables:
points = [(12, 3), (-1, 33), (12, 0)]
[ f'x: {x} y: {y}' for x, y in points ]
['x: 12 y: 3', 'x: -1 y: 33', 'x: 12 y: 0']
You can perform the equivalent of nested for loops by using multiple for statements in the same list comprehensions:
list_of_lists = [[1,2,3], [4,5,6], [7,8,9]] [x for y in list_of_lists for x in y] [1, 2, 3, 4, 5, 6, 7, 8, 9]
Dictionary Comprehensions
Dictionary comprehensions use a syntax similar to that of list comprehensions. However, whereas you append a single value to a list, you add a key/value pair to a dictionary. This example uses the values in two lists to construct a dictionary:
names = ['James', 'Jokubus', 'Shaemus']
scores = [12, 33, 23]
{ name:score for name in names for score in scores}
{'James': 23, 'Jokubus': 23, 'Shaemus': 23}
Generators
One of the big advantages of using a range object over using a list when dealing with big numeric ranges is that the range object calculates results as you request them. This means that its memory footprint is consistently small. Generators let you use your own calculations to create values on demand, working in a similar way to range objects.
Generator Expressions
One way to create generators is through generator expressions, which use the same syntax as list comprehensions except that the enclosing square brackets are replaced with parentheses. This example shows how to create a list and a generator based on the same calculation and print them:
l_ten = [x**3 for x in range(10)]
g_ten = (x**3 for x in range(10))
print(f"l_ten is a {type(l_ten)}")
l_ten is a <class 'list'>
print(f"l_ten prints as: {l_ten}")
l_ten prints as: [0, 1, 8, 27, 64, 125, 216, 343, 512, 729]
print(f"g_ten is a {type(g_ten)}")
g_ten is a <class 'generator'>
print(f"g_ten prints as: {g_ten}")
g_ten prints as: <generator object <genexpr> at 0x7f3704d52f68>
When you print the list, you can see its contents; this is not the case with the generator. To get a value from a generator, you have to request the next value, which you can do by using the next() function:
next(g_ten) 0
Or, more commonly, you can iterate through a generator in a for loop:
for x in g_ten:
print(x)
1
8
27
64
125
216
343
512
729
Because generators only generate values on demand, there is no way to index or slice them:
g_ten[3]
---------------------------------------------------------------------------
TypeError Traceback (most recent call last)
<ipython-input-6-e7b8f961aa33> in <module>()
1
----> 2 g_ten[3]
TypeError: 'generator' object is not subscriptable
One of the important advantages of generators over lists is their memory footprint. The following examples use the sys.getsizeof() function to compare the sizes of a list and a generator:
import sys
x = 100000000
l_big = [x for x in range(x)]
g_big = (x for x in range(x))
print( f"l_big is {sys.getsizeof(l_big)} bytes")
l_big is 859724472 bytes
print( f"g_big is {sys.getsizeof(g_big)} bytes")
g_big is 88 bytes
Generator Functions
You can use generator functions to create complex generators. Generator functions look like normal functions but with the return statement replaced with a yield statement. The generator keeps its own internal state, returning values as requested:
def square_them(numbers):
for number in numbers:
yield number * number
s = square_them(range(10000))
print(next(s))
0
print(next(s))
1
print(next(s))
4
print(next(s))
9
An additional advantage of generators over lists is the ability to create an infinite generator—that is, a generator with no end. An infinite generator returns as many values as requested. For example, you can make a generator that increments a number as many times as you like:
def counter(d):
while True:
d += 1
yield d
c = counter(10)
print(next(c))
11
print(next(c))
12
print(next(c))
13
Listing 13.5 chains together four generators. This is a useful way to keep each generator understandable, while still harnessing the just-in-time calculations of the generators.
Listing 13.5 Generator Pipeline
evens = (x*2 for x in range(5000000))
three_factors = (x//3 for x in evens if x%3 == 0)
titles = (f"this number is {x}" for x in three_factors)
capped = (x.title() for x in titles)
print(f"The first call to capped: {next(capped)}")
The first call to capped: This Number Is 0
print(f"The second call to capped: {next(capped)}") The second call to capped: This
Number Is 2
print(f"The third call to capped: {next(capped)}")
The third call to capped: This Number Is 4
Using generators is a great way to make your code performant. You should consider using them whenever you are iterating through a long sequence of calculated values.
Summary
Functional programming is an approach to organizing programs that is useful for designing software that can be run concurrently. It is based on the idea that a function’s inner state should be changed by or should change the outer state of the code calling it. A function should always return the same value for a given input. Three built-in Python functions that come from the functional programming world are map(), filter(), and reduce(). Using list comprehensions and generators are both very Pythonic ways of creating sequences of values. Using generators is recommended when you’re iterating through any large number of values or when you don’t know how many values you need.
Questions
1. What would the following code print?
a = 1
b = 2
def do_something(c):
c = 3
a = 4
print(a)
return c
b = do_something(b)
print(a + b)
2. Use the map() function to take the string 'omni' and return the list ['oo','mm', 'nn', 'ii'].
3. Use the sum() function, which sums the contents of a sequence, with a list comprehension to find the summation of the positive even numbers below 100.
4. Write a generator expression that returns cubed numbers up to 1,000.
5. A Fibonacci sequence starts with 0 and 1, and every subsequent number is the sum of the previous two numbers. Write a generator function that calculates a Fibonacci sequence.