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

In [ ]:

```
def f(y):
return x + y
x = 1
print(f(5))
x = -5
print(f(5))
```

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

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.

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.

In [1]:

```
lines = [' line1 ', 'line2\t', ' ', ' line3 \n ', '\n']
stripped_iter = (line.strip() for line in lines)
```

In [2]:

```
for i in stripped_iter:
print(i, end="")
```

line1line2line3

In [3]:

```
[line.strip() for line in lines]
```

Out[3]:

['line1', 'line2', '', 'line3', '']

In [4]:

```
[line.strip() for line in lines if line.strip() != ""]
```

Out[4]:

['line1', 'line2', 'line3']

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

In [5]:

```
[(x, y, x * y) for x in (1, 2, 3) for y in [1, 2, 3, 4] if x < y]
```

Out[5]:

[(1, 2, 2), (1, 3, 3), (1, 4, 4), (2, 3, 6), (2, 4, 8), (3, 4, 12)]

In [6]:

```
l = []
for x in (1, 2, 3):
for y in [1, 2, 3, 4]:
if x < y:
l.append((x, y, x*y))
l
```

Out[6]:

[(1, 2, 2), (1, 3, 3), (1, 4, 4), (2, 3, 6), (2, 4, 8), (3, 4, 12)]

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

In [ ]:

```
[year for year in range(1890, 1915)];
```

In [ ]:

```
[year for year in range(1890, 1915) if year%4 == 0]
```

In [ ]:

```
[year for year in range(1890, 1915)
if (year%4 == 0 and year%100 != 0) or year%400 == 0]
```

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

```
lambda arguments: expression
```

In [7]:

```
def square(x):
return x * x
square(5)
```

Out[7]:

25

You may define this function wit `lambda`

:

In [8]:

```
square2 = lambda x: x*x
square2(6)
```

Out[8]:

36

In [9]:

```
(lambda x: x**2)(6)
```

Out[9]:

36

A lambda function can have more arguments:

In [10]:

```
expr = lambda a, b, c: a + b*c
expr(2, 4, 4)
```

Out[10]:

18

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})$$

In [11]:

```
l = [1, 5, 8]
list(map(square, l))
```

Out[11]:

[1, 25, 64]

The same with lambda (and list comprehension):

In [12]:

```
list(map(lambda x: x**2, range(5)))
```

Out[12]:

[0, 1, 4, 9, 16]

In [13]:

```
[x**2 for x in range(5)]
```

Out[13]:

[0, 1, 4, 9, 16]

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$$In [14]:

```
map(pow, [0.5, 1, 1.5], [-1, 2, 3])
```

Out[14]:

<map at 0x7ffbec394be0>

In [15]:

```
list(map(pow, [0.5, 1, 1.5], [-1, 2, 3]))
```

Out[15]:

[2.0, 1, 3.375]

In [16]:

```
list(map(pow, [0.5, 1], [-1, 2, 3]))
```

Out[16]:

[2.0, 1]

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

In [17]:

```
x = -4
x if x>0 else -x
```

Out[17]:

4

In [18]:

```
absolute = lambda x: x if x >= 0 else -x
print(absolute(5), absolute(-5))
```

5 5

In [ ]:

```
list(map(lambda x: x if x>=0 else 0, range(-5,5)))
```

One of the advantage of using conditional expressions is that both `if`

and `else`

are necessary, which makes it harder to forget a case.

Bad example:

In [ ]:

```
def ageroup(x):
if x < 8:
return "child"
elif x < 15:
return "adolescent"
elif x >=18:
return "adult"
print(ageroup(16))
```

In [ ]:

```
def ageroup(x):
return "child" if x<8 else ("adolescent"
if x<15 else ("adult" if x>=18 else "INVALID"))
ageroup(16)
```

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$$In [ ]:

```
list(filter(lambda x: x % 2 == 0, range(10)))
```

In [ ]:

```
[x for x in range(10) if x % 2 == 0]
```

In [ ]:

```
list(filter(str.isupper, "aAbBcC"))
```

`zip()`

¶In [ ]:

```
list(zip(['a', 'b', 'c'], (1, 2, 3)))
```

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

In [ ]:

```
any([1,2,0,1])
```

In [ ]:

```
all([1,2,0,1])
```

In [ ]:

```
import math
print([math.cos(i*math.pi) for i in range(3)])
any([math.cos(i*math.pi) == 1.0 for i in range(3)])
```

In [ ]:

```
all([math.cos(i*math.pi) == 1.0 for i in range(3)])
```

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.

In [ ]:

```
from functools import reduce
addition = lambda a, b: a+b
reduce(addition, [1, 2, 3, 4])
```

In [ ]:

```
reduce(addition, [4])
```

In [ ]:

```
reduce(addition, [], 0)
```

In [ ]:

```
division = lambda a, b: a/b
reduce(division, [2, 3, 4], 1)
```

In [ ]:

```
1/24
```

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

In [ ]:

```
greater = lambda x, y: x if x > y else y
reduce(greater, [0, 1, 10, -10, 2], float("-inf"))
```

In [ ]:

```
smaller = lambda x, y: x if x < y else y
reduce(smaller, [0, 1, 10, -10, 2], float("inf"))
```

In [ ]:

```
def dot(a, b):
return sum(map(lambda x, y: x*y, a, b))
dot([0.5, 1, 1.5], [-1, 1, -1])
```

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:

In [ ]:

```
def inner(a, b, g=lambda x, y: x*y, f=sum):
return f(map(g, a, b))
inner([0.5, 1, 1.5], [-1, 1, -1])
```

In [ ]:

```
inner("abc", [1,3,2], f=list)
```

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

In [ ]:

```
def inner(a, b, g=lambda x, y: x*y, f=lambda a, b: a+b, i=0):
return reduce(f, map(g, a, b), i)
inner([0.5, 1, 1.5], [-1, 1, -1])
```

In [ ]:

```
inner("abc", [1,3,2], i='')
```

In [ ]:

```
inner([1,11,4], [3,2,6], g=min, f=max, i=float("-Inf"))
```

In [ ]:

```
inner([1,11,4], [3,2,6], g=max, f=min, i=float("Inf"))
```

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:

In [ ]:

```
or_ = lambda a, b: a or b
and_ = lambda a, b: a and b
```

In [ ]:

```
from operator import or_, and_
```

In [ ]:

```
inner([0,0,1,1], [0,1,0,1], g=or_, f=and_, i=1)
```

In [ ]:

```
inner([0,0,1,1], [0,1,0,1], g=and_, f=or_, i=0)
```

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.

In [19]:

```
from itertools import permutations
s = 0
for x in permutations(list(range(8))):
if all([i == j or abs(i - j) != abs(x[i] - x[j])
for i in range(8) for j in range(8)]):
s += 1
print(s)
```

92

In [20]:

```
for x in permutations(list(range(8))):
if all([i == j or abs(i - j) != abs(x[i] - x[j])
for i in range(8) for j in range(8)]):
print(x)
```

In [ ]:

```
```