Functional Programming¶

In connection with functional programming (see also wikipedia) we start with a few words about how do we decompose a program, that is about the programming paradigms. There are some main types of them, but several programming languages cannot be strictly classified into one paradigm, but rather include features from several paradigms, like Python.

• Imperative in which you instruct the machine what to do, how to change its state.
• Procedural where your programs are lists of instructions which are grouped into procedures (e.g. C, FORTRAN, bash).
• Object-oriented where you manipulate objects having internal state which can be queried or modified by methods. (e.g. Java)
• Declarative where you describe the problem, and the program figures out how to compute it.
• Logic which mainly based on formal logic. (e.g. Prolog)
• Functional in which the desired result is declared as the value of a series of function calls. (e.g. Haskell, Standard ML, Lisp)

In the functional paradigm any function $f(x)$ results the same value for the same $x$.

This is not the case if you have variables and change them while the program is running. Look at the following function (result depends on $x$).

If you avoid those, then the python functions will be actual mathematical functions), otherwise those are sequence of commands. Hence the name functional programming.

History¶

Originally, Guido van Rossum wanted to drop out the main functional programming tools from the core of Python 3 into a modul, because python has list comprehension instead. But after a strong lobby of functional programming fanatics Rossum kept the lambda, map() and filter() in the core and moved reduce() to the functools package.

The theoretical and practical advantages to the functional style are

• formal provability of the correcness of code,
• easier debugging and testing as there are no states, so no side effects, no mutable objects,
• parallel programmability, modularity, composability.

List comprehension and generator expression¶

The first and most important functional programming element of Python is the iterator what we introduced before. Running through the elements of an iterable object and performing an operation on them or selecting some of them by a condition are the most important tasks in a functional programming approach. In Python one may use list comprehension or generator expression for these tasks. List comprehension gives back a list, generator expression an iterator. The only difference is that we put the former in [] and the latter in ().

Example: After reading the lines from a file into a list of strings, remove the white space characters from the beginning and end of each line, using the .strip() method.

The general form of the generator expression:

(expression for expr1 in seq1
if condition1
for expr2 in seq2
if condition2
...
for exprN in seqN
if conditionN )

The list comprehension is the same except that [] is used instead of ().

These are equivalent to the next code. Mind the position of the main expression:

for expr1 in seq1:
if not (condition1):
continue
for expr2 in seq2:
if not (condition2):
continue
...
for exprN in seqN:
if not (conditionN):
continue
expression

Exercise: Print out the leap years between 1890 and 1914!

Lambda functions¶

Some simple functions can be written shorter with lambda. Traditional function, the form of it is

lambda arguments: expression

You may define this function wit lambda:

A lambda function can have more arguments:

map()¶

The map applies a given function for every element of an iterable object and returns an iterator. Describing with a math formula: $$\mathop{\mathrm{map}}:(A\mapsto B)\times A^n\mapsto B^n\ \ (n\in \mathbb{N})$$

The same with lambda (and list comprehension):

You can use a multi-variate function as the first argument. If $f$ has more variable, then you have to provide more iterables.

$$\mathop{\mathrm{map}}: (A \mapsto X)\times A^n \mapsto X^n$$$$\mathop{\mathrm{map}}: (A\times B \mapsto X) \times A^n\times B^n \mapsto X^n$$$$\mathop{\mathrm{map}}: (A\times B \times C\mapsto X)\times A^n\times B^n\times C^n \mapsto X^n$$$$\vdots$$

Conditional expressions¶

We may use conditional expressions in lambda functions. Let us recall that the general form of a conditional expression is

expression if condition else expression_when_condition_false

One of the advantage of using conditional expressions is that both if and else are necessary, which makes it harder to forget a case.

filter()¶

The filter makes an iterator from an iterable object according to a condition given as a logical function.

The logical function should be $A\mapsto \{True, False\}$.

$$\mathrm{filter} : (A\mapsto \{True, False\})\times A^n\mapsto A^m \text{ ahol } m\leq n$$

any() és all()¶

According to the quantifiers the any() and all() built-ins look at the truth values of an iterable object, and any() returns True if any element in the iterable is true, and all() returns True if all of the elements are true.

reduce()¶

The functools.reduce(*function*, *iterable*[, *initial*]) cumulatively performs a bi-variate function on all the iterable’s elements. functools.reduce() takes the first two elements a and b returned by the iterator and calculates func(a, b), then calculates func(func(a, b), c) with the third element, and continues until the iterable is exhausted. If an initial value is given, then the calculation starts with func(initial, a). If only one element is offered by the iterator, then that will be the result. If no element is offered by the iteratot then a TypeError exception is raised. So always use an initial value if this may happen.

The paradigm of accumulation can be done with this. Finding the extrema can be one application.

Two examples¶

Generalized inner product¶

The dot product can be implemented functionally:

In general, expressions of the form $f(g(x_1, y_1), g(x_2, y_2), \ldots g(x_n, y_n))$ can be considered a generalized inner product.

It is easy to implement functionally:

Or with a bi-variate, asssociative $g$ function via a reduce:

Or do something similar with the 'or's of 'and's or with the 'and's of 'or's. For this we need a function version of the operations or and and. We may construct these functions or we may use the operations modul:

The eight queens puzzle¶

The eight queens puzzle is the problem of placing eight chess queens on an $8\times8$ chessboard so that no two queens threaten each other. A solution requires that no two queens share the same row, column, or diagonal. How many solutions are there? List them!

Two queens in the line $i$ and $j$ ($i\neq j$) does not threaten each other if $\mathrm{abs}(i - j)\neq\mathrm{abs}(x[i] - x[j])$. Listing the permutations we import the function permutations from the itertools module. This iterates through the permutations of the elements.