Debian Codegraph @

Doc/howto/functional.rst

raw
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 sequence 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])