[Python-checkins] r61737 - python/trunk/Doc/howto/functional.rst
georg.brandl
python-checkins at python.org
Sat Mar 22 12:00:49 CET 2008
Author: georg.brandl
Date: Sat Mar 22 12:00:48 2008
New Revision: 61737
Modified:
python/trunk/Doc/howto/functional.rst
Log:
Fixup this HOWTO's doctest blocks so that they can be run with sphinx' doctest builder.
Modified: python/trunk/Doc/howto/functional.rst
==============================================================================
--- python/trunk/Doc/howto/functional.rst (original)
+++ python/trunk/Doc/howto/functional.rst Sat Mar 22 12:00:48 2008
@@ -2,7 +2,7 @@
Functional Programming HOWTO
********************************
-:Author: \A. M. Kuchling
+:Author: A. M. Kuchling
:Release: 0.31
(This is a first draft. Please send comments/error reports/suggestions to
@@ -98,6 +98,7 @@
* Composability.
* Ease of debugging and testing.
+
Formal provability
------------------
@@ -133,6 +134,7 @@
proof; maybe there's an error in it, and you wrongly believe you've proved the
program correct.
+
Modularity
----------
@@ -159,7 +161,6 @@
check that the output matches expectations.
-
Composability
-------------
@@ -175,7 +176,6 @@
a few functions specialized for the current task.
-
Iterators
=========
@@ -197,12 +197,12 @@
dictionaries. An object is called an **iterable** object if you can get an
iterator for it.
-You can experiment with the iteration interface manually::
+You can experiment with the iteration interface manually:
>>> L = [1,2,3]
>>> it = iter(L)
>>> print it
- <iterator object at 0x8116870>
+ <...iterator object at ...>
>>> it.next()
1
>>> it.next()
@@ -220,14 +220,14 @@
be an iterator or some object for which ``iter()`` can create an iterator.
These two statements are equivalent::
- for i in iter(obj):
- print i
+ for i in iter(obj):
+ print i
- for i in obj:
- print i
+ for i in obj:
+ print i
Iterators can be materialized as lists or tuples by using the :func:`list` or
-:func:`tuple` constructor functions::
+:func:`tuple` constructor functions:
>>> L = [1,2,3]
>>> iterator = iter(L)
@@ -236,7 +236,7 @@
(1, 2, 3)
Sequence unpacking also supports iterators: if you know an iterator will return
-N elements, you can unpack them into an N-tuple::
+N elements, you can unpack them into an N-tuple:
>>> L = [1,2,3]
>>> iterator = iter(L)
@@ -269,7 +269,7 @@
iterator.
Calling :func:`iter` on a dictionary returns an iterator that will loop over the
-dictionary's keys::
+dictionary's keys:
>>> m = {'Jan': 1, 'Feb': 2, 'Mar': 3, 'Apr': 4, 'May': 5, 'Jun': 6,
... 'Jul': 7, 'Aug': 8, 'Sep': 9, 'Oct': 10, 'Nov': 11, 'Dec': 12}
@@ -279,11 +279,11 @@
Feb 2
Aug 8
Sep 9
- May 5
+ Apr 4
Jun 6
Jul 7
Jan 1
- Apr 4
+ May 5
Nov 11
Dec 12
Oct 10
@@ -297,7 +297,7 @@
``itervalues()``, or ``iteritems()`` methods to get an appropriate iterator.
The :func:`dict` constructor can accept an iterator that returns a finite stream
-of ``(key, value)`` tuples::
+of ``(key, value)`` tuples:
>>> L = [('Italy', 'Rome'), ('France', 'Paris'), ('US', 'Washington DC')]
>>> dict(iter(L))
@@ -334,18 +334,18 @@
functional programming language Haskell (http://www.haskell.org). You can strip
all the whitespace from a stream of strings with the following code::
- line_list = [' line 1\n', 'line 2 \n', ...]
+ line_list = [' line 1\n', 'line 2 \n', ...]
- # Generator expression -- returns iterator
- stripped_iter = (line.strip() for line in line_list)
+ # Generator expression -- returns iterator
+ stripped_iter = (line.strip() for line in line_list)
- # List comprehension -- returns list
- stripped_list = [line.strip() for line in line_list]
+ # List comprehension -- returns list
+ stripped_list = [line.strip() for line in line_list]
You can select only certain elements by adding an ``"if"`` condition::
- stripped_list = [line.strip() for line in line_list
- if line != ""]
+ stripped_list = [line.strip() for line in line_list
+ if line != ""]
With a list comprehension, you get back a Python list; ``stripped_list`` is a
list containing the resulting lines, not an iterator. Generator expressions
@@ -378,7 +378,7 @@
parentheses signalling a function call also count. If you want to create an
iterator that will be immediately passed to a function you can write::
- obj_total = sum(obj.count for obj in list_all_objects())
+ obj_total = sum(obj.count for obj in list_all_objects())
The ``for...in`` clauses contain the sequences to be iterated over. The
sequences do not have to be the same length, because they are iterated over from
@@ -406,11 +406,14 @@
This means that when there are multiple ``for...in`` clauses but no ``if``
clauses, the length of the resulting output will be equal to the product of the
lengths of all the sequences. If you have two lists of length 3, the output
-list is 9 elements long::
+list is 9 elements long:
- seq1 = 'abc'
- seq2 = (1,2,3)
- >>> [ (x,y) for x in seq1 for y in seq2]
+.. doctest::
+ :options: +NORMALIZE_WHITESPACE
+
+ >>> seq1 = 'abc'
+ >>> seq2 = (1,2,3)
+ >>> [(x,y) for x in seq1 for y in seq2]
[('a', 1), ('a', 2), ('a', 3),
('b', 1), ('b', 2), ('b', 3),
('c', 1), ('c', 2), ('c', 3)]
@@ -441,7 +444,9 @@
function? What if you could later resume the function where it left off? This
is what generators provide; they can be thought of as resumable functions.
-Here's the simplest example of a generator function::
+Here's the simplest example of a generator function:
+
+.. testcode:: doctest_block
def generate_ints(N):
for i in range(N):
@@ -459,11 +464,11 @@
suspended and local variables are preserved. On the next call to the
generator's ``.next()`` method, the function will resume executing.
-Here's a sample usage of the ``generate_ints()`` generator::
+Here's a sample usage of the ``generate_ints()`` generator:
>>> gen = generate_ints(3)
>>> gen
- <generator object at 0x8117f90>
+ <generator object at ...>
>>> gen.next()
0
>>> gen.next()
@@ -496,9 +501,7 @@
The test suite included with Python's library, ``test_generators.py``, contains
a number of more interesting examples. Here's one generator that implements an
-in-order traversal of a tree using generators recursively.
-
-::
+in-order traversal of a tree using generators recursively. ::
# A recursive generator that generates Tree leaves in in-order.
def inorder(t):
@@ -553,7 +556,7 @@
Here's a simple counter that increments by 1 and allows changing the value of
the internal counter.
-::
+.. testcode:: doctest_block
def counter (maximum):
i = 0
@@ -623,15 +626,14 @@
``map(f, iterA, iterB, ...)`` returns a list containing ``f(iterA[0], iterB[0]),
f(iterA[1], iterB[1]), f(iterA[2], iterB[2]), ...``.
-::
+ >>> def upper(s):
+ ... return s.upper()
- def upper(s):
- return s.upper()
- map(upper, ['sentence', 'fragment']) =>
- ['SENTENCE', 'FRAGMENT']
+ >>> map(upper, ['sentence', 'fragment'])
+ ['SENTENCE', 'FRAGMENT']
- [upper(s) for s in ['sentence', 'fragment']] =>
- ['SENTENCE', 'FRAGMENT']
+ >>> [upper(s) for s in ['sentence', 'fragment']]
+ ['SENTENCE', 'FRAGMENT']
As shown above, you can achieve the same effect with a list comprehension. The
:func:`itertools.imap` function does the same thing but can handle infinite
@@ -643,15 +645,13 @@
some condition; for use with :func:`filter`, the predicate must take a single
value.
-::
-
- def is_even(x):
- return (x % 2) == 0
+ >>> def is_even(x):
+ ... return (x % 2) == 0
- filter(is_even, range(10)) =>
- [0, 2, 4, 6, 8]
+ >>> filter(is_even, range(10))
+ [0, 2, 4, 6, 8]
-This can also be written as a list comprehension::
+This can also be written as a list comprehension:
>>> [x for x in range(10) if is_even(x)]
[0, 2, 4, 6, 8]
@@ -672,28 +672,28 @@
supplied, it's used as a starting point and ``func(initial_value, A)`` is the
first calculation.
-::
-
- import operator
- reduce(operator.concat, ['A', 'BB', 'C']) =>
- 'ABBC'
- reduce(operator.concat, []) =>
- TypeError: reduce() of empty sequence with no initial value
- reduce(operator.mul, [1,2,3], 1) =>
- 6
- reduce(operator.mul, [], 1) =>
- 1
+ >>> import operator
+ >>> reduce(operator.concat, ['A', 'BB', 'C'])
+ 'ABBC'
+ >>> reduce(operator.concat, [])
+ Traceback (most recent call last):
+ ...
+ TypeError: reduce() of empty sequence with no initial value
+ >>> reduce(operator.mul, [1,2,3], 1)
+ 6
+ >>> reduce(operator.mul, [], 1)
+ 1
If you use :func:`operator.add` with :func:`reduce`, you'll add up all the
elements of the iterable. This case is so common that there's a special
-built-in called :func:`sum` to compute it::
+built-in called :func:`sum` to compute it:
- reduce(operator.add, [1,2,3,4], 0) =>
- 10
- sum([1,2,3,4]) =>
- 10
- sum([]) =>
- 0
+ >>> reduce(operator.add, [1,2,3,4], 0)
+ 10
+ >>> sum([1,2,3,4])
+ 10
+ >>> sum([])
+ 0
For many uses of :func:`reduce`, though, it can be clearer to just write the
obvious :keyword:`for` loop::
@@ -710,10 +710,11 @@
``enumerate(iter)`` counts off the elements in the iterable, returning 2-tuples
containing the count and each element.
-::
-
- enumerate(['subject', 'verb', 'object']) =>
- (0, 'subject'), (1, 'verb'), (2, 'object')
+ >>> for item in enumerate(['subject', 'verb', 'object']):
+ ... print item
+ (0, 'subject')
+ (1, 'verb')
+ (2, 'object')
:func:`enumerate` is often used when looping through a list and recording the
indexes at which certain conditions are met::
@@ -726,19 +727,17 @@
``sorted(iterable, [cmp=None], [key=None], [reverse=False)`` collects all the
elements of the iterable into a list, sorts the list, and returns the sorted
result. The ``cmp``, ``key``, and ``reverse`` arguments are passed through to
-the constructed list's ``.sort()`` method.
-
-::
+the constructed list's ``.sort()`` method. ::
- import random
- # Generate 8 random numbers between [0, 10000)
- rand_list = random.sample(range(10000), 8)
- rand_list =>
- [769, 7953, 9828, 6431, 8442, 9878, 6213, 2207]
- sorted(rand_list) =>
- [769, 2207, 6213, 6431, 7953, 8442, 9828, 9878]
- sorted(rand_list, reverse=True) =>
- [9878, 9828, 8442, 7953, 6431, 6213, 2207, 769]
+ >>> import random
+ >>> # Generate 8 random numbers between [0, 10000)
+ >>> rand_list = random.sample(range(10000), 8)
+ >>> rand_list
+ [769, 7953, 9828, 6431, 8442, 9878, 6213, 2207]
+ >>> sorted(rand_list)
+ [769, 2207, 6213, 6431, 7953, 8442, 9828, 9878]
+ >>> sorted(rand_list, reverse=True)
+ [9878, 9828, 8442, 7953, 6431, 6213, 2207, 769]
(For a more detailed discussion of sorting, see the Sorting mini-HOWTO in the
Python wiki at http://wiki.python.org/moin/HowTo/Sorting.)
@@ -746,20 +745,20 @@
The ``any(iter)`` and ``all(iter)`` built-ins look at the truth values of an
iterable's contents. :func:`any` returns True if any element in the iterable is
a true value, and :func:`all` returns True if all of the elements are true
-values::
+values:
- any([0,1,0]) =>
- True
- any([0,0,0]) =>
- False
- any([1,1,1]) =>
- True
- all([0,1,0]) =>
- False
- all([0,0,0]) =>
- False
- all([1,1,1]) =>
- True
+ >>> any([0,1,0])
+ True
+ >>> any([0,0,0])
+ False
+ >>> any([1,1,1])
+ True
+ >>> all([0,1,0])
+ False
+ >>> all([0,0,0])
+ False
+ >>> all([1,1,1])
+ True
Small functions and the lambda expression
@@ -771,31 +770,31 @@
If there's a Python built-in or a module function that's suitable, you don't
need to define a new function at all::
- stripped_lines = [line.strip() for line in lines]
- existing_files = filter(os.path.exists, file_list)
+ stripped_lines = [line.strip() for line in lines]
+ existing_files = filter(os.path.exists, file_list)
If the function you need doesn't exist, you need to write it. One way to write
small functions is to use the ``lambda`` statement. ``lambda`` takes a number
of parameters and an expression combining these parameters, and creates a small
function that returns the value of the expression::
- lowercase = lambda x: x.lower()
+ lowercase = lambda x: x.lower()
- print_assign = lambda name, value: name + '=' + str(value)
+ print_assign = lambda name, value: name + '=' + str(value)
- adder = lambda x, y: x+y
+ adder = lambda x, y: x+y
An alternative is to just use the ``def`` statement and define a function in the
usual way::
- def lowercase(x):
- return x.lower()
+ def lowercase(x):
+ return x.lower()
- def print_assign(name, value):
- return name + '=' + str(value)
+ def print_assign(name, value):
+ return name + '=' + str(value)
- def adder(x,y):
- return x + y
+ def adder(x,y):
+ return x + y
Which alternative is preferable? That's a style question; my usual course is to
avoid using ``lambda``.
@@ -866,24 +865,20 @@
``itertools.count(n)`` returns an infinite stream of integers, increasing by 1
each time. You can optionally supply the starting number, which defaults to 0::
- itertools.count() =>
- 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, ...
- itertools.count(10) =>
- 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, ...
+ itertools.count() =>
+ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, ...
+ itertools.count(10) =>
+ 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, ...
``itertools.cycle(iter)`` saves a copy of the contents of a provided iterable
and returns a new iterator that returns its elements from first to last. The
-new iterator will repeat these elements infinitely.
-
-::
+new iterator will repeat these elements infinitely. ::
- itertools.cycle([1,2,3,4,5]) =>
- 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, ...
+ itertools.cycle([1,2,3,4,5]) =>
+ 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, ...
``itertools.repeat(elem, [n])`` returns the provided element ``n`` times, or
-returns the element endlessly if ``n`` is not provided.
-
-::
+returns the element endlessly if ``n`` is not provided. ::
itertools.repeat('abc') =>
abc, abc, abc, abc, abc, abc, abc, abc, abc, abc, ...
@@ -892,9 +887,7 @@
``itertools.chain(iterA, iterB, ...)`` takes an arbitrary number of iterables as
input, and returns all the elements of the first iterator, then all the elements
-of the second, and so on, until all of the iterables have been exhausted.
-
-::
+of the second, and so on, until all of the iterables have been exhausted. ::
itertools.chain(['a', 'b', 'c'], (1, 2, 3)) =>
a, b, c, 1, 2, 3
@@ -913,9 +906,7 @@
This iterator is intended to be used with iterables that are all of the same
length. If the iterables are of different lengths, the resulting stream will be
-the same length as the shortest iterable.
-
-::
+the same length as the shortest iterable. ::
itertools.izip(['a', 'b'], (1, 2, 3)) =>
('a', 1), ('b', 2)
@@ -929,9 +920,7 @@
first ``stop`` elements. If you supply a starting index, you'll get
``stop-start`` elements, and if you supply a value for ``step``, elements will
be skipped accordingly. Unlike Python's string and list slicing, you can't use
-negative values for ``start``, ``stop``, or ``step``.
-
-::
+negative values for ``start``, ``stop``, or ``step``. ::
itertools.islice(range(10), 8) =>
0, 1, 2, 3, 4, 5, 6, 7
@@ -945,9 +934,7 @@
If you don't supply a value for ``n``, the default is 2. Replicating iterators
requires saving some of the contents of the source iterator, so this can consume
significant memory if the iterator is large and one of the new iterators is
-consumed more than the others.
-
-::
+consumed more than the others. ::
itertools.tee( itertools.count() ) =>
iterA, iterB
@@ -1144,87 +1131,75 @@
The ``compose()`` function implements function composition. In other words, it
returns a wrapper around the ``outer`` and ``inner`` callables, such that the
-return value from ``inner`` is fed directly to ``outer``. That is,
-
-::
+return value from ``inner`` is fed directly to ``outer``. That is, ::
- >>> def add(a, b):
- ... return a + b
- ...
- >>> def double(a):
- ... return 2 * a
- ...
- >>> compose(double, add)(5, 6)
- 22
+ >>> def add(a, b):
+ ... return a + b
+ ...
+ >>> def double(a):
+ ... return 2 * a
+ ...
+ >>> compose(double, add)(5, 6)
+ 22
-is equivalent to
-
-::
+is equivalent to ::
- >>> double(add(5, 6))
- 22
+ >>> double(add(5, 6))
+ 22
The ``unpack`` keyword is provided to work around the fact that Python functions
are not always `fully curried <http://en.wikipedia.org/wiki/Currying>`__. By
default, it is expected that the ``inner`` function will return a single object
and that the ``outer`` function will take a single argument. Setting the
``unpack`` argument causes ``compose`` to expect a tuple from ``inner`` which
-will be expanded before being passed to ``outer``. Put simply,
+will be expanded before being passed to ``outer``. Put simply, ::
-::
-
- compose(f, g)(5, 6)
+ compose(f, g)(5, 6)
is equivalent to::
- f(g(5, 6))
+ f(g(5, 6))
-while
-
-::
+while ::
- compose(f, g, unpack=True)(5, 6)
+ compose(f, g, unpack=True)(5, 6)
is equivalent to::
- f(*g(5, 6))
+ f(*g(5, 6))
Even though ``compose()`` only accepts two functions, it's trivial to build up a
version that will compose any number of functions. We'll use ``reduce()``,
``compose()`` and ``partial()`` (the last of which is provided by both
-``functional`` and ``functools``).
+``functional`` and ``functools``). ::
-::
-
- from functional import compose, partial
+ from functional import compose, partial
- multi_compose = partial(reduce, compose)
+ multi_compose = partial(reduce, compose)
We can also use ``map()``, ``compose()`` and ``partial()`` to craft a version of
``"".join(...)`` that converts its arguments to string::
- from functional import compose, partial
+ from functional import compose, partial
- join = compose("".join, partial(map, str))
+ join = compose("".join, partial(map, str))
``flip(func)``
``flip()`` wraps the callable in ``func`` and causes it to receive its
-non-keyword arguments in reverse order.
+non-keyword arguments in reverse order. ::
-::
-
- >>> def triple(a, b, c):
- ... return (a, b, c)
- ...
- >>> triple(5, 6, 7)
- (5, 6, 7)
- >>>
- >>> flipped_triple = flip(triple)
- >>> flipped_triple(5, 6, 7)
- (7, 6, 5)
+ >>> def triple(a, b, c):
+ ... return (a, b, c)
+ ...
+ >>> triple(5, 6, 7)
+ (5, 6, 7)
+ >>>
+ >>> flipped_triple = flip(triple)
+ >>> flipped_triple(5, 6, 7)
+ (7, 6, 5)
``foldl(func, start, iterable)``
@@ -1235,35 +1210,34 @@
This means that a call such as::
- foldl(f, 0, [1, 2, 3])
+ foldl(f, 0, [1, 2, 3])
is equivalent to::
- f(f(f(0, 1), 2), 3)
+ f(f(f(0, 1), 2), 3)
``foldl()`` is roughly equivalent to the following recursive function::
- def foldl(func, start, seq):
- if len(seq) == 0:
- return start
+ def foldl(func, start, seq):
+ if len(seq) == 0:
+ return start
- return foldl(func, func(start, seq[0]), seq[1:])
+ return foldl(func, func(start, seq[0]), seq[1:])
Speaking of equivalence, the above ``foldl`` call can be expressed in terms of
the built-in ``reduce`` like so::
- reduce(f, [1, 2, 3], 0)
+ reduce(f, [1, 2, 3], 0)
We can use ``foldl()``, ``operator.concat()`` and ``partial()`` to write a
cleaner, more aesthetically-pleasing version of Python's ``"".join(...)``
idiom::
- from functional import foldl, partial
- from operator import concat
-
- join = partial(foldl, concat, "")
+ from functional import foldl, partial from operator import concat
+
+ join = partial(foldl, concat, "")
Revision History and Acknowledgements
More information about the Python-checkins
mailing list