********************************

  Functional Programming HOWTO

********************************

:Author: A. M. Kuchling

:Release: 0.31

(This is a first draft.  Please send comments/error reports/suggestions to

amk@amk.ca.)

In this document, we'll take a tour of Python's features suitable for

implementing programs in a functional style.  After an introduction to the

concepts of functional programming, we'll look at language features such as

:term:`iterator`\s and :term:`generator`\s and relevant library modules such as

:mod:`itertools` and :mod:`functools`.

Introduction

============

This section explains the basic concept of functional programming; if you're

just interested in learning about Python language features, skip to the next

section.

Programming languages support decomposing problems in several different ways:

* Most programming languages are **procedural**: programs are lists of

  instructions that tell the computer what to do with the program's input.  C,

  Pascal, and even Unix shells are procedural languages.

* In **declarative** languages, you write a specification that describes the

  problem to be solved, and the language implementation figures out how to

  perform the computation efficiently.  SQL is the declarative language you're

  most likely to be familiar with; a SQL query describes the data set you want

  to retrieve, and the SQL engine decides whether to scan tables or use indexes,

  which subclauses should be performed first, etc.

* **Object-oriented** programs manipulate collections of objects.  Objects have

  internal state and support methods that query or modify this internal state in

  some way. Smalltalk and Java are object-oriented languages.  C++ and Python

  are languages that support object-oriented programming, but don't force the

  use of object-oriented features.

* **Functional** programming decomposes a problem into a set of functions.

  Ideally, functions only take inputs and produce outputs, and don't have any

  internal state that affects the output produced for a given input.  Well-known

  functional languages include the ML family (Standard ML, OCaml, and other

  variants) and Haskell.

The designers of some computer languages choose to emphasize one

particular approach to programming.  This often makes it difficult to

write programs that use a different approach.  Other languages are

multi-paradigm languages that support several different approaches.

Lisp, C++, and Python are multi-paradigm; you can write programs or

libraries that are largely procedural, object-oriented, or functional

in all of these languages.  In a large program, different sections

might be written using different approaches; the GUI might be

object-oriented while the processing logic is procedural or

functional, for example.

In a functional program, input flows through a set of functions. Each function

operates on its input and produces some output.  Functional style discourages

functions with side effects that modify internal state or make other changes

that aren't visible in the function's return value.  Functions that have no side

effects at all are called **purely functional**.  Avoiding side effects means

not using data structures that get updated as a program runs; every function's

output must only depend on its input.

Some languages are very strict about purity and don't even have assignment

statements such as ``a=3`` or ``c = a + b``, but it's difficult to avoid all

side effects.  Printing to the screen or writing to a disk file are side

effects, for example.  For example, in Python a ``print`` statement or a

``time.sleep(1)`` both return no useful value; they're only called for their

side effects of sending some text to the screen or pausing execution for a

second.

Python programs written in functional style usually won't go to the extreme of

avoiding all I/O or all assignments; instead, they'll provide a

functional-appearing interface but will use non-functional features internally.

For example, the implementation of a function will still use assignments to

local variables, but won't modify global variables or have other side effects.

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, and programs

consist of making the right set of state changes.  Functional programming wants

to avoid state changes as much as possible and works with data flowing between

functions.  In Python you might combine the two approaches by writing functions

that take and return instances representing objects in your application (e-mail

messages, transactions, etc.).

Functional design may seem like an odd constraint to work under.  Why should you

avoid objects and side effects?  There are theoretical and practical advantages

to the functional style:

* Formal provability.

* Modularity.

* Composability.

* Ease of debugging and testing.

Formal provability

------------------

A theoretical benefit is that it's easier to construct a mathematical proof that

a functional program is correct.

For a long time researchers have been interested in finding ways to

mathematically prove programs correct.  This is different from testing a program

on numerous inputs and concluding that its output is usually correct, or reading

a program's source code and concluding that the code looks right; the goal is

instead a rigorous proof that a program produces the right result for all

possible inputs.

The technique used to prove programs correct is to write down **invariants**,

properties of the input data and of the program's variables that are always

true.  For each line of code, you then show that if invariants X and Y are true

**before** the line is executed, the slightly different invariants X' and Y' are

true **after** the line is executed.  This continues until you reach the end of

the program, at which point the invariants should match the desired conditions

on the program's output.

Functional programming's avoidance of assignments arose because assignments are

difficult to handle with this technique; assignments can break invariants that

were true before the assignment without producing any new invariants that can be

propagated onward.

Unfortunately, proving programs correct is largely impractical and not relevant

to Python software. Even trivial programs require proofs that are several pages

long; the proof of correctness for a moderately complicated program would be

enormous, and few or none of the programs you use daily (the Python interpreter,

your XML parser, your web browser) could be proven correct.  Even if you wrote

down or generated a proof, there would then be the question of verifying the

proof; maybe there's an error in it, and you wrongly believe you've proved the

program correct.

Modularity

----------

A more practical benefit of functional programming is that it forces you to

break apart your problem into small pieces.  Programs are more modular as a

result.  It's easier to specify and write a small function that does one thing

than a large function that performs a complicated transformation.  Small

functions are also easier to read and to check for errors.

Ease of debugging and testing 

-----------------------------

Testing and debugging a functional-style program is easier.

Debugging is simplified because functions are generally small and clearly

specified.  When a program doesn't work, each function is an interface point

where you can check that the data are correct.  You can look at the intermediate

inputs and outputs to quickly isolate the function that's responsible for a bug.

Testing is easier because each function is a potential subject for a unit test.

Functions don't depend on system state that needs to be replicated before

running a test; instead you only have to synthesize the right input and then

check that the output matches expectations.

Composability

-------------

As you work on a functional-style program, you'll write a number of functions

with varying inputs and outputs.  Some of these functions will be unavoidably

specialized to a particular application, but others will be useful in a wide

variety of programs.  For example, a function that takes a directory path and

returns all the XML files in the directory, or a function that takes a filename

and returns its contents, can be applied to many different situations.

Over time you'll form a personal library of utilities.  Often you'll assemble

new programs by arranging existing functions in a new configuration and writing

a few functions specialized for the current task.

Iterators

=========

I'll start by looking at a Python language feature that's an important

foundation for writing functional-style programs: iterators.

An iterator is an object representing a stream of data; this object 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 :func:`iter` function takes an arbitrary object and tries to return

an iterator that will return the object's contents or elements, raising

:exc:`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.  An object is called an **iterable** object if you can get an

iterator for it.

You can experiment with the iteration interface manually:

    >>> L = [1,2,3]

    >>> it = iter(L)

    >>> print it

    <...iterator object at ...>

    >>> 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 :func:`list` or

:func:`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 = iterator

    >>> a,b,c

    (1, 2, 3)

Built-in functions such as :func:`max` and :func:`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 ``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 :func:`iter` on a dictionary returns an iterator that will loop over the

dictionary's keys:

.. not a doctest since dict ordering varies across Pythons

::

    >>> 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

    Apr 4

    Jun 6

    Jul 7

    Jan 1

    May 5

    Nov 11

    Dec 12

    Oct 10

Note that the order is essentially random, because it's based on the hash

ordering of the objects in the dictionary.

Applying ``iter()`` to a dictionary always loops over the keys, but dictionaries

have methods that return other iterators.  If you want to iterate over keys,

values, or key/value pairs, you can explicitly call the ``iterkeys()``,

``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:

    >>> 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 ``readline()`` method until there

are no more lines in the file.  This means you can read each line of a file like

this::

    for line in file:

        # do something for each line

        ...

Sets can take their contents from an iterable and let you iterate over the set's

elements::

    S = set((2, 3, 5, 7, 11, 13))

    for i in S:

        print i

Generator expressions and list comprehensions

=============================================

Two common operations on an iterator's output are 1) performing some operation

for every element, 2) selecting a subset of elements that meet some condition.

For example, given a list of strings, you might want to strip off trailing

whitespace from each line or extract all the strings containing a given

substring.

List comprehensions and generator expressions (short form: "listcomps" and

"genexps") are a concise notation for such operations, borrowed from the

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', ...]

    # 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]

You can select only certain elements by adding an ``"if"`` condition::

    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

return an iterator that computes the values as necessary, not needing to

materialize all the values at once.  This means that list comprehensions aren't

useful if you're working with iterators that return an infinite stream or a very

large amount of data.  Generator expressions are preferable in these situations.

Generator expressions are surrounded by parentheses ("()") and list

comprehensions are surrounded by square brackets ("[]").  Generator expressions

have the form::

    ( expression for expr in sequence1 

                 if condition1

                 for expr2 in sequence2

                 if condition2

                 for expr3 in sequence3 ...

                 if condition3

                 for exprN in sequenceN

                 if conditionN )

Again, for a list comprehension only the outside brackets are different (square

brackets instead of parentheses).

The elements of the generated output will be the successive values of

``expression``.  The ``if`` clauses are all optional; if present, ``expression``

is only evaluated and added to the result when ``condition`` is true.

Generator expressions always have to be written inside parentheses, but the

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())

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``.

To put it another way, a list comprehension or generator expression is

equivalent to the following Python code::

    for expr1 in sequence1:

        if not (condition1):

            continue   # Skip this element

        for expr2 in sequence2:

            if not (condition2):

                continue    # Skip this element

            ...

            for exprN in sequenceN:

                 if not (conditionN):

                     continue   # Skip this element

                 # Output the value of 

                 # the expression.

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:

.. 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)]

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

==========

Generators are a special class of functions that simplify the task of writing

iterators.  Regular functions compute a value and return it, but generators

return an iterator that returns a stream of values.

You're doubtless familiar with how regular function calls work in Python or C.

When you call a function, it gets a private namespace where its local variables

are created.  When the function reaches a ``return`` statement, the local

variables are destroyed and the value is returned to the caller.  A later call

to the same function creates a new private namespace and a fresh set of local

variables. But, what if the local variables weren't thrown away on exiting a

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:

.. testcode::

    def generate_ints(N):

        for i in range(N):

            yield i

Any function containing a ``yield`` keyword is a generator function; this is

detected by Python's :term:`bytecode` compiler which compiles the function

specially as a result.

When you call a generator function, it doesn't return a single value; instead it

returns a generator object that supports the iterator protocol.  On executing

the ``yield`` expression, the generator outputs the value of ``i``, similar to a

``return`` statement.  The big difference between ``yield`` and a ``return``

statement is that on reaching a ``yield`` the generator's state of execution is

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:

    >>> gen = generate_ints(3)

    >>> gen

    <generator object at ...>

    >>> gen.next()

    0

    >>> gen.next()

    1

    >>> gen.next()

    2

    >>> gen.next()

    Traceback (most recent call last):

      File "stdin", line 1, in ?

      File "stdin", line 2, in generate_ints

    StopIteration

You could equally write ``for i in generate_ints(5)``, or ``a,b,c =

generate_ints(3)``.

Inside a generator function, the ``return`` statement can only be used without a

value, and signals the end of the procession of values; after executing a

``return`` the generator cannot return any further values.  ``return`` with a

value, such as ``return 5``, is a syntax error inside a generator function.  The

end of the generator's results can also be indicated by raising

``StopIteration`` manually, or by just letting the flow of execution fall off

the bottom of the function.

You could achieve the effect of generators manually by writing your own class

and storing all the local variables of the generator as instance variables.  For

example, returning a list of integers could be done by setting ``self.count`` to

0, and having the ``next()`` method increment ``self.count`` and return it.

However, for a moderately complicated generator, writing a corresponding class

can be much messier.

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. ::

    # A recursive generator that generates Tree leaves in in-order.

    def inorder(t):

        if t:

            for x in inorder(t.left):

                yield x

            yield t.label

            for x in inorder(t.right):

                yield x

Two other examples in ``test_generators.py`` produce solutions for the N-Queens

problem (placing N queens on an NxN chess board so that no queen threatens

another) and the Knight's Tour (finding a route that takes a knight to every

square of an NxN chessboard without visiting any square twice).

Passing values into a generator