Differences between revisions 2 and 3
Revision 2 as of 2009-12-12 23:06:08
Size: 9157
Editor: Minh Nguyen
Comment: typo fixes
Revision 3 as of 2009-12-12 23:08:21
Size: 9160
Editor: Minh Nguyen
Comment:
Deletions are marked like this. Additions are marked like this.
Line 183: Line 183:
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}$. 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}$.

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. Along the way, we briefly review Python's built-in support for functional programming, including filter(), lambda, map() and reduce(). The tutorial concludes with some resources on detailed information on functional programming using Python.

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

Another common style of programming is called object-oriented programming. Think of an object as code that encapsulates both data and functionalities. The above procedural program could be implemented in the object-oriented style as follows:

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: ZZ = MyInteger()
sage: ZZ.cardinality
'infinite'
sage: ZZ.add(2, 3)
5
sage: ZZ.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 map(), reduce() and filter() 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 a list like so:

[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[i] + B[i] for i in xrange(len(A))]
[3, 5, 8, 11]

Alternatively, you could use the addition function add_ZZ() defined earlier together with map() to achieve the same result:

sage: map(add_ZZ, A, B)
[3, 5, 8, 11]

An advantage of map() is that you don't 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 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 = lambda a, b: a + b
sage: mult = lambda a, b: a * b
sage: add(2, 3)
5
sage: mult(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 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 = map(lambda x: Integer(Mprod / x), M)
....:     X = map(inverse_mod, Mdiv, M)
....:     x = sum([A[i]*X[i]*Mdiv[i] for i in xrange(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

Reducing a sequence to a value

The function reduce() takes a function of two arguments and apply it to a given sequence to reduce that sequence to a single value. The function sum() is an example of a reduce() function. The following sample code uses reduce() and the function add() defined above 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 dot product is then implemented using the custom-defined add() and mult() functions, in conjunction with the built-in Python functions reduce() and map().

sage: U = [1, 2, 3]
sage: V = [2, 3, 5]
sage: reduce(add, map(mult, 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 the custom defined function add() and re-defines mult() to multiply three numbers instead of two.

sage: mult = lambda a, b, c: a * b * c
sage: def crt(A, M):
....:     Mprod = prod(M)
....:     Mdiv = map(lambda x: Integer(Mprod / x), M)
....:     X = map(inverse_mod, Mdiv, M)
....:     x = reduce(add, map(mult, 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 a list 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: filter(is_prime, [1..50])
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]

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])
....:     all_primroots = [power_mod(g, k, p) for k in good_odd_integers]
....:     all_primroots.sort()
....:     return all_primroots
....: 
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 built-in functions, many of which are useful in functional programming. For example, you might want to read up on all(), any(), max(), min(), and zip(). Another useful resource is the Functional Programming HOWTO by A. M. Kuchling. Steven F. Lott's book Building Skills in Python has a chapter on Functional Programming using Collections. See also the chapter Functional Programming from Mark Pilgrim's book Dive Into Python.

devel/FunctionalProgramming (last edited 2020-06-22 08:10:56 by chapoton)