Functional Programming

Functional programming is a programming paradigm where you avoid the assignment of any variable because that changes the internal state of the program. In the functional paradigm any function $f(x)$ results the same 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 [29]:
def f(y):
    return x+y

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 this out from Python 3, because python has list comprehension instead. The Functional programming fanatics lobbied to keep the lambda, map() and filter() but the reduce() was moved to the functools package.

Lambda functions

Some simple functions can be written shorter with lambda. Traditional function:

In [30]:
def square(x):
    return x * x
def cube(x):
    return x*x*x

f = square

Instead you can make a function object and call it with paranthesis, like you would call a function.

In [31]:
square = lambda x: x*x
print square(6)

(lambda x: x**3)(8)

A lambda function can have more arguments:

In [32]:
addition = lambda a, b: a + b
addition(2, 4)


The map applies a given function for every element of a list and returns the results in a list. In formula:

$$map(f, L) = \{f(x) \mid x\in L\}$$

If $f: A\mapsto B$ then $map:(A\mapsto B) \times A^n\mapsto B^n$ ($n\in \mathbb{N}$)

In [33]:
L = [1, 5, 8]
print map(square, L)
[1, 25, 64]

The same with lambda (and list comprehension):

In [34]:
print map(lambda x: x**2, range(5))

[x**2 for x in range(5)]
[0, 1, 4, 9, 16]
[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 lists to iterate on. map takes the arguments of the function from the lists, one from each list.

Formally: $$map: (A \mapsto X), A^n \mapsto X^n$$ $$map: (A\times B \mapsto X), A^n, B^n \mapsto X^n$$ $$map: (A\times B \times C\mapsto X), A^n, B^n, C^n \mapsto X^n$$ $$\vdots$$

In [35]:
map(pow, [0.5, 1, 1.5], [-1, 2, 3])
[2.0, 1, 3.375]

Conditions (if)

You can use only one line of code inside a lambda, but you can use if, too.

"expression in the True case" if condition else "expression in the False case"

In [36]:
absolute = lambda x: x if x>=0 else -x

print absolute(5)
print absolute(-5)
In [37]:
map(lambda x: x if x>=0 else 0, range(-5,5))
[0, 0, 0, 0, 0, 0, 1, 2, 3, 4]

This is really just an other syntax for the same if. This itself has nothing to do with functional or traditional (procedural) programming.

One difference is that you have to do the if and else in pair, which makes it harder to forget a case.

Bad example:

In [38]:
def ageroup(x):
    if x < 8:
        return "child"
    elif x < 15:
        return "adolescent"
    elif x >=18:
        return "adult"

print ageroup(16)
In [39]:
def ageroup(x):
    return "child" if x<8 else ("adolescent" if x<15 else ("adult" if x>=18 else "INVALID"))

print ageroup(16)


The filter makes a sublist according to a condition given as a logical function.

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

$$filter : (A\mapsto \{True, False\})\times A^n\mapsto A^m \text{ where } m\leq n$$
In [40]:
print filter(lambda x: x % 2 == 0, range(10))
[0, 2, 4, 6, 8]
In [41]:
print filter(str.isupper, "aAbBcC")


reduce applies a bi-variate function and accumulates elements from a given list, with an optional initial value. In code:

reduce(*function*, *iterable*[, *initial*])

The bi-variate function should be $A\times B\mapsto A$ and the iterable is of $B$, the initial value is the element of $A$. The default initial value is $0$.

For a tuple $(a, b, c)$ and initial value $x$ the reduce would result this:

$$reduce(f, (a,b,c), x) = f(f(f(x, a), b), c)$$
In [42]:
addition = lambda a, b: a+b
print reduce(addition, [1, 2, 3, 4])
print reduce(addition, [1, 2, 3, 4], 0)
print reduce(addition, [1, 2, 3, 4], 3.14)
In [43]:
division = lambda a, b: a/b
print reduce(division, [1, 2, 3, 4], 1.0)
print 1/24.0

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

In [44]:
print reduce(max, [0,1,10,-10, 2], float("-inf"))
print reduce(min, [0,1,10,-10, 2], float("inf"))

Or an even tackier solution:

In [45]:
print reduce(lambda x, y: x if x > y else y, [0,1,10,-10, 2], float("-inf"))


The dot product can be implemented functionally:

In [46]:
def dot(a, b):
    return sum(map(lambda x, y: x*y, a, b))
print 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 [47]:
def inner(a, b, g=lambda x, y: x*y, f=sum):
    return f(map(g, a, b))

print inner([0.5, 1, 1.5], [-1, 1, -1])
print inner("abc", [1,3,2], f=list)
['a', 'bbb', 'cc']

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

In [48]:
def inner_2(a, b, g=lambda x, y: x*y, f=lambda a, b: a+b, i=0):
    return reduce(f, map(g, a, b), i)

print inner_2([0.5, 1, 1.5], [-1, 1, -1])
print inner_2("abc", [1,3,2], i='')
In [ ]: