| 1 |
.. _functional-howto: |
| 2 |
|
| 3 |
******************************** |
| 4 |
Functional Programming HOWTO |
| 5 |
******************************** |
| 6 |
|
| 7 |
:Author: \A. M. Kuchling |
| 8 |
:Release: 0.32 |
| 9 |
|
| 10 |
In this document, we'll take a tour of Python's features suitable for |
| 11 |
implementing programs in a functional style. After an introduction to the |
| 12 |
concepts of functional programming, we'll look at language features such as |
| 13 |
:term:`iterator`\s and :term:`generator`\s and relevant library modules such as |
| 14 |
:mod:`itertools` and :mod:`functools`. |
| 15 |
|
| 16 |
|
| 17 |
Introduction |
| 18 |
============ |
| 19 |
|
| 20 |
This section explains the basic concept of functional programming; if |
| 21 |
you're just interested in learning about Python language features, |
| 22 |
skip to the next section on :ref:`functional-howto-iterators`. |
| 23 |
|
| 24 |
Programming languages support decomposing problems in several different ways: |
| 25 |
|
| 26 |
* Most programming languages are **procedural**: programs are lists of |
| 27 |
instructions that tell the computer what to do with the program's input. C, |
| 28 |
Pascal, and even Unix shells are procedural languages. |
| 29 |
|
| 30 |
* In **declarative** languages, you write a specification that describes the |
| 31 |
problem to be solved, and the language implementation figures out how to |
| 32 |
perform the computation efficiently. SQL is the declarative language you're |
| 33 |
most likely to be familiar with; a SQL query describes the data set you want |
| 34 |
to retrieve, and the SQL engine decides whether to scan tables or use indexes, |
| 35 |
which subclauses should be performed first, etc. |
| 36 |
|
| 37 |
* **Object-oriented** programs manipulate collections of objects. Objects have |
| 38 |
internal state and support methods that query or modify this internal state in |
| 39 |
some way. Smalltalk and Java are object-oriented languages. C++ and Python |
| 40 |
are languages that support object-oriented programming, but don't force the |
| 41 |
use of object-oriented features. |
| 42 |
|
| 43 |
* **Functional** programming decomposes a problem into a set of functions. |
| 44 |
Ideally, functions only take inputs and produce outputs, and don't have any |
| 45 |
internal state that affects the output produced for a given input. Well-known |
| 46 |
functional languages include the ML family (Standard ML, OCaml, and other |
| 47 |
variants) and Haskell. |
| 48 |
|
| 49 |
The designers of some computer languages choose to emphasize one |
| 50 |
particular approach to programming. This often makes it difficult to |
| 51 |
write programs that use a different approach. Other languages are |
| 52 |
multi-paradigm languages that support several different approaches. |
| 53 |
Lisp, C++, and Python are multi-paradigm; you can write programs or |
| 54 |
libraries that are largely procedural, object-oriented, or functional |
| 55 |
in all of these languages. In a large program, different sections |
| 56 |
might be written using different approaches; the GUI might be |
| 57 |
object-oriented while the processing logic is procedural or |
| 58 |
functional, for example. |
| 59 |
|
| 60 |
In a functional program, input flows through a set of functions. Each function |
| 61 |
operates on its input and produces some output. Functional style discourages |
| 62 |
functions with side effects that modify internal state or make other changes |
| 63 |
that aren't visible in the function's return value. Functions that have no side |
| 64 |
effects at all are called **purely functional**. Avoiding side effects means |
| 65 |
not using data structures that get updated as a program runs; every function's |
| 66 |
output must only depend on its input. |
| 67 |
|
| 68 |
Some languages are very strict about purity and don't even have assignment |
| 69 |
statements such as ``a=3`` or ``c = a + b``, but it's difficult to avoid all |
| 70 |
side effects, such as printing to the screen or writing to a disk file. Another |
| 71 |
example is a call to the :func:`print` or :func:`time.sleep` function, neither |
| 72 |
of which returns a useful value. Both are called only for their side effects |
| 73 |
of sending some text to the screen or pausing execution for a second. |
| 74 |
|
| 75 |
Python programs written in functional style usually won't go to the extreme of |
| 76 |
avoiding all I/O or all assignments; instead, they'll provide a |
| 77 |
functional-appearing interface but will use non-functional features internally. |
| 78 |
For example, the implementation of a function will still use assignments to |
| 79 |
local variables, but won't modify global variables or have other side effects. |
| 80 |
|
| 81 |
Functional programming can be considered the opposite of object-oriented |
| 82 |
programming. Objects are little capsules containing some internal state along |
| 83 |
with a collection of method calls that let you modify this state, and programs |
| 84 |
consist of making the right set of state changes. Functional programming wants |
| 85 |
to avoid state changes as much as possible and works with data flowing between |
| 86 |
functions. In Python you might combine the two approaches by writing functions |
| 87 |
that take and return instances representing objects in your application (e-mail |
| 88 |
messages, transactions, etc.). |
| 89 |
|
| 90 |
Functional design may seem like an odd constraint to work under. Why should you |
| 91 |
avoid objects and side effects? There are theoretical and practical advantages |
| 92 |
to the functional style: |
| 93 |
|
| 94 |
* Formal provability. |
| 95 |
* Modularity. |
| 96 |
* Composability. |
| 97 |
* Ease of debugging and testing. |
| 98 |
|
| 99 |
|
| 100 |
Formal provability |
| 101 |
------------------ |
| 102 |
|
| 103 |
A theoretical benefit is that it's easier to construct a mathematical proof that |
| 104 |
a functional program is correct. |
| 105 |
|
| 106 |
For a long time researchers have been interested in finding ways to |
| 107 |
mathematically prove programs correct. This is different from testing a program |
| 108 |
on numerous inputs and concluding that its output is usually correct, or reading |
| 109 |
a program's source code and concluding that the code looks right; the goal is |
| 110 |
instead a rigorous proof that a program produces the right result for all |
| 111 |
possible inputs. |
| 112 |
|
| 113 |
The technique used to prove programs correct is to write down **invariants**, |
| 114 |
properties of the input data and of the program's variables that are always |
| 115 |
true. For each line of code, you then show that if invariants X and Y are true |
| 116 |
**before** the line is executed, the slightly different invariants X' and Y' are |
| 117 |
true **after** the line is executed. This continues until you reach the end of |
| 118 |
the program, at which point the invariants should match the desired conditions |
| 119 |
on the program's output. |
| 120 |
|
| 121 |
Functional programming's avoidance of assignments arose because assignments are |
| 122 |
difficult to handle with this technique; assignments can break invariants that |
| 123 |
were true before the assignment without producing any new invariants that can be |
| 124 |
propagated onward. |
| 125 |
|
| 126 |
Unfortunately, proving programs correct is largely impractical and not relevant |
| 127 |
to Python software. Even trivial programs require proofs that are several pages |
| 128 |
long; the proof of correctness for a moderately complicated program would be |
| 129 |
enormous, and few or none of the programs you use daily (the Python interpreter, |
| 130 |
your XML parser, your web browser) could be proven correct. Even if you wrote |
| 131 |
down or generated a proof, there would then be the question of verifying the |
| 132 |
proof; maybe there's an error in it, and you wrongly believe you've proved the |
| 133 |
program correct. |
| 134 |
|
| 135 |
|
| 136 |
Modularity |
| 137 |
---------- |
| 138 |
|
| 139 |
A more practical benefit of functional programming is that it forces you to |
| 140 |
break apart your problem into small pieces. Programs are more modular as a |
| 141 |
result. It's easier to specify and write a small function that does one thing |
| 142 |
than a large function that performs a complicated transformation. Small |
| 143 |
functions are also easier to read and to check for errors. |
| 144 |
|
| 145 |
|
| 146 |
Ease of debugging and testing |
| 147 |
----------------------------- |
| 148 |
|
| 149 |
Testing and debugging a functional-style program is easier. |
| 150 |
|
| 151 |
Debugging is simplified because functions are generally small and clearly |
| 152 |
specified. When a program doesn't work, each function is an interface point |
| 153 |
where you can check that the data are correct. You can look at the intermediate |
| 154 |
inputs and outputs to quickly isolate the function that's responsible for a bug. |
| 155 |
|
| 156 |
Testing is easier because each function is a potential subject for a unit test. |
| 157 |
Functions don't depend on system state that needs to be replicated before |
| 158 |
running a test; instead you only have to synthesize the right input and then |
| 159 |
check that the output matches expectations. |
| 160 |
|
| 161 |
|
| 162 |
Composability |
| 163 |
------------- |
| 164 |
|
| 165 |
As you work on a functional-style program, you'll write a number of functions |
| 166 |
with varying inputs and outputs. Some of these functions will be unavoidably |
| 167 |
specialized to a particular application, but others will be useful in a wide |
| 168 |
variety of programs. For example, a function that takes a directory path and |
| 169 |
returns all the XML files in the directory, or a function that takes a filename |
| 170 |
and returns its contents, can be applied to many different situations. |
| 171 |
|
| 172 |
Over time you'll form a personal library of utilities. Often you'll assemble |
| 173 |
new programs by arranging existing functions in a new configuration and writing |
| 174 |
a few functions specialized for the current task. |
| 175 |
|
| 176 |
|
| 177 |
.. _functional-howto-iterators: |
| 178 |
|
| 179 |
Iterators |
| 180 |
========= |
| 181 |
|
| 182 |
I'll start by looking at a Python language feature that's an important |
| 183 |
foundation for writing functional-style programs: iterators. |
| 184 |
|
| 185 |
An iterator is an object representing a stream of data; this object returns the |
| 186 |
data one element at a time. A Python iterator must support a method called |
| 187 |
:meth:`~iterator.__next__` that takes no arguments and always returns the next |
| 188 |
element of the stream. If there are no more elements in the stream, |
| 189 |
:meth:`~iterator.__next__` must raise the :exc:`StopIteration` exception. |
| 190 |
Iterators don't have to be finite, though; it's perfectly reasonable to write |
| 191 |
an iterator that produces an infinite stream of data. |
| 192 |
|
| 193 |
The built-in :func:`iter` function takes an arbitrary object and tries to return |
| 194 |
an iterator that will return the object's contents or elements, raising |
| 195 |
:exc:`TypeError` if the object doesn't support iteration. Several of Python's |
| 196 |
built-in data types support iteration, the most common being lists and |
| 197 |
dictionaries. An object is called :term:`iterable` if you can get an iterator |
| 198 |
for it. |
| 199 |
|
| 200 |
You can experiment with the iteration interface manually: |
| 201 |
|
| 202 |
>>> L = [1, 2, 3] |
| 203 |
>>> it = iter(L) |
| 204 |
>>> it #doctest: +ELLIPSIS |
| 205 |
<...iterator object at ...> |
| 206 |
>>> it.__next__() # same as next(it) |
| 207 |
1 |
| 208 |
>>> next(it) |
| 209 |
2 |
| 210 |
>>> next(it) |
| 211 |
3 |
| 212 |
>>> next(it) |
| 213 |
Traceback (most recent call last): |
| 214 |
File "<stdin>", line 1, in <module> |
| 215 |
StopIteration |
| 216 |
>>> |
| 217 |
|
| 218 |
Python expects iterable objects in several different contexts, the most |
| 219 |
important being the :keyword:`for` statement. In the statement ``for X in Y``, |
| 220 |
Y must be an iterator or some object for which :func:`iter` can create an |
| 221 |
iterator. These two statements are equivalent:: |
| 222 |
|
| 223 |
|
| 224 |
for i in iter(obj): |
| 225 |
print(i) |
| 226 |
|
| 227 |
for i in obj: |
| 228 |
print(i) |
| 229 |
|
| 230 |
Iterators can be materialized as lists or tuples by using the :func:`list` or |
| 231 |
:func:`tuple` constructor functions: |
| 232 |
|
| 233 |
>>> L = [1, 2, 3] |
| 234 |
>>> iterator = iter(L) |
| 235 |
>>> t = tuple(iterator) |
| 236 |
>>> t |
| 237 |
(1, 2, 3) |
| 238 |
|
| 239 |
Sequence unpacking also supports iterators: if you know an iterator will return |
| 240 |
N elements, you can unpack them into an N-tuple: |
| 241 |
|
| 242 |
>>> L = [1, 2, 3] |
| 243 |
>>> iterator = iter(L) |
| 244 |
>>> a, b, c = iterator |
| 245 |
>>> a, b, c |
| 246 |
(1, 2, 3) |
| 247 |
|
| 248 |
Built-in functions such as :func:`max` and :func:`min` can take a single |
| 249 |
iterator argument and will return the largest or smallest element. The ``"in"`` |
| 250 |
and ``"not in"`` operators also support iterators: ``X in iterator`` is true if |
| 251 |
X is found in the stream returned by the iterator. You'll run into obvious |
| 252 |
problems if the iterator is infinite; :func:`max`, :func:`min` |
| 253 |
will never return, and if the element X never appears in the stream, the |
| 254 |
``"in"`` and ``"not in"`` operators won't return either. |
| 255 |
|
| 256 |
Note that you can only go forward in an iterator; there's no way to get the |
| 257 |
previous element, reset the iterator, or make a copy of it. Iterator objects |
| 258 |
can optionally provide these additional capabilities, but the iterator protocol |
| 259 |
only specifies the :meth:`~iterator.__next__` method. Functions may therefore |
| 260 |
consume all of the iterator's output, and if you need to do something different |
| 261 |
with the same stream, you'll have to create a new iterator. |
| 262 |
|
| 263 |
|
| 264 |
|
| 265 |
Data Types That Support Iterators |
| 266 |
--------------------------------- |
| 267 |
|
| 268 |
We've already seen how lists and tuples support iterators. In fact, any Python |
| 269 |
sequence type, such as strings, will automatically support creation of an |
| 270 |
iterator. |
| 271 |
|
| 272 |
Calling :func:`iter` on a dictionary returns an iterator that will loop over the |
| 273 |
dictionary's keys:: |
| 274 |
|
| 275 |
>>> m = {'Jan': 1, 'Feb': 2, 'Mar': 3, 'Apr': 4, 'May': 5, 'Jun': 6, |
| 276 |
... 'Jul': 7, 'Aug': 8, 'Sep': 9, 'Oct': 10, 'Nov': 11, 'Dec': 12} |
| 277 |
>>> for key in m: |
| 278 |
... print(key, m[key]) |
| 279 |
Jan 1 |
| 280 |
Feb 2 |
| 281 |
Mar 3 |
| 282 |
Apr 4 |
| 283 |
May 5 |
| 284 |
Jun 6 |
| 285 |
Jul 7 |
| 286 |
Aug 8 |
| 287 |
Sep 9 |
| 288 |
Oct 10 |
| 289 |
Nov 11 |
| 290 |
Dec 12 |
| 291 |
|
| 292 |
Note that starting with Python 3.7, dictionary iteration order is guaranteed |
| 293 |
to be the same as the insertion order. In earlier versions, the behaviour was |
| 294 |
unspecified and could vary between implementations. |
| 295 |
|
| 296 |
Applying :func:`iter` to a dictionary always loops over the keys, but |
| 297 |
dictionaries have methods that return other iterators. If you want to iterate |
| 298 |
over values or key/value pairs, you can explicitly call the |
| 299 |
:meth:`~dict.values` or :meth:`~dict.items` methods to get an appropriate |
| 300 |
iterator. |
| 301 |
|
| 302 |
The :func:`dict` constructor can accept an iterator that returns a finite stream |
| 303 |
of ``(key, value)`` tuples: |
| 304 |
|
| 305 |
>>> L = [('Italy', 'Rome'), ('France', 'Paris'), ('US', 'Washington DC')] |
| 306 |
>>> dict(iter(L)) |
| 307 |
{'Italy': 'Rome', 'France': 'Paris', 'US': 'Washington DC'} |
| 308 |
|
| 309 |
Files also support iteration by calling the :meth:`~io.TextIOBase.readline` |
| 310 |
method until there are no more lines in the file. This means you can read each |
| 311 |
line of a file like this:: |
| 312 |
|
| 313 |
for line in file: |
| 314 |
# do something for each line |
| 315 |
... |
| 316 |
|
| 317 |
Sets can take their contents from an iterable and let you iterate over the set's |
| 318 |
elements:: |
| 319 |
|
| 320 |
>>> S = {2, 3, 5, 7, 11, 13} |
| 321 |
>>> for i in S: |
| 322 |
... print(i) |
| 323 |
2 |
| 324 |
3 |
| 325 |
5 |
| 326 |
7 |
| 327 |
11 |
| 328 |
13 |
| 329 |
|
| 330 |
|
| 331 |
|
| 332 |
Generator expressions and list comprehensions |
| 333 |
============================================= |
| 334 |
|
| 335 |
Two common operations on an iterator's output are 1) performing some operation |
| 336 |
for every element, 2) selecting a subset of elements that meet some condition. |
| 337 |
For example, given a list of strings, you might want to strip off trailing |
| 338 |
whitespace from each line or extract all the strings containing a given |
| 339 |
substring. |
| 340 |
|
| 341 |
List comprehensions and generator expressions (short form: "listcomps" and |
| 342 |
"genexps") are a concise notation for such operations, borrowed from the |
| 343 |
functional programming language Haskell (https://www.haskell.org/). You can strip |
| 344 |
all the whitespace from a stream of strings with the following code:: |
| 345 |
|
| 346 |
>>> line_list = [' line 1\n', 'line 2 \n', ' \n', ''] |
| 347 |
|
| 348 |
>>> # Generator expression -- returns iterator |
| 349 |
>>> stripped_iter = (line.strip() for line in line_list) |
| 350 |
|
| 351 |
>>> # List comprehension -- returns list |
| 352 |
>>> stripped_list = [line.strip() for line in line_list] |
| 353 |
|
| 354 |
You can select only certain elements by adding an ``"if"`` condition:: |
| 355 |
|
| 356 |
>>> stripped_list = [line.strip() for line in line_list |
| 357 |
... if line != ""] |
| 358 |
|
| 359 |
With a list comprehension, you get back a Python list; ``stripped_list`` is a |
| 360 |
list containing the resulting lines, not an iterator. Generator expressions |
| 361 |
return an iterator that computes the values as necessary, not needing to |
| 362 |
materialize all the values at once. This means that list comprehensions aren't |
| 363 |
useful if you're working with iterators that return an infinite stream or a very |
| 364 |
large amount of data. Generator expressions are preferable in these situations. |
| 365 |
|
| 366 |
Generator expressions are surrounded by parentheses ("()") and list |
| 367 |
comprehensions are surrounded by square brackets ("[]"). Generator expressions |
| 368 |
have the form:: |
| 369 |
|
| 370 |
( expression for expr in sequence1 |
| 371 |
if condition1 |
| 372 |
for expr2 in sequence2 |
| 373 |
if condition2 |
| 374 |
for expr3 in sequence3 |
| 375 |
... |
| 376 |
if condition3 |
| 377 |
for exprN in sequenceN |
| 378 |
if conditionN ) |
| 379 |
|
| 380 |
Again, for a list comprehension only the outside brackets are different (square |
| 381 |
brackets instead of parentheses). |
| 382 |
|
| 383 |
The elements of the generated output will be the successive values of |
| 384 |
``expression``. The ``if`` clauses are all optional; if present, ``expression`` |
| 385 |
is only evaluated and added to the result when ``condition`` is true. |
| 386 |
|
| 387 |
Generator expressions always have to be written inside parentheses, but the |
| 388 |
parentheses signalling a function call also count. If you want to create an |
| 389 |
iterator that will be immediately passed to a function you can write:: |
| 390 |
|
| 391 |
obj_total = sum(obj.count for obj in list_all_objects()) |
| 392 |
|
| 393 |
The ``for...in`` clauses contain the sequences to be iterated over. The |
| 394 |
sequences do not have to be the same length, because they are iterated over from |
| 395 |
left to right, **not** in parallel. For each element in ``sequence1``, |
| 396 |
``sequence2`` is looped over from the beginning. ``sequence3`` is then looped |
| 397 |
over for each resulting pair of elements from ``sequence1`` and ``sequence2``. |
| 398 |
|
| 399 |
To put it another way, a list comprehension or generator expression is |
| 400 |
equivalent to the following Python code:: |
| 401 |
|
| 402 |
for expr1 in sequence1: |
| 403 |
if not (condition1): |
| 404 |
continue # Skip this element |
| 405 |
for expr2 in sequence2: |
| 406 |
if not (condition2): |
| 407 |
continue # Skip this element |
| 408 |
... |
| 409 |
for exprN in sequenceN: |
| 410 |
if not (conditionN): |
| 411 |
continue # Skip this element |
| 412 |
|
| 413 |
# Output the value of |
| 414 |
# the expression. |
| 415 |
|
| 416 |
This means that when there are multiple ``for...in`` clauses but no ``if`` |
| 417 |
clauses, the length of the resulting output will be equal to the product of the |
| 418 |
lengths of all the sequences. If you have two lists of length 3, the output |
| 419 |
list is 9 elements long: |
| 420 |
|
| 421 |
>>> seq1 = 'abc' |
| 422 |
>>> seq2 = (1, 2, 3) |
| 423 |
>>> [(x, y) for x in seq1 for y in seq2] #doctest: +NORMALIZE_WHITESPACE |
| 424 |
[('a', 1), ('a', 2), ('a', 3), |
| 425 |
('b', 1), ('b', 2), ('b', 3), |
| 426 |
('c', 1), ('c', 2), ('c', 3)] |
| 427 |
|
| 428 |
To avoid introducing an ambiguity into Python's grammar, if ``expression`` is |
| 429 |
creating a tuple, it must be surrounded with parentheses. The first list |
| 430 |
comprehension below is a syntax error, while the second one is correct:: |
| 431 |
|
| 432 |
# Syntax error |
| 433 |
[x, y for x in seq1 for y in seq2] |
| 434 |
# Correct |
| 435 |
[(x, y) for x in seq1 for y in seq2] |
| 436 |
|
| 437 |
|
| 438 |
Generators |
| 439 |
========== |
| 440 |
|
| 441 |
Generators are a special class of functions that simplify the task of writing |
| 442 |
iterators. Regular functions compute a value and return it, but generators |
| 443 |
return an iterator that returns a stream of values. |
| 444 |
|
| 445 |
You're doubtless familiar with how regular function calls work in Python or C. |
| 446 |
When you call a function, it gets a private namespace where its local variables |
| 447 |
are created. When the function reaches a ``return`` statement, the local |
| 448 |
variables are destroyed and the value is returned to the caller. A later call |
| 449 |
to the same function creates a new private namespace and a fresh set of local |
| 450 |
variables. But, what if the local variables weren't thrown away on exiting a |
| 451 |
function? What if you could later resume the function where it left off? This |
| 452 |
is what generators provide; they can be thought of as resumable functions. |
| 453 |
|
| 454 |
Here's the simplest example of a generator function: |
| 455 |
|
| 456 |
>>> def generate_ints(N): |
| 457 |
... for i in range(N): |
| 458 |
... yield i |
| 459 |
|
| 460 |
Any function containing a :keyword:`yield` keyword is a generator function; |
| 461 |
this is detected by Python's :term:`bytecode` compiler which compiles the |
| 462 |
function specially as a result. |
| 463 |
|
| 464 |
When you call a generator function, it doesn't return a single value; instead it |
| 465 |
returns a generator object that supports the iterator protocol. On executing |
| 466 |
the ``yield`` expression, the generator outputs the value of ``i``, similar to a |
| 467 |
``return`` statement. The big difference between ``yield`` and a ``return`` |
| 468 |
statement is that on reaching a ``yield`` the generator's state of execution is |
| 469 |
suspended and local variables are preserved. On the next call to the |
| 470 |
generator's :meth:`~generator.__next__` method, the function will resume |
| 471 |
executing. |
| 472 |
|
| 473 |
Here's a sample usage of the ``generate_ints()`` generator: |
| 474 |
|
| 475 |
>>> gen = generate_ints(3) |
| 476 |
>>> gen #doctest: +ELLIPSIS |
| 477 |
<generator object generate_ints at ...> |
| 478 |
>>> next(gen) |
| 479 |
0 |
| 480 |
>>> next(gen) |
| 481 |
1 |
| 482 |
>>> next(gen) |
| 483 |
2 |
| 484 |
>>> next(gen) |
| 485 |
Traceback (most recent call last): |
| 486 |
File "stdin", line 1, in <module> |
| 487 |
File "stdin", line 2, in generate_ints |
| 488 |
StopIteration |
| 489 |
|
| 490 |
You could equally write ``for i in generate_ints(5)``, or ``a, b, c = |
| 491 |
generate_ints(3)``. |
| 492 |
|
| 493 |
Inside a generator function, ``return value`` causes ``StopIteration(value)`` |
| 494 |
to be raised from the :meth:`~generator.__next__` method. Once this happens, or |
| 495 |
the bottom of the function is reached, the procession of values ends and the |
| 496 |
generator cannot yield any further values. |
| 497 |
|
| 498 |
You could achieve the effect of generators manually by writing your own class |
| 499 |
and storing all the local variables of the generator as instance variables. For |
| 500 |
example, returning a list of integers could be done by setting ``self.count`` to |
| 501 |
0, and having the :meth:`~iterator.__next__` method increment ``self.count`` and |
| 502 |
return it. |
| 503 |
However, for a moderately complicated generator, writing a corresponding class |
| 504 |
can be much messier. |
| 505 |
|
| 506 |
The test suite included with Python's library, |
| 507 |
:source:`Lib/test/test_generators.py`, contains |
| 508 |
a number of more interesting examples. Here's one generator that implements an |
| 509 |
in-order traversal of a tree using generators recursively. :: |
| 510 |
|
| 511 |
# A recursive generator that generates Tree leaves in in-order. |
| 512 |
def inorder(t): |
| 513 |
if t: |
| 514 |
for x in inorder(t.left): |
| 515 |
yield x |
| 516 |
|
| 517 |
yield t.label |
| 518 |
|
| 519 |
for x in inorder(t.right): |
| 520 |
yield x |
| 521 |
|
| 522 |
Two other examples in ``test_generators.py`` produce solutions for the N-Queens |
| 523 |
problem (placing N queens on an NxN chess board so that no queen threatens |
| 524 |
another) and the Knight's Tour (finding a route that takes a knight to every |
| 525 |
square of an NxN chessboard without visiting any square twice). |
| 526 |
|
| 527 |
|
| 528 |
|
| 529 |
Passing values into a generator |
| 530 |
------------------------------- |
| 531 |
|
| 532 |
In Python 2.4 and earlier, generators only produced output. Once a generator's |
| 533 |
code was invoked to create an iterator, there was no way to pass any new |
| 534 |
information into the function when its execution is resumed. You could hack |
| 535 |
together this ability by making the generator look at a global variable or by |
| 536 |
passing in some mutable object that callers then modify, but these approaches |
| 537 |
are messy. |
| 538 |
|
| 539 |
In Python 2.5 there's a simple way to pass values into a generator. |
| 540 |
:keyword:`yield` became an expression, returning a value that can be assigned to |
| 541 |
a variable or otherwise operated on:: |
| 542 |
|
| 543 |
val = (yield i) |
| 544 |
|
| 545 |
I recommend that you **always** put parentheses around a ``yield`` expression |
| 546 |
when you're doing something with the returned value, as in the above example. |
| 547 |
The parentheses aren't always necessary, but it's easier to always add them |
| 548 |
instead of having to remember when they're needed. |
| 549 |
|
| 550 |
(:pep:`342` explains the exact rules, which are that a ``yield``-expression must |
| 551 |
always be parenthesized except when it occurs at the top-level expression on the |
| 552 |
right-hand side of an assignment. This means you can write ``val = yield i`` |
| 553 |
but have to use parentheses when there's an operation, as in ``val = (yield i) |
| 554 |
+ 12``.) |
| 555 |
|
| 556 |
Values are sent into a generator by calling its :meth:`send(value) |
| 557 |
<generator.send>` method. This method resumes the generator's code and the |
| 558 |
``yield`` expression returns the specified value. If the regular |
| 559 |
:meth:`~generator.__next__` method is called, the ``yield`` returns ``None``. |
| 560 |
|
| 561 |
Here's a simple counter that increments by 1 and allows changing the value of |
| 562 |
the internal counter. |
| 563 |
|
| 564 |
.. testcode:: |
| 565 |
|
| 566 |
def counter(maximum): |
| 567 |
i = 0 |
| 568 |
while i < maximum: |
| 569 |
val = (yield i) |
| 570 |
# If value provided, change counter |
| 571 |
if val is not None: |
| 572 |
i = val |
| 573 |
else: |
| 574 |
i += 1 |
| 575 |
|
| 576 |
And here's an example of changing the counter: |
| 577 |
|
| 578 |
>>> it = counter(10) #doctest: +SKIP |
| 579 |
>>> next(it) #doctest: +SKIP |
| 580 |
0 |
| 581 |
>>> next(it) #doctest: +SKIP |
| 582 |
1 |
| 583 |
>>> it.send(8) #doctest: +SKIP |
| 584 |
8 |
| 585 |
>>> next(it) #doctest: +SKIP |
| 586 |
9 |
| 587 |
>>> next(it) #doctest: +SKIP |
| 588 |
Traceback (most recent call last): |
| 589 |
File "t.py", line 15, in <module> |
| 590 |
it.next() |
| 591 |
StopIteration |
| 592 |
|
| 593 |
Because ``yield`` will often be returning ``None``, you should always check for |
| 594 |
this case. Don't just use its value in expressions unless you're sure that the |
| 595 |
:meth:`~generator.send` method will be the only method used to resume your |
| 596 |
generator function. |
| 597 |
|
| 598 |
In addition to :meth:`~generator.send`, there are two other methods on |
| 599 |
generators: |
| 600 |
|
| 601 |
* :meth:`throw(value) <generator.throw>` is used to |
| 602 |
raise an exception inside the generator; the exception is raised by the |
| 603 |
``yield`` expression where the generator's execution is paused. |
| 604 |
|
| 605 |
* :meth:`~generator.close` sends a :exc:`GeneratorExit` exception to the |
| 606 |
generator to terminate the iteration. On receiving this exception, the |
| 607 |
generator's code must either raise :exc:`GeneratorExit` or |
| 608 |
:exc:`StopIteration`; catching the exception and doing anything else is |
| 609 |
illegal and will trigger a :exc:`RuntimeError`. :meth:`~generator.close` |
| 610 |
will also be called by Python's garbage collector when the generator is |
| 611 |
garbage-collected. |
| 612 |
|
| 613 |
If you need to run cleanup code when a :exc:`GeneratorExit` occurs, I suggest |
| 614 |
using a ``try: ... finally:`` suite instead of catching :exc:`GeneratorExit`. |
| 615 |
|
| 616 |
The cumulative effect of these changes is to turn generators from one-way |
| 617 |
producers of information into both producers and consumers. |
| 618 |
|
| 619 |
Generators also become **coroutines**, a more generalized form of subroutines. |
| 620 |
Subroutines are entered at one point and exited at another point (the top of the |
| 621 |
function, and a ``return`` statement), but coroutines can be entered, exited, |
| 622 |
and resumed at many different points (the ``yield`` statements). |
| 623 |
|
| 624 |
|
| 625 |
Built-in functions |
| 626 |
================== |
| 627 |
|
| 628 |
Let's look in more detail at built-in functions often used with iterators. |
| 629 |
|
| 630 |
Two of Python's built-in functions, :func:`map` and :func:`filter` duplicate the |
| 631 |
features of generator expressions: |
| 632 |
|
| 633 |
:func:`map(f, iterA, iterB, ...) <map>` returns an iterator over the sequence |
| 634 |
``f(iterA[0], iterB[0]), f(iterA[1], iterB[1]), f(iterA[2], iterB[2]), ...``. |
| 635 |
|
| 636 |
>>> def upper(s): |
| 637 |
... return s.upper() |
| 638 |
|
| 639 |
>>> list(map(upper, ['sentence', 'fragment'])) |
| 640 |
['SENTENCE', 'FRAGMENT'] |
| 641 |
>>> [upper(s) for s in ['sentence', 'fragment']] |
| 642 |
['SENTENCE', 'FRAGMENT'] |
| 643 |
|
| 644 |
You can of course achieve the same effect with a list comprehension. |
| 645 |
|
| 646 |
:func:`filter(predicate, iter) <filter>` returns an iterator over all the |
| 647 |
sequence elements that meet a certain condition, and is similarly duplicated by |
| 648 |
list comprehensions. A **predicate** is a function that returns the truth |
| 649 |
value of some condition; for use with :func:`filter`, the predicate must take a |
| 650 |
single value. |
| 651 |
|
| 652 |
>>> def is_even(x): |
| 653 |
... return (x % 2) == 0 |
| 654 |
|
| 655 |
>>> list(filter(is_even, range(10))) |
| 656 |
[0, 2, 4, 6, 8] |
| 657 |
|
| 658 |
|
| 659 |
This can also be written as a list comprehension: |
| 660 |
|
| 661 |
>>> list(x for x in range(10) if is_even(x)) |
| 662 |
[0, 2, 4, 6, 8] |
| 663 |
|
| 664 |
|
| 665 |
:func:`enumerate(iter, start=0) <enumerate>` counts off the elements in the |
| 666 |
iterable returning 2-tuples containing the count (from *start*) and |
| 667 |
each element. :: |
| 668 |
|
| 669 |
>>> for item in enumerate(['subject', 'verb', 'object']): |
| 670 |
... print(item) |
| 671 |
(0, 'subject') |
| 672 |
(1, 'verb') |
| 673 |
(2, 'object') |
| 674 |
|
| 675 |
:func:`enumerate` is often used when looping through a list and recording the |
| 676 |
indexes at which certain conditions are met:: |
| 677 |
|
| 678 |
f = open('data.txt', 'r') |
| 679 |
for i, line in enumerate(f): |
| 680 |
if line.strip() == '': |
| 681 |
print('Blank line at line #%i' % i) |
| 682 |
|
| 683 |
:func:`sorted(iterable, key=None, reverse=False) <sorted>` collects all the |
| 684 |
elements of the iterable into a list, sorts the list, and returns the sorted |
| 685 |
result. The *key* and *reverse* arguments are passed through to the |
| 686 |
constructed list's :meth:`~list.sort` method. :: |
| 687 |
|
| 688 |
>>> import random |
| 689 |
>>> # Generate 8 random numbers between [0, 10000) |
| 690 |
>>> rand_list = random.sample(range(10000), 8) |
| 691 |
>>> rand_list #doctest: +SKIP |
| 692 |
[769, 7953, 9828, 6431, 8442, 9878, 6213, 2207] |
| 693 |
>>> sorted(rand_list) #doctest: +SKIP |
| 694 |
[769, 2207, 6213, 6431, 7953, 8442, 9828, 9878] |
| 695 |
>>> sorted(rand_list, reverse=True) #doctest: +SKIP |
| 696 |
[9878, 9828, 8442, 7953, 6431, 6213, 2207, 769] |
| 697 |
|
| 698 |
(For a more detailed discussion of sorting, see the :ref:`sortinghowto`.) |
| 699 |
|
| 700 |
|
| 701 |
The :func:`any(iter) <any>` and :func:`all(iter) <all>` built-ins look at the |
| 702 |
truth values of an iterable's contents. :func:`any` returns ``True`` if any element |
| 703 |
in the iterable is a true value, and :func:`all` returns ``True`` if all of the |
| 704 |
elements are true values: |
| 705 |
|
| 706 |
>>> any([0, 1, 0]) |
| 707 |
True |
| 708 |
>>> any([0, 0, 0]) |
| 709 |
False |
| 710 |
>>> any([1, 1, 1]) |
| 711 |
True |
| 712 |
>>> all([0, 1, 0]) |
| 713 |
False |
| 714 |
>>> all([0, 0, 0]) |
| 715 |
False |
| 716 |
>>> all([1, 1, 1]) |
| 717 |
True |
| 718 |
|
| 719 |
|
| 720 |
:func:`zip(iterA, iterB, ...) <zip>` takes one element from each iterable and |
| 721 |
returns them in a tuple:: |
| 722 |
|
| 723 |
zip(['a', 'b', 'c'], (1, 2, 3)) => |
| 724 |
('a', 1), ('b', 2), ('c', 3) |
| 725 |
|
| 726 |
It doesn't construct an in-memory list and exhaust all the input iterators |
| 727 |
before returning; instead tuples are constructed and returned only if they're |
| 728 |
requested. (The technical term for this behaviour is `lazy evaluation |
| 729 |
<https://en.wikipedia.org/wiki/Lazy_evaluation>`__.) |
| 730 |
|
| 731 |
This iterator is intended to be used with iterables that are all of the same |
| 732 |
length. If the iterables are of different lengths, the resulting stream will be |
| 733 |
the same length as the shortest iterable. :: |
| 734 |
|
| 735 |
zip(['a', 'b'], (1, 2, 3)) => |
| 736 |
('a', 1), ('b', 2) |
| 737 |
|
| 738 |
You should avoid doing this, though, because an element may be taken from the |
| 739 |
longer iterators and discarded. This means you can't go on to use the iterators |
| 740 |
further because you risk skipping a discarded element. |
| 741 |
|
| 742 |
|
| 743 |
The itertools module |
| 744 |
==================== |
| 745 |
|
| 746 |
The :mod:`itertools` module contains a number of commonly used iterators as well |
| 747 |
as functions for combining several iterators. This section will introduce the |
| 748 |
module's contents by showing small examples. |
| 749 |
|
| 750 |
The module's functions fall into a few broad classes: |
| 751 |
|
| 752 |
* Functions that create a new iterator based on an existing iterator. |
| 753 |
* Functions for treating an iterator's elements as function arguments. |
| 754 |
* Functions for selecting portions of an iterator's output. |
| 755 |
* A function for grouping an iterator's output. |
| 756 |
|
| 757 |
Creating new iterators |
| 758 |
---------------------- |
| 759 |
|
| 760 |
:func:`itertools.count(start, step) <itertools.count>` returns an infinite |
| 761 |
stream of evenly spaced values. You can optionally supply the starting number, |
| 762 |
which defaults to 0, and the interval between numbers, which defaults to 1:: |
| 763 |
|
| 764 |
itertools.count() => |
| 765 |
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, ... |
| 766 |
itertools.count(10) => |
| 767 |
10, 11, 12, 13, 14, 15, 16, 17, 18, 19, ... |
| 768 |
itertools.count(10, 5) => |
| 769 |
10, 15, 20, 25, 30, 35, 40, 45, 50, 55, ... |
| 770 |
|
| 771 |
:func:`itertools.cycle(iter) <itertools.cycle>` saves a copy of the contents of |
| 772 |
a provided iterable and returns a new iterator that returns its elements from |
| 773 |
first to last. The new iterator will repeat these elements infinitely. :: |
| 774 |
|
| 775 |
itertools.cycle([1, 2, 3, 4, 5]) => |
| 776 |
1, 2, 3, 4, 5, 1, 2, 3, 4, 5, ... |
| 777 |
|
| 778 |
:func:`itertools.repeat(elem, [n]) <itertools.repeat>` returns the provided |
| 779 |
element *n* times, or returns the element endlessly if *n* is not provided. :: |
| 780 |
|
| 781 |
itertools.repeat('abc') => |
| 782 |
abc, abc, abc, abc, abc, abc, abc, abc, abc, abc, ... |
| 783 |
itertools.repeat('abc', 5) => |
| 784 |
abc, abc, abc, abc, abc |
| 785 |
|
| 786 |
:func:`itertools.chain(iterA, iterB, ...) <itertools.chain>` takes an arbitrary |
| 787 |
number of iterables as input, and returns all the elements of the first |
| 788 |
iterator, then all the elements of the second, and so on, until all of the |
| 789 |
iterables have been exhausted. :: |
| 790 |
|
| 791 |
itertools.chain(['a', 'b', 'c'], (1, 2, 3)) => |
| 792 |
a, b, c, 1, 2, 3 |
| 793 |
|
| 794 |
:func:`itertools.islice(iter, [start], stop, [step]) <itertools.islice>` returns |
| 795 |
a stream that's a slice of the iterator. With a single *stop* argument, it |
| 796 |
will return the first *stop* elements. If you supply a starting index, you'll |
| 797 |
get *stop-start* elements, and if you supply a value for *step*, elements |
| 798 |
will be skipped accordingly. Unlike Python's string and list slicing, you can't |
| 799 |
use negative values for *start*, *stop*, or *step*. :: |
| 800 |
|
| 801 |
itertools.islice(range(10), 8) => |
| 802 |
0, 1, 2, 3, 4, 5, 6, 7 |
| 803 |
itertools.islice(range(10), 2, 8) => |
| 804 |
2, 3, 4, 5, 6, 7 |
| 805 |
itertools.islice(range(10), 2, 8, 2) => |
| 806 |
2, 4, 6 |
| 807 |
|
| 808 |
:func:`itertools.tee(iter, [n]) <itertools.tee>` replicates an iterator; it |
| 809 |
returns *n* independent iterators that will all return the contents of the |
| 810 |
source iterator. |
| 811 |
If you don't supply a value for *n*, the default is 2. Replicating iterators |
| 812 |
requires saving some of the contents of the source iterator, so this can consume |
| 813 |
significant memory if the iterator is large and one of the new iterators is |
| 814 |
consumed more than the others. :: |
| 815 |
|
| 816 |
itertools.tee( itertools.count() ) => |
| 817 |
iterA, iterB |
| 818 |
|
| 819 |
where iterA -> |
| 820 |
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, ... |
| 821 |
|
| 822 |
and iterB -> |
| 823 |
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, ... |
| 824 |
|
| 825 |
|
| 826 |
Calling functions on elements |
| 827 |
----------------------------- |
| 828 |
|
| 829 |
The :mod:`operator` module contains a set of functions corresponding to Python's |
| 830 |
operators. Some examples are :func:`operator.add(a, b) <operator.add>` (adds |
| 831 |
two values), :func:`operator.ne(a, b) <operator.ne>` (same as ``a != b``), and |
| 832 |
:func:`operator.attrgetter('id') <operator.attrgetter>` |
| 833 |
(returns a callable that fetches the ``.id`` attribute). |
| 834 |
|
| 835 |
:func:`itertools.starmap(func, iter) <itertools.starmap>` assumes that the |
| 836 |
iterable will return a stream of tuples, and calls *func* using these tuples as |
| 837 |
the arguments:: |
| 838 |
|
| 839 |
itertools.starmap(os.path.join, |
| 840 |
[('/bin', 'python'), ('/usr', 'bin', 'java'), |
| 841 |
('/usr', 'bin', 'perl'), ('/usr', 'bin', 'ruby')]) |
| 842 |
=> |
| 843 |
/bin/python, /usr/bin/java, /usr/bin/perl, /usr/bin/ruby |
| 844 |
|
| 845 |
|
| 846 |
Selecting elements |
| 847 |
------------------ |
| 848 |
|
| 849 |
Another group of functions chooses a subset of an iterator's elements based on a |
| 850 |
predicate. |
| 851 |
|
| 852 |
:func:`itertools.filterfalse(predicate, iter) <itertools.filterfalse>` is the |
| 853 |
opposite of :func:`filter`, returning all elements for which the predicate |
| 854 |
returns false:: |
| 855 |
|
| 856 |
itertools.filterfalse(is_even, itertools.count()) => |
| 857 |
1, 3, 5, 7, 9, 11, 13, 15, ... |
| 858 |
|
| 859 |
:func:`itertools.takewhile(predicate, iter) <itertools.takewhile>` returns |
| 860 |
elements for as long as the predicate returns true. Once the predicate returns |
| 861 |
false, the iterator will signal the end of its results. :: |
| 862 |
|
| 863 |
def less_than_10(x): |
| 864 |
return x < 10 |
| 865 |
|
| 866 |
itertools.takewhile(less_than_10, itertools.count()) => |
| 867 |
0, 1, 2, 3, 4, 5, 6, 7, 8, 9 |
| 868 |
|
| 869 |
itertools.takewhile(is_even, itertools.count()) => |
| 870 |
0 |
| 871 |
|
| 872 |
:func:`itertools.dropwhile(predicate, iter) <itertools.dropwhile>` discards |
| 873 |
elements while the predicate returns true, and then returns the rest of the |
| 874 |
iterable's results. :: |
| 875 |
|
| 876 |
itertools.dropwhile(less_than_10, itertools.count()) => |
| 877 |
10, 11, 12, 13, 14, 15, 16, 17, 18, 19, ... |
| 878 |
|
| 879 |
itertools.dropwhile(is_even, itertools.count()) => |
| 880 |
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, ... |
| 881 |
|
| 882 |
:func:`itertools.compress(data, selectors) <itertools.compress>` takes two |
| 883 |
iterators and returns only those elements of *data* for which the corresponding |
| 884 |
element of *selectors* is true, stopping whenever either one is exhausted:: |
| 885 |
|
| 886 |
itertools.compress([1, 2, 3, 4, 5], [True, True, False, False, True]) => |
| 887 |
1, 2, 5 |
| 888 |
|
| 889 |
|
| 890 |
Combinatoric functions |
| 891 |
---------------------- |
| 892 |
|
| 893 |
The :func:`itertools.combinations(iterable, r) <itertools.combinations>` |
| 894 |
returns an iterator giving all possible *r*-tuple combinations of the |
| 895 |
elements contained in *iterable*. :: |
| 896 |
|
| 897 |
itertools.combinations([1, 2, 3, 4, 5], 2) => |
| 898 |
(1, 2), (1, 3), (1, 4), (1, 5), |
| 899 |
(2, 3), (2, 4), (2, 5), |
| 900 |
(3, 4), (3, 5), |
| 901 |
(4, 5) |
| 902 |
|
| 903 |
itertools.combinations([1, 2, 3, 4, 5], 3) => |
| 904 |
(1, 2, 3), (1, 2, 4), (1, 2, 5), (1, 3, 4), (1, 3, 5), (1, 4, 5), |
| 905 |
(2, 3, 4), (2, 3, 5), (2, 4, 5), |
| 906 |
(3, 4, 5) |
| 907 |
|
| 908 |
The elements within each tuple remain in the same order as |
| 909 |
*iterable* returned them. For example, the number 1 is always before |
| 910 |
2, 3, 4, or 5 in the examples above. A similar function, |
| 911 |
:func:`itertools.permutations(iterable, r=None) <itertools.permutations>`, |
| 912 |
removes this constraint on the order, returning all possible |
| 913 |
arrangements of length *r*:: |
| 914 |
|
| 915 |
itertools.permutations([1, 2, 3, 4, 5], 2) => |
| 916 |
(1, 2), (1, 3), (1, 4), (1, 5), |
| 917 |
(2, 1), (2, 3), (2, 4), (2, 5), |
| 918 |
(3, 1), (3, 2), (3, 4), (3, 5), |
| 919 |
(4, 1), (4, 2), (4, 3), (4, 5), |
| 920 |
(5, 1), (5, 2), (5, 3), (5, 4) |
| 921 |
|
| 922 |
itertools.permutations([1, 2, 3, 4, 5]) => |
| 923 |
(1, 2, 3, 4, 5), (1, 2, 3, 5, 4), (1, 2, 4, 3, 5), |
| 924 |
... |
| 925 |
(5, 4, 3, 2, 1) |
| 926 |
|
| 927 |
If you don't supply a value for *r* the length of the iterable is used, |
| 928 |
meaning that all the elements are permuted. |
| 929 |
|
| 930 |
Note that these functions produce all of the possible combinations by |
| 931 |
position and don't require that the contents of *iterable* are unique:: |
| 932 |
|
| 933 |
itertools.permutations('aba', 3) => |
| 934 |
('a', 'b', 'a'), ('a', 'a', 'b'), ('b', 'a', 'a'), |
| 935 |
('b', 'a', 'a'), ('a', 'a', 'b'), ('a', 'b', 'a') |
| 936 |
|
| 937 |
The identical tuple ``('a', 'a', 'b')`` occurs twice, but the two 'a' |
| 938 |
strings came from different positions. |
| 939 |
|
| 940 |
The :func:`itertools.combinations_with_replacement(iterable, r) <itertools.combinations_with_replacement>` |
| 941 |
function relaxes a different constraint: elements can be repeated |
| 942 |
within a single tuple. Conceptually an element is selected for the |
| 943 |
first position of each tuple and then is replaced before the second |
| 944 |
element is selected. :: |
| 945 |
|
| 946 |
itertools.combinations_with_replacement([1, 2, 3, 4, 5], 2) => |
| 947 |
(1, 1), (1, 2), (1, 3), (1, 4), (1, 5), |
| 948 |
(2, 2), (2, 3), (2, 4), (2, 5), |
| 949 |
(3, 3), (3, 4), (3, 5), |
| 950 |
(4, 4), (4, 5), |
| 951 |
(5, 5) |
| 952 |
|
| 953 |
|
| 954 |
Grouping elements |
| 955 |
----------------- |
| 956 |
|
| 957 |
The last function I'll discuss, :func:`itertools.groupby(iter, key_func=None) |
| 958 |
<itertools.groupby>`, is the most complicated. ``key_func(elem)`` is a function |
| 959 |
that can compute a key value for each element returned by the iterable. If you |
| 960 |
don't supply a key function, the key is simply each element itself. |
| 961 |
|
| 962 |
:func:`~itertools.groupby` collects all the consecutive elements from the |
| 963 |
underlying iterable that have the same key value, and returns a stream of |
| 964 |
2-tuples containing a key value and an iterator for the elements with that key. |
| 965 |
|
| 966 |
:: |
| 967 |
|
| 968 |
city_list = [('Decatur', 'AL'), ('Huntsville', 'AL'), ('Selma', 'AL'), |
| 969 |
('Anchorage', 'AK'), ('Nome', 'AK'), |
| 970 |
('Flagstaff', 'AZ'), ('Phoenix', 'AZ'), ('Tucson', 'AZ'), |
| 971 |
... |
| 972 |
] |
| 973 |
|
| 974 |
def get_state(city_state): |
| 975 |
return city_state[1] |
| 976 |
|
| 977 |
itertools.groupby(city_list, get_state) => |
| 978 |
('AL', iterator-1), |
| 979 |
('AK', iterator-2), |
| 980 |
('AZ', iterator-3), ... |
| 981 |
|
| 982 |
where |
| 983 |
iterator-1 => |
| 984 |
('Decatur', 'AL'), ('Huntsville', 'AL'), ('Selma', 'AL') |
| 985 |
iterator-2 => |
| 986 |
('Anchorage', 'AK'), ('Nome', 'AK') |
| 987 |
iterator-3 => |
| 988 |
('Flagstaff', 'AZ'), ('Phoenix', 'AZ'), ('Tucson', 'AZ') |
| 989 |
|
| 990 |
:func:`~itertools.groupby` assumes that the underlying iterable's contents will |
| 991 |
already be sorted based on the key. Note that the returned iterators also use |
| 992 |
the underlying iterable, so you have to consume the results of iterator-1 before |
| 993 |
requesting iterator-2 and its corresponding key. |
| 994 |
|
| 995 |
|
| 996 |
The functools module |
| 997 |
==================== |
| 998 |
|
| 999 |
The :mod:`functools` module contains some higher-order functions. |
| 1000 |
A **higher-order function** takes one or more functions as input and returns a |
| 1001 |
new function. The most useful tool in this module is the |
| 1002 |
:func:`functools.partial` function. |
| 1003 |
|
| 1004 |
For programs written in a functional style, you'll sometimes want to construct |
| 1005 |
variants of existing functions that have some of the parameters filled in. |
| 1006 |
Consider a Python function ``f(a, b, c)``; you may wish to create a new function |
| 1007 |
``g(b, c)`` that's equivalent to ``f(1, b, c)``; you're filling in a value for |
| 1008 |
one of ``f()``'s parameters. This is called "partial function application". |
| 1009 |
|
| 1010 |
The constructor for :func:`~functools.partial` takes the arguments |
| 1011 |
``(function, arg1, arg2, ..., kwarg1=value1, kwarg2=value2)``. The resulting |
| 1012 |
object is callable, so you can just call it to invoke ``function`` with the |
| 1013 |
filled-in arguments. |
| 1014 |
|
| 1015 |
Here's a small but realistic example:: |
| 1016 |
|
| 1017 |
import functools |
| 1018 |
|
| 1019 |
def log(message, subsystem): |
| 1020 |
"""Write the contents of 'message' to the specified subsystem.""" |
| 1021 |
print('%s: %s' % (subsystem, message)) |
| 1022 |
... |
| 1023 |
|
| 1024 |
server_log = functools.partial(log, subsystem='server') |
| 1025 |
server_log('Unable to open socket') |
| 1026 |
|
| 1027 |
:func:`functools.reduce(func, iter, [initial_value]) <functools.reduce>` |
| 1028 |
cumulatively performs an operation on all the iterable's elements and, |
| 1029 |
therefore, can't be applied to infinite iterables. *func* must be a function |
| 1030 |
that takes two elements and returns a single value. :func:`functools.reduce` |
| 1031 |
takes the first two elements A and B returned by the iterator and calculates |
| 1032 |
``func(A, B)``. It then requests the third element, C, calculates |
| 1033 |
``func(func(A, B), C)``, combines this result with the fourth element returned, |
| 1034 |
and continues until the iterable is exhausted. If the iterable returns no |
| 1035 |
values at all, a :exc:`TypeError` exception is raised. If the initial value is |
| 1036 |
supplied, it's used as a starting point and ``func(initial_value, A)`` is the |
| 1037 |
first calculation. :: |
| 1038 |
|
| 1039 |
>>> import operator, functools |
| 1040 |
>>> functools.reduce(operator.concat, ['A', 'BB', 'C']) |
| 1041 |
'ABBC' |
| 1042 |
>>> functools.reduce(operator.concat, []) |
| 1043 |
Traceback (most recent call last): |
| 1044 |
... |
| 1045 |
TypeError: reduce() of empty iterable with no initial value |
| 1046 |
>>> functools.reduce(operator.mul, [1, 2, 3], 1) |
| 1047 |
6 |
| 1048 |
>>> functools.reduce(operator.mul, [], 1) |
| 1049 |
1 |
| 1050 |
|
| 1051 |
If you use :func:`operator.add` with :func:`functools.reduce`, you'll add up all the |
| 1052 |
elements of the iterable. This case is so common that there's a special |
| 1053 |
built-in called :func:`sum` to compute it: |
| 1054 |
|
| 1055 |
>>> import functools, operator |
| 1056 |
>>> functools.reduce(operator.add, [1, 2, 3, 4], 0) |
| 1057 |
10 |
| 1058 |
>>> sum([1, 2, 3, 4]) |
| 1059 |
10 |
| 1060 |
>>> sum([]) |
| 1061 |
0 |
| 1062 |
|
| 1063 |
For many uses of :func:`functools.reduce`, though, it can be clearer to just |
| 1064 |
write the obvious :keyword:`for` loop:: |
| 1065 |
|
| 1066 |
import functools |
| 1067 |
# Instead of: |
| 1068 |
product = functools.reduce(operator.mul, [1, 2, 3], 1) |
| 1069 |
|
| 1070 |
# You can write: |
| 1071 |
product = 1 |
| 1072 |
for i in [1, 2, 3]: |
| 1073 |
product *= i |
| 1074 |
|
| 1075 |
A related function is :func:`itertools.accumulate(iterable, func=operator.add) |
| 1076 |
<itertools.accumulate>`. It performs the same calculation, but instead of |
| 1077 |
returning only the final result, :func:`~itertools.accumulate` returns an iterator |
| 1078 |
that also yields each partial result:: |
| 1079 |
|
| 1080 |
itertools.accumulate([1, 2, 3, 4, 5]) => |
| 1081 |
1, 3, 6, 10, 15 |
| 1082 |
|
| 1083 |
itertools.accumulate([1, 2, 3, 4, 5], operator.mul) => |
| 1084 |
1, 2, 6, 24, 120 |
| 1085 |
|
| 1086 |
|
| 1087 |
The operator module |
| 1088 |
------------------- |
| 1089 |
|
| 1090 |
The :mod:`operator` module was mentioned earlier. It contains a set of |
| 1091 |
functions corresponding to Python's operators. These functions are often useful |
| 1092 |
in functional-style code because they save you from writing trivial functions |
| 1093 |
that perform a single operation. |
| 1094 |
|
| 1095 |
Some of the functions in this module are: |
| 1096 |
|
| 1097 |
* Math operations: ``add()``, ``sub()``, ``mul()``, ``floordiv()``, ``abs()``, ... |
| 1098 |
* Logical operations: ``not_()``, ``truth()``. |
| 1099 |
* Bitwise operations: ``and_()``, ``or_()``, ``invert()``. |
| 1100 |
* Comparisons: ``eq()``, ``ne()``, ``lt()``, ``le()``, ``gt()``, and ``ge()``. |
| 1101 |
* Object identity: ``is_()``, ``is_not()``. |
| 1102 |
|
| 1103 |
Consult the operator module's documentation for a complete list. |
| 1104 |
|
| 1105 |
|
| 1106 |
Small functions and the lambda expression |
| 1107 |
========================================= |
| 1108 |
|
| 1109 |
When writing functional-style programs, you'll often need little functions that |
| 1110 |
act as predicates or that combine elements in some way. |
| 1111 |
|
| 1112 |
If there's a Python built-in or a module function that's suitable, you don't |
| 1113 |
need to define a new function at all:: |
| 1114 |
|
| 1115 |
stripped_lines = [line.strip() for line in lines] |
| 1116 |
existing_files = filter(os.path.exists, file_list) |
| 1117 |
|
| 1118 |
If the function you need doesn't exist, you need to write it. One way to write |
| 1119 |
small functions is to use the :keyword:`lambda` expression. ``lambda`` takes a |
| 1120 |
number of parameters and an expression combining these parameters, and creates |
| 1121 |
an anonymous function that returns the value of the expression:: |
| 1122 |
|
| 1123 |
adder = lambda x, y: x+y |
| 1124 |
|
| 1125 |
print_assign = lambda name, value: name + '=' + str(value) |
| 1126 |
|
| 1127 |
An alternative is to just use the ``def`` statement and define a function in the |
| 1128 |
usual way:: |
| 1129 |
|
| 1130 |
def adder(x, y): |
| 1131 |
return x + y |
| 1132 |
|
| 1133 |
def print_assign(name, value): |
| 1134 |
return name + '=' + str(value) |
| 1135 |
|
| 1136 |
Which alternative is preferable? That's a style question; my usual course is to |
| 1137 |
avoid using ``lambda``. |
| 1138 |
|
| 1139 |
One reason for my preference is that ``lambda`` is quite limited in the |
| 1140 |
functions it can define. The result has to be computable as a single |
| 1141 |
expression, which means you can't have multiway ``if... elif... else`` |
| 1142 |
comparisons or ``try... except`` statements. If you try to do too much in a |
| 1143 |
``lambda`` statement, you'll end up with an overly complicated expression that's |
| 1144 |
hard to read. Quick, what's the following code doing? :: |
| 1145 |
|
| 1146 |
import functools |
| 1147 |
total = functools.reduce(lambda a, b: (0, a[1] + b[1]), items)[1] |
| 1148 |
|
| 1149 |
You can figure it out, but it takes time to disentangle the expression to figure |
| 1150 |
out what's going on. Using a short nested ``def`` statements makes things a |
| 1151 |
little bit better:: |
| 1152 |
|
| 1153 |
import functools |
| 1154 |
def combine(a, b): |
| 1155 |
return 0, a[1] + b[1] |
| 1156 |
|
| 1157 |
total = functools.reduce(combine, items)[1] |
| 1158 |
|
| 1159 |
But it would be best of all if I had simply used a ``for`` loop:: |
| 1160 |
|
| 1161 |
total = 0 |
| 1162 |
for a, b in items: |
| 1163 |
total += b |
| 1164 |
|
| 1165 |
Or the :func:`sum` built-in and a generator expression:: |
| 1166 |
|
| 1167 |
total = sum(b for a, b in items) |
| 1168 |
|
| 1169 |
Many uses of :func:`functools.reduce` are clearer when written as ``for`` loops. |
| 1170 |
|
| 1171 |
Fredrik Lundh once suggested the following set of rules for refactoring uses of |
| 1172 |
``lambda``: |
| 1173 |
|
| 1174 |
1. Write a lambda function. |
| 1175 |
2. Write a comment explaining what the heck that lambda does. |
| 1176 |
3. Study the comment for a while, and think of a name that captures the essence |
| 1177 |
of the comment. |
| 1178 |
4. Convert the lambda to a def statement, using that name. |
| 1179 |
5. Remove the comment. |
| 1180 |
|
| 1181 |
I really like these rules, but you're free to disagree |
| 1182 |
about whether this lambda-free style is better. |
| 1183 |
|
| 1184 |
|
| 1185 |
Revision History and Acknowledgements |
| 1186 |
===================================== |
| 1187 |
|
| 1188 |
The author would like to thank the following people for offering suggestions, |
| 1189 |
corrections and assistance with various drafts of this article: Ian Bicking, |
| 1190 |
Nick Coghlan, Nick Efford, Raymond Hettinger, Jim Jewett, Mike Krell, Leandro |
| 1191 |
Lameiro, Jussi Salmela, Collin Winter, Blake Winton. |
| 1192 |
|
| 1193 |
Version 0.1: posted June 30 2006. |
| 1194 |
|
| 1195 |
Version 0.11: posted July 1 2006. Typo fixes. |
| 1196 |
|
| 1197 |
Version 0.2: posted July 10 2006. Merged genexp and listcomp sections into one. |
| 1198 |
Typo fixes. |
| 1199 |
|
| 1200 |
Version 0.21: Added more references suggested on the tutor mailing list. |
| 1201 |
|
| 1202 |
Version 0.30: Adds a section on the ``functional`` module written by Collin |
| 1203 |
Winter; adds short section on the operator module; a few other edits. |
| 1204 |
|
| 1205 |
|
| 1206 |
References |
| 1207 |
========== |
| 1208 |
|
| 1209 |
General |
| 1210 |
------- |
| 1211 |
|
| 1212 |
**Structure and Interpretation of Computer Programs**, by Harold Abelson and |
| 1213 |
Gerald Jay Sussman with Julie Sussman. The book can be found at |
| 1214 |
https://mitpress.mit.edu/sicp. In this classic textbook of computer science, |
| 1215 |
chapters 2 and 3 discuss the use of sequences and streams to organize the data |
| 1216 |
flow inside a program. The book uses Scheme for its examples, but many of the |
| 1217 |
design approaches described in these chapters are applicable to functional-style |
| 1218 |
Python code. |
| 1219 |
|
| 1220 |
https://defmacro.org/2006/06/19/fp.html: A general introduction to functional |
| 1221 |
programming that uses Java examples and has a lengthy historical introduction. |
| 1222 |
|
| 1223 |
https://en.wikipedia.org/wiki/Functional_programming: General Wikipedia entry |
| 1224 |
describing functional programming. |
| 1225 |
|
| 1226 |
https://en.wikipedia.org/wiki/Coroutine: Entry for coroutines. |
| 1227 |
|
| 1228 |
https://en.wikipedia.org/wiki/Partial_application: Entry for the concept of partial function application. |
| 1229 |
|
| 1230 |
https://en.wikipedia.org/wiki/Currying: Entry for the concept of currying. |
| 1231 |
|
| 1232 |
Python-specific |
| 1233 |
--------------- |
| 1234 |
|
| 1235 |
https://gnosis.cx/TPiP/: The first chapter of David Mertz's book |
| 1236 |
:title-reference:`Text Processing in Python` discusses functional programming |
| 1237 |
for text processing, in the section titled "Utilizing Higher-Order Functions in |
| 1238 |
Text Processing". |
| 1239 |
|
| 1240 |
Mertz also wrote a 3-part series of articles on functional programming |
| 1241 |
for IBM's DeveloperWorks site; see |
| 1242 |
`part 1 <https://developer.ibm.com/articles/l-prog/>`__, |
| 1243 |
`part 2 <https://developer.ibm.com/tutorials/l-prog2/>`__, and |
| 1244 |
`part 3 <https://developer.ibm.com/tutorials/l-prog3/>`__, |
| 1245 |
|
| 1246 |
|
| 1247 |
Python documentation |
| 1248 |
-------------------- |
| 1249 |
|
| 1250 |
Documentation for the :mod:`itertools` module. |
| 1251 |
|
| 1252 |
Documentation for the :mod:`functools` module. |
| 1253 |
|
| 1254 |
Documentation for the :mod:`operator` module. |
| 1255 |
|
| 1256 |
:pep:`289`: "Generator Expressions" |
| 1257 |
|
| 1258 |
:pep:`342`: "Coroutines via Enhanced Generators" describes the new generator |
| 1259 |
features in Python 2.5. |
| 1260 |
|
| 1261 |
.. comment |
| 1262 |
|
| 1263 |
Handy little function for printing part of an iterator -- used |
| 1264 |
while writing this document. |
| 1265 |
|
| 1266 |
import itertools |
| 1267 |
def print_iter(it): |
| 1268 |
slice = itertools.islice(it, 10) |
| 1269 |
for elem in slice[:-1]: |
| 1270 |
sys.stdout.write(str(elem)) |
| 1271 |
sys.stdout.write(', ') |
| 1272 |
print(elem[-1]) |