[Python-checkins] r46042 - sandbox/trunk/Doc/functional.rst
andrew.kuchling
python-checkins at python.org
Fri May 19 02:04:44 CEST 2006
Author: andrew.kuchling
Date: Fri May 19 02:04:44 2006
New Revision: 46042
Modified:
sandbox/trunk/Doc/functional.rst
Log:
Add two sections
Modified: sandbox/trunk/Doc/functional.rst
==============================================================================
--- sandbox/trunk/Doc/functional.rst (original)
+++ sandbox/trunk/Doc/functional.rst Fri May 19 02:04:44 2006
@@ -4,7 +4,11 @@
**Incomplete Draft**
In this document, we'll take a tour of Python's features that are
-well-suited to implementing programs in a functional style.
+well-suited to implementing programs in a functional style.
+After an introduction to the concepts of functional programming,
+we'll look at language features such as iterators and generators
+and relevant library modules such as the ``itertools`` module.
+
Introduction
----------------------
@@ -60,6 +64,11 @@
a pointless skill like writing a BASIC interpreter in {\TeX}. There
are theoretical and practical advantages to the functional style:
+* Formal provability.
+* Modularity.
+* Composability.
+* Ease of debugging and testing.
+
Formal provability
''''''''''''''''''''''
@@ -97,101 +106,293 @@
Modularity
''''''''''''''''''''''
-Ease of debugging
-''''''''''''''''''''''
+.. comment
+ Small functions that do one thing.
Composability
''''''''''''''''''''''
+.. comment
+
+ You assemble a toolbox of functions that can be mixed
-*
- Formal provability
- Not very relevant to Python
- Modularity
- Small functions that do one thing
- Debuggability:
+Ease of debugging
+''''''''''''''''''''''
+
+.. comment
Easy to test due to lack of state
Easy to verify output from intermediate steps
- Composability
- You assemble a toolbox of functions that can be mixed
-Functional programming can be considered the opposite of
-object-oriented programming. Objects are little capsules containing
-some internal state, and there's a collection of method calls that let
-you modify this state.
-The Idea of Functional Programming
-'''''''''''''''''''''''''''''''''''''''
- Programs built out of functions
- Functions are strictly input-output, no internal state
- Opposed to OO programming, where objects have state
-
-Why Functional Programming?
-'''''''''''''''''''''''''''''''''''
+
Formal provability
- Assignment is difficult to reason about
Not very relevant to Python
Modularity
Small functions that do one thing
+ Composability
+ You assemble a toolbox of functions that can be mixed
Debuggability:
Easy to test due to lack of state
Easy to verify output from intermediate steps
- Composability
- You assemble a toolbox of functions that can be mixed
-Tackling a problem
--------------------------
- Need a significant example
+Functional programming can be considered the opposite of
+object-oriented programming. Objects are little capsules containing
+some internal state along with a collection of method calls that let
+you modify this state.
+
+
Iterators
-----------------------
-Basic idea
- Object which supports next() and raises StopIteration
- Iterators don't need to end
+Iterators are the fundamental Python feature that provides
+the foundation for writing functional-style programs.
+
+An iterator is an object representing a stream of data that returns
+the data one element at a time. A Python iterator must support a
+method called ``next()`` that takes no arguments and always returns
+the next element of the stream. If there are no more elements in the
+stream, ``next()`` must raise the ``StopIteration`` exception.
+Iterators don't have to be finite, though; it's perfectly reasonable
+to write an iterator that produces an infinite stream of data.
+
+The built-in ``iter()`` function takes an arbitrary object and tries
+to return an iterator that will return the object's contents or
+elements, raising ``TypeError`` if the object doesn't support
+iteration. Several of Python's built-in data types support iteration,
+the most common being lists and dictionaries.
+
+You can experiment with the iteration interface manually::
+
+ >>> L = [1,2,3]
+ >>> it = iter(L)
+ >>> print it
+ <iterator object at 0x8116870>
+ >>> it.next()
+ 1
+ >>> it.next()
+ 2
+ >>> it.next()
+ 3
+ >>> it.next()
+ Traceback (most recent call last):
+ File "<stdin>", line 1, in ?
+ StopIteration
+ >>>
+
+Python expects iterable objects in several different contexts, the
+most important being the ``for`` statement. In the statement ``for X in Y``,
+Y must 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 obj:
+ print i
+
+Iterators can be materialized as lists or tuples by using the ``list()`` or ``tuple()``
+constructor functions::
+
+ >>> L = [1,2,3]
+ >>> iterator = iter(L)
+ >>> t = tuple(iterator)
+ >>> t
+ (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::
+
+ >>> L = [1,2,3]
+ >>> iterator = iter(L)
+ >>> a,b,c = i
+ >>> a,b,c
+ (1, 2, 3)
+
+Built-in functions such as ``max()`` and ``min()`` can take a single
+iterator argument and will return the largest or smallest element.
+The ``"in"`` and ``"not in"`` operators also support iterators: ``X in
+iterator`` is true if X is found in the stream returned by the
+iterator. You'll run into obvious problems if the iterator is
+infinite; ``max()``, ``min()``, and ``"not in"`` will never return, and
+if the element X never appears in the stream, the ``"in"`` operator
+won't return either.
+
+Note that you can only go forward in an iterator; there's no way to
+get the previous element, reset the iterator, or make a copy of it.
+Iterator objects can optionally provide these additional capabilities,
+but the iterator protocol only specifies the \method{next()} method.
+Functions may therefore consume all of the iterator's output, and if
+you need to do something different with the same stream, you'll have
+to create a new iterator.
+
+
+
+Data Types That Support Iterators
+'''''''''''''''''''''''''''''''''''
+
+We've already seen how lists and tuples support iterators. In fact,
+any Python sequence type, such as strings, will automatically support
+creation of an iterator.
+
+Calling ``iter()`` on a dictionary returns an iterator that will loop
+over the 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}
+ >>> for key in m:
+ ... print key, m[key]
+ Mar 3
+ Feb 2
+ Aug 8
+ Sep 9
+ May 5
+ Jun 6
+ Jul 7
+ Jan 1
+ Apr 4
+ Nov 11
+ Dec 12
+ Oct 10
+
+This is just the default behaviour. If you want to iterate over keys,
+values, or key/value pairs, you can explicitly call the
+\method{iterkeys()}, \method{itervalues()}, or \method{iteritems()}
+methods to get an appropriate iterator.
+
+The ``dict()`` constructor can accept an iterator that returns a
+finite stream of ``(key, value)`` tuples::
+
+ >>> L = [('Italy', 'Rome'), ('France', 'Paris'), ('US', 'Washington DC')]
+ >>> dict(iter(L))
+ {'Italy': 'Rome', 'US': 'Washington DC', 'France': 'Paris'}
+
+Files also support iteration by calling the \method{readline()}
+method until there are no more lines in the file. This means you can
+read each line of a file like this:
+
+\begin{verbatim}
+for line in file:
+ # do something for each line
+ ...
+\end{verbatim}
+
+XXX sets
-iter() -- returns an iterator for an object
-Example: iter(list)
-Objects: __iter__ returns iterator
-Example: object w/ list of contents
List comprehensions
-----------------------
-Some built-ins support iterators, some don't. min(), max(), len(), dict().
-List comps.
+Two common operations on a stream are performing some operation for
+every element, or selecting a subset of elements that meet some
+condition. For example, given a list of strings, you might want to
+pull out all the strings containing a given substring, or strip off
+trailing whitespace from each line.
+
+List comprehensions (or "listcomps") are a concise notation for such
+operations, borrowed from the functional programming language Haskell
+(\url{http://www.haskell.org}). You can strip all the whitespace from
+a stream of strings with the following list comprehension::
+
+ line_list = [' line 1\n', 'line 2 \n', ...]
+ 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 != ""]
+
+Note that in all case the resulting ``stripped_list`` is a Python list
+containing the resulting lines, not an iterator. This means that list
+comprehensions aren't very useful if you're working with iterators
+that return an infinite or a very large stream of data.
+
+List comprehensions have the form::
+
+ [ expression for expr in sequence1
+ for expr2 in sequence2
+ for expr3 in sequence3 ...
+ for exprN in sequenceN
+ if condition ]
+
+The elements of the generated list will be the successive
+values of \var{expression}. The final \keyword{if} clause is
+optional; if present, \var{expression} is only evaluated and added to
+the result when \var{condition} is true.
+
+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 left to right, **not** in parallel. For each
+element in ``sequence1``, ``sequence2`` is looped over from the
+beginning. ``sequence3`` is then looped over for each
+resulting pair of elements from ``sequence1`` and ``sequence2``.
+
+Put another way, a list comprehension is equivalent to the following
+Python code:
+
+\begin{verbatim}
+for expr1 in sequence1:
+ for expr2 in sequence2:
+ ...
+ for exprN in sequenceN:
+ if (condition):
+ # Append the value of
+ # the expression to the
+ # resulting list.
+\end{verbatim}
+
+This means that when there are multiple \keyword{for}...\keyword{in}
+clauses, the resulting list 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:
+
+ 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)]
+
+To avoid introducing an ambiguity into Python's grammar, if
+``expression`` is creating a tuple, it must be surrounded with
+parentheses. The first list comprehension below is a syntax error,
+while the second one is correct:
+
+ # Syntax error
+ [ x,y for x in seq1 for y in seq2]
+ # Correct
+ [ (x,y) for x in seq1 for y in seq2]
+
Generators
-----------------------
-Functions where internal state is stored
-{Copy bits of what's new}
+Generators are a special class of functions that simplify
+the task of writing certain kinds of iterators.
+
+XXX {Copy bits of what's new}
+
+Mention 2.5 additions but don't describe them.
-Mention 2.5 additions but don't desribe them.
The itertools module
-----------------------
Small functions and the lambda statement
------------------------
+----------------------------------------------
Built-in functions
------------------------
+----------------------------------------------
-map()
-''''''
+map(), filter(), reduce()
-filter()
-''''''''''
-
-reduce()
-''''''''''''
.. comment
+
Introduction
Idea of FP
Programs built out of functions
More information about the Python-checkins
mailing list