## page was renamed from Tips/FunctionalProgramming
== Python Functional Programming for Mathematicians ==


This tutorial discusses some techniques of functional programming that might be of interest to mathematicians or people who use Python for scientific computation. We first start off with a brief overview of procedural and object-oriented programming, and then discuss functional programming techniques. The tutorial concludes with some resources on detailed information on functional programming using Python. This tutorial is also available at [[http://mvngu.wordpress.com/2009/12/12/python-functional-programming-for-mathematicians/|Wordpress]].


=== Styles of programming ===


Python supports several styles of programming. You could program in the procedural style by writing a program as a list of instructions. Say you want to implement addition and multiplication over the integers. A procedural program to do so would be as follows:

{{{
sage: def add_ZZ(a, b):
....:     return a + b
sage: def mult_ZZ(a, b):
....:     return a * b
sage: add_ZZ(2, 3)
5
sage: mult_ZZ(2, 3)
6
}}}

The Python module `operator` defines several common arithmetic and comparison operators as named functions. Addition is defined in the built-in function `operator.add()` and multiplication is defined in `operator.mul()`. The above example can be worked through as follows:

{{{
sage: from operator import add, mul
sage: add(2, 3)
5
sage: mul(2, 3)
6
}}}

Another common style of programming is called object-oriented programming. Think of an object as code that encapsulates both data and functionalities. You could encapsulate integer addition and multiplication as in the following object-oriented implementation:

{{{
sage: class MyInteger:
....:     def __init__(self):
....:         self.cardinality = "infinite"
....:     def add(self, a, b):
....:         return a + b
....:     def mult(self, a, b):
....:         return a * b
....:     
sage: myZZ = MyInteger()
sage: myZZ.cardinality
'infinite'
sage: myZZ.add(2, 3)
5
sage: myZZ.mult(2, 3)
6
}}}


=== Functional programming using map() ===


Functional programming is yet another style of programming in which a program is decomposed into various functions. The Python built-in functions [[https://docs.python.org/library/functions.html#map|map()]], [[https://docs.python.org/library/functions.html#reduce|reduce()]] allow you to program in the functional style. The function

{{{
map(func, seq1, seq2, ...)
}}}

takes a function `func` and one or more sequences, and apply `func` to elements of those sequences. In particular, you end up with an iterable, that will 
 generate the list:

{{{
[func(seq1[0], seq2[0], ...), func(seq1[1], seq2[1], ...), ...]
}}}

In many cases, using `map()` allows you to express the logic of your program in a concise manner without using list comprehension. For example, say you have two lists of integers and you want to add them element-wise. A list comprehension to accomplish this would be as follows:

{{{
sage: A = [1, 2, 3, 4]
sage: B = [2, 3, 5, 7]
sage: [a + b for a, b in zip(A, B)]
[3, 5, 8, 11]
}}}

Alternatively, you could use the Python built-in addition function `operator.add()` together with `map()` to achieve the same result:

{{{
sage: list(map(add, A, B))
[3, 5, 8, 11]
}}}

An advantage of `map()` is that you do not need to explicitly define a `for` loop as was done in the above list comprehension.


=== Define small functions using lambda ===


There are times when you want to write a short, one-liner function. You could re-write the above addition function as follows:

{{{
sage: def add_ZZ(a, b): return a + b
....:
}}}

Or you could use a [[https://docs.python.org/reference/expressions.html#lambda|lambda]] statement to do the same thing in a much clearer style. The above addition and multiplication functions could be written using `lambda` as follows:

{{{
sage: add_ZZ = lambda a, b: a + b
sage: mult_ZZ = lambda a, b: a * b
sage: add_ZZ(2, 3)
5
sage: mult_ZZ(2, 3)
6
}}}

Things get more interesting once you combine `map()` with the `lambda` statement. As an exercise, you might try to write a simple function that implements a constructive algorithm for the [[https://en.wikipedia.org/wiki/Chinese_remainder_theorem|Chinese Remainder Theorem]]. You could use list comprehension together with `map()` and `lambda` as shown below. Here, the parameter `A` is a list of integers and `M` is a list of moduli.

{{{
sage: def crt(A, M):
....:     Mprod = prod(M)
....:     Mdiv = list(map(lambda x: Integer(Mprod / x), M))
....:     X = map(inverse_mod, Mdiv, M)
....:     x = sum(A[i]*X[i]*Mdiv[i] for i in range(len(A)))
....:     return mod(x, Mprod).lift()
sage: A = [2, 3, 1]
sage: M = [3, 4, 5]
sage: x = crt(A, M); x
11
sage: mod(x, 3)
2
sage: mod(x, 4)
3
sage: mod(x, 5)
1
}}}

To produce a random matrix over a ring, say `ZZ`, you could start by defining a matrix space and then obtain a random element of that matrix space:

{{{
sage: MS = MatrixSpace(ZZ, nrows=5, ncols=3)
sage: MS.random_element()
[ 6  1  0]
[-1  5  0]
[-1  0  0]
[-5  0  1]
[ 1 -1 -3]
}}}

Or you could use the function `random_matrix()`:

{{{
sage: random_matrix(ZZ, nrows=5, ncols=3)
[  2 -50   0]
[ -1   0  -6]
[ -4  -1  -1]
[  1   1   3]
[  2  -1  -1]
}}}

The next example uses `map()` to construct a list of random integer matrices:

{{{
sage: rows = [randint(1, 10) for i in range(10)]
sage: cols = [randint(1, 10) for i in range(10)]
sage: rings = [ZZ]*10
sage: M = list(map(random_matrix, rings, rows, cols))
sage: M[0]
[ -1  -3  -1 -37   1  -1  -4   5]
[  2   1   1   5   2   1  -2   1]
[ -1   0  -4   0  -2   1  -2   1]
}}}

If you want more control over the entries of your matrices than the `random_matrix()` function permits, you could use `lambda` together with `map()` as follows:

{{{
sage: rand_row = lambda n: [randint(1, 10) for i in range(n)]
sage: rand_mat = lambda nrows, ncols: [rand_row(ncols) for i in range(nrows)]
sage: matrix(rand_mat(5, 3))
[ 2  9 10]
[ 8  8  9]
[ 6  7  6]
[ 9  2 10]
[ 2  6  2]
sage: rows = [randint(1, 10) for i in range(10)]
sage: cols = [randint(1, 10) for i in range(10)]
sage: M = map(rand_mat, rows, cols)
sage: M = list(map(matrix, M))
sage: M[0]
[ 9  1  5  2 10 10  1]
[ 3  4  3  7  4  3  7]
[ 4  8  7  6  4  2 10]
[ 1  6  3  3  6  2  1]
[ 5  5  2  6  4  3  4]
[ 6  6  2  9  4  5  1]
[10  2  5  5  7 10  4]
[ 2  7  3  5 10  8  1]
[ 1  5  1  7  8  8  6]
}}}


=== Reducing a sequence to a value ===


The function [[http://docs.python.org/library/functions.html#reduce|reduce()]] takes a function of two arguments and apply it to a given sequence to reduce that sequence to a single value. The function [[http://docs.python.org/library/functions.html#sum|sum()]] is an example of a `reduce()` function. The following sample code uses `reduce()` and the built-in function `operator.add()` to add together all integers in a given list. This is followed by using `sum()` to accomplish the same task:

{{{
sage: L = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
sage: reduce(add, L)
55
sage: sum(L)
55
}}}

In the following sample code, we consider a vector as a list of real numbers. The [[http://en.wikipedia.org/wiki/Dot_product|dot product]] is then implemented using the functions `operator.add()` and `operator.mul()`, in conjunction with the built-in Python functions `reduce()` and `map()`. We then show how `sum()` and `map()` could be combined to produce the same result.

{{{
sage: U = [1, 2, 3]
sage: V = [2, 3, 5]
sage: reduce(add, map(mul, U, V))
23
sage: sum(map(mul, U, V))
23
}}}

Or you could use Sage's built-in support for the dot product:

{{{
sage: u = vector(U)
sage: v = vector(V)
sage: u.dot_product(v)
23
}}}

Here is an implementation of the Chinese Remainder Theorem without using `sum()` as was done previously. The version below uses `operator.add()` and defines `mul3()` to multiply three numbers instead of two.

{{{
sage: def crt(A, M):
....:     Mprod = prod(M)
....:     Mdiv = map(lambda x: Integer(Mprod / x), M)
....:     X = map(inverse_mod, Mdiv, M)
....:     mul3 = lambda a, b, c: a * b * c
....:     x = reduce(add, map(mul3, A, X, Mdiv))
....:     return mod(x, Mprod).lift()
....: 
sage: A = [2, 3, 1]
sage: M = [3, 4, 5]
sage: x = crt(A, M); x
11
}}}


=== Filtering with filter() ===


The Python built-in function `filter()` takes a function of one argument and a sequence. It then returns an iterable of all those items from the given sequence such that any item in the new list results in the given function returning `True`. In a sense, you are filtering out all items that satisfies some condition(s) defined in the given function. For example, you could use `filter()` to filter out all primes between 1 and 50, inclusive.

{{{
sage: list(filter(is_prime, [1..50]))
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]
}}}

For a given positive integer `n`, the [[https://en.wikipedia.org/wiki/Euler%27s_totient_function|Euler phi function]] counts the number of integers `a`, with `1 <= a <= n`, such that `gcd(a, n) = 1`. You could use list comprehension to obtain all such `a`'s when `n = 20`:

{{{
sage: [k for k in range(1, 21) if gcd(k, 20) == 1]
[1, 3, 7, 9, 11, 13, 17, 19]
}}}

A functional approach is to use `lambda` to define a function that determines whether or not a given integer is relatively prime to `20`. Then you could use `filter()` instead of list comprehension to obtain all the required `a`'s.

{{{
sage: is_coprime = lambda k: gcd(k, 20) == 1
sage: list(filter(is_coprime, range(1, 21)))
[1, 3, 7, 9, 11, 13, 17, 19]
}}}

The function `primroots()` defined below returns all primitive roots modulo a given positive prime integer `p`. It uses `filter()` to obtain a list of integers between `1` and `p - 1`, inclusive, each integer in the list being relatively prime to the order of `(\mathbf{Z} / p\mathbf{Z})^{\ast}`.

{{{
sage: def primroots(p):
....:     g = primitive_root(p)
....:     znorder = p - 1
....:     is_coprime = lambda x: gcd(x, znorder) == 1
....:     good_odd_integers = filter(is_coprime, [1..p-1, step=2])
....:     return sorted(power_mod(g, k, p) for k in good_odd_integers)
sage: primroots(3)
[2]
sage: primroots(5)
[2, 3]
sage: primroots(7)
[3, 5]
sage: primroots(11)
[2, 6, 7, 8]
sage: primroots(13)
[2, 6, 7, 11]
sage: primroots(17)
[3, 5, 6, 7, 10, 11, 12, 14]
sage: primroots(23)
[5, 7, 10, 11, 14, 15, 17, 19, 20, 21]
sage: primroots(29)
[2, 3, 8, 10, 11, 14, 15, 18, 19, 21, 26, 27]
sage: primroots(31)
[3, 11, 12, 13, 17, 21, 22, 24]
}}}


=== Further resources ===


This has been a rather short introduction to functional programming with Python. The Python standard documentation has a list of [[http://docs.python.org/library/functions.html|built-in functions]], many of which are useful in functional programming. For example, you might want to read up on [[http://docs.python.org/library/functions.html#all|all()]], [[http://docs.python.org/library/functions.html#any|any()]], [[http://docs.python.org/library/functions.html#max|max()]], [[http://docs.python.org/library/functions.html#min|min()]], and [[http://docs.python.org/library/functions.html#zip|zip()]]. The Python module [[http://docs.python.org/library/operator.html|operator]] has numerous built-in arithmetic and comparison operators, each operator being implemented as a function whose name reflects its intended purpose. For arithmetic and comparison operations, it is recommended that you consult the `operator` module to determine if there is a built-in function that satisfies your requirement. The module [[http://docs.python.org/library/itertools.html|itertools]] has numerous built-in functions to efficiently process sequences of items. The functions `filter()`, `map()` and `zip()` have their counterparts in `itertools` as `itertools.ifilter()`, `itertools.imap()` and `itertools.izip()`.

Another useful resource for functional programming in Python is the [[http://docs.python.org/howto/functional.html|Functional Programming HOWTO]] by A. M. Kuchling. Steven F. Lott's book [[http://homepage.mac.com/s_lott/books/python.html#book-python|Building Skills in Python]] has a chapter on [[http://homepage.mac.com/s_lott/books/python/html/p02/p02c10_adv_seq.html|Functional Programming using Collections]]. See also the chapter [[http://www.diveintopython3.org/functional_programming/index.html|Functional Programming]] from Mark Pilgrim's book [[http://www.diveintopython3.org|Dive Into Python]].

You might also want to consider experimenting with [[http://www.haskell.org|Haskell]] for expressing mathematical concepts. For an example of Haskell in expressing mathematical algorithms, see J. Gibbons' article [[http://www.maa.org/pubs/monthly_apr06_toc.html|Unbounded Spigot Algorithms for the Digits of Pi]] in the American Mathematical Monthly.