Functional Programming
Given the importance of sequence processing, Python includes comprehensive, higher-level support for sequence operations, which provides for functional tools and lambda functions.
Functional Tools
You have already seen how to apply an existing function (built-in or external) to items in a sequence using for loops, list comprehensions, and generator expressions. These constructs are explicitly iterative, emphasizing the “for each” mechanism: “for each item matching a condition, transform it, and add to the result.”
Functional tools let you work with sequences as higher-level, abstract (opaque) objects.
The built-in function map creates an iterator that calls another function func using arguments taken from one or more sequences. The number of sequences must match the number of parameters expected by func, and at least one sequence is required.
A call to map(func, data0, data1, ...) is equivalent to the generator expression:
| | (func(*args) for args in zip(data0, data1, ...)) |
That is:
-
Combine the sequences with zip.
-
Iterate through the resulting sequence of tuples.
-
Call func on each unpacked tuple.
However, map is more concise and keeps the focus on the operation rather than on the implementation details. Like any iterator, the result of map can be expanded into a list or used in a for loop, a comprehension, or a generator expression.
In the next example, the built-in function len is applied to each word in the list. The resulting iterator is zipped with the original words to produce (word, length) tuples, which are then used to build a dictionary of words and their lengths:
| | >>> data = ['#Mary', 'had', 'a', 'little', '#lamb'] |
| | |
| | >>> lengths = map(len, data) |
| | >>> dict(zip(data, lengths)) |
| | {'#Mary': 5, 'had': 3, 'a': 1, 'little': 6, '#lamb': 5} |
The mapped function does not have to be built-in; it can be user-defined. Suppose you are automating grading for a six-question true/false quiz. The expected (correct) answers are in expected, and the submitted answers are in real. You can define a function that returns whether a question was answered correctly, and map it over the two lists:
| | >>> expected = [True, False, False, True, True, False] |
| | >>> real = [True, True, True, True, False, False] |
| | >>> def success(x: bool, y: bool) -> bool: |
| | ... """Return True if and only if x equals y |
| | ... |
| | ... >>> success(True, False) |
| | ... False |
| | ... """ |
| | ... return x == y |
| | ... |
| | >>> all(map(success, expected, real)) |
| | False |
The built-in functions all and any (the latter not used in the example) return True if all or any elements of the argument list are True.
The built-in function filter, another functional tool, returns an iterator that yields those items from the input sequence data for which the argument function func is True. Here is a Pythonic way to find the words that are not hashtags (the predicate method str.isalpha checks if the argument string consists only of alphabetic characters), and then measure their lengths by combining the power of filter and map:
| | >>> data = ['#Mary', 'had', 'a', 'little', '#lamb'] |
| | >>> words = filter(str.isalpha, data) |
| | >>> list(words) |
| | ['had', 'a', 'little'] |
| | >>> words = filter(str.isalpha, data) |
| | >>> list(map(len, words)) |
| | [3, 1, 6] |
Note that filter expects a function that takes one argument. There is no standard one-argument predicate that tests whether the first character is a hashtag, so you can write your own and obtain the familiar result:
| | >>> def ishashtag(s: str) -> bool: |
| | ... """Return True if and only if a string starts with a hashtag marker |
| | ... |
| | ... >>> ishashtag('#lamb') |
| | ... True |
| | ... >>> ishashtag('') |
| | ... False |
| | ... """ |
| | ... return s.startswith('#') |
| | ... |
| | >>> hashtags = filter(ishashtag, data) |
| | >>> list(hashtags) |
| | ['#Mary', '#lamb'] |
While writing a one-line throwaway function may feel wasteful, the next section demonstrates a convenient way to handle such cases. Meanwhile, you can find more functional tools in the standard library module functools.
Lambda Functions
Lambda functions are useful for quick predicate checks and simple transformations
A lambda function is essentially a function without a name. As an additional restriction, it must consist of a single expression and have no statements. The value of the expression is returned implicitly. The general form of a lambda function is:
| | lambda args: expr |
Here, args is a possibly empty comma-separated parameter list. Lambda functions are commonly passed as arguments to higher-order functions such as map, filter, and sorted.
Assigning a lambda function to a variable is usually pointless because it is equivalent to defining a “normal,” named function. Lambdas work best for small, one-off tasks (for example, testing whether a word is a hashtag or stripping the first character) that you pass to functional tools and then discard:
| | >>> hashtags = filter( |
| | ... lambda w: w.startswith('#'), # A predicate |
| | ... data) |
| | >>> clean_hashtags = map( |
| | ... lambda w: w[1:], # A transformer |
| | ... hashtags) |
| | >>> list(clean_hashtags) |
| | ['Mary', 'lamb'] |
Writing Your Own Generators
Python functions are typically stateless: unless they read or write global variables (defined outside functions), they do not “remember” previous calls. Once a function returns, its local variables go out of scope (see ) and their values are discarded. In the absence of global variables (whose use is strongly discouraged, because they introduce intricate, hard-to-track relationships between code fragments), a function’s result depends only on the arguments passed to the function.
Some programming languages (for example, C and C++) solve the problem of preserving function state across calls by declaring static variables. Generators are a common Pythonic way to maintain iteration state.
A generator function is a function that contains at least one yield statement (introduced later in this section). Calling a generator function doesn’t run the body immediately; instead, a call returns a generator object. The generator remembers its execution state (including all local variables). When the generator yields a value (for example, via next or a for loop), it suspends execution and returns that value to the caller. On the next request, the generator resumes immediately after the last yield and continues until the next yield (or until it finishes by executing the return statement).
To understand generator functions better, let’s write one that implements a down-counter: it yields a sequence of decreasing positive integer numbers starting from an initial value. The generator function make_down_counter initializes an internal state variable value, then yields it, and decrements it, until value reaches zero. Once exhausted, the generator must be reinitialized. Since all iterators are also generators, you can choose either Iterator or Generator type hint to annotate the function.
| | >>> from collections.abc import Iterator |
| | >>> def make_down_counter(initial: int) -> Iterator[int]: |
| | ... """ Yield a countdown from `initial` down to 1 (inclusive). |
| | ... |
| | ... The argument is converted to an integer using `int(initial)`. |
| | ... If the resulting value is <= 0, the generator yields nothing. |
| | ... |
| | ... >>> list(make_down_counter(3)) |
| | ... [3, 2, 1] |
| | ... """ |
| | ... |
| | ... value = initial |
| | ... while value > 0: |
| | ... yield value |
| | ... value -= 1 |
| | ... return |
| | ... |
| | >>> down_counter = make_down_counter(3) |
| | >>> next(down_counter) |
| | 3 |
| | >>> next(down_counter) |
| | 2 |
| | >>> next(down_counter) |
| | 1 |
| | >>> next(down_counter) |
| | Traceback (most recent call last): |
| | File "<python-input-6>", line 1, in <module> |
| | next(down_counter) |
| | ~~~~^^^^^^^^^ |
| | StopIteration |
You can use the generator either explicitly (as above) or in a loop:
| | >>> down_counter = make_down_counter(3) |
| | >>> for val in down_counter: |
| | ... print(val) |
| | ... |
| | 3 |
| | 2 |
| | 1 |
A pseudo-random number generator (PRNG) is a practical application of generators. A PRNG is a special case of random number generators: sources of random (that is, unpredictable) numbers. Random numbers are extensively used in cryptography, algorithm design, and computer simulations. Unfortunately, truly unpredictable randomness is difficult to obtain, so in many cases, pseudo-random numbers—deterministic yet hard to predict—are acceptable.
No Pseudo in Crypto! | |
|---|---|
 | Never use pseudo-random numbers for cryptography or computer and Internet security tasks because they are deterministic. For example, if a web app uses a PRNG for password-reset tokens, an attacker who can observe a few tokens may predict the next token and take over accounts. |
Python provides the random module, which is based on the pseudo-random Mersenne Twister algorithm. Among other functions, the module includes randint and random for generating integer and floating-point numbers in the ranges [a, b] and [0, 1), respectively:
| | >>> import random |
| | >>> random.randint(0,55) |
| | 35 |
| | >>> random.randint(0,55) |
| | 48 |
| | >>> random.randint(0,55) |
| | 39 |
| | >>> random.random() |
| | 0.38402282929624554 |
| | >>> random.random() |
| | 0.0033172813689996694 |
| | >>> random.random() |
| | 0.7797058697769986 |
As an alternative, let’s write a linear congruential generator (LCG), one of the oldest and simplest PRNG algorithms. The algorithm starts with a seed number x0 and computes the next value using a piecewise-linear function: xn+1 = (A * xn + C) % M. The numbers A, C, and M are fixed parameters; their choice is outside this book’s scope. The implementation of the generator function is trivial:
| | from collections.abc import Iterator |
| | def make_lcg(seed: int) -> Iterator[int]: |
| | """ Yield a pseudo random number from 0 to M - 1 (inclusive). |
| | |
| | >>> next(make_lcg(0)) |
| | 52 |
| | """ |
| | |
| | # Define generator parameters |
| | A, C, M = 83, 52, 101 |
| | |
| | # Initialize the initial state (cannot be 24) |
| | if seed != 24: |
| | state = seed |
| | else: |
| | state = seed + 1 |
| | |
| | # Yield PRNs |
| | while True: |
| | state = (A * state + C) % M |
| | yield state |
Note that the choice of seed is not completely unrestricted: depending on A, C, and M, some seeds can lead to a degenerate sequence (producing the same value repeatedly).
You can test the generator with different seeds inferred from the current time in seconds (computed by time.time from the namesake module):
| | import time |
| | |
| | lcg = make_lcg(int(time.time())) |
| | print(next(lcg)) # 96 |
| | print(next(lcg)) # 41 |
| | print(next(lcg)) # 21 |
| | print(next(lcg)) # 78 |
| | print(next(lcg)) # 62 |
The results look random enough!
