9366
Comment: layout tutorial on functional programming

← Revision 19 as of 20200622 08:10:56 ⇥
13098

Deletions are marked like this.  Additions are marked like this. 
Line 1:  Line 1: 
## page was renamed from Tips/FunctionalProgramming  
Line 4:  Line 5: 
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 objectoriented programming, and then discuss functional programming techniques. Along the way, we briefly review Python's builtin support for functional programming, including `filter()`, `lambda`, `map()` and `reduce()`. The tutorial concludes with some resources on detailed information on functional programming using Python.  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 objectoriented 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/pythonfunctionalprogrammingformathematicians/Wordpress]]. 
Line 15:  Line 16: 
....:  
Line 18:  Line 18: 
....:  
Line 25:  Line 24: 
Another common style of programming is called objectoriented programming. Think of an object as code that encapsulates both data and functionalities. The above procedural program could be implemented in the objectoriented style as follows:  The Python module `operator` defines several common arithmetic and comparison operators as named functions. Addition is defined in the builtin 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 objectoriented programming. Think of an object as code that encapsulates both data and functionalities. You could encapsulate integer addition and multiplication as in the following objectoriented implementation: 
Line 36:  Line 45: 
sage: ZZ = MyInteger() sage: ZZ.cardinality 
sage: myZZ = MyInteger() sage: myZZ.cardinality 
Line 39:  Line 48: 
sage: ZZ.add(2, 3)  sage: myZZ.add(2, 3) 
Line 41:  Line 50: 
sage: ZZ.mult(2, 3)  sage: myZZ.mult(2, 3) 
Line 49:  Line 58: 
Functional programming is yet another style of programming in which a program is decomposed into various functions. The Python builtin functions <a href="http://docs.python.org/library/functions.html#map">`map()`</a>, <a href="http://docs.python.org/library/functions.html#reduce">`reduce()`</a> and <a href="http://docs.python.org/library/functions.html#filter">`filter()`</a> allow you to program in the functional style. The function  Functional programming is yet another style of programming in which a program is decomposed into various functions. The Python builtin functions [[https://docs.python.org/library/functions.html#mapmap()]], [[https://docs.python.org/library/functions.html#reducereduce()]] allow you to program in the functional style. The function 
Line 55:  Line 64: 
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:  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: 
Line 66:  Line 76: 
sage: [A[i] + B[i] for i in xrange(len(A))]  sage: [a + b for a, b in zip(A, B)] 
Line 70:  Line 80: 
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) 
Alternatively, you could use the Python builtin addition function `operator.add()` together with `map()` to achieve the same result: {{{ sage: list(map(add, A, B)) 
Line 77:  Line 87: 
An advantage of `map()` is that you don't need to explicitly define a `for` loop as was done in the above list comprehension.  An advantage of `map()` is that you do not need to explicitly define a `for` loop as was done in the above list comprehension. 
Line 90:  Line 100: 
Or you could use a <a href="http://docs.python.org/reference/expressions.html#lambda">`lambda`</a> 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) 
Or you could use a [[https://docs.python.org/reference/expressions.html#lambdalambda]] 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) 
Line 97:  Line 107: 
sage: mult(2, 3)  sage: mult_ZZ(2, 3) 
Line 101:  Line 111: 
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 <a href="http://en.wikipedia.org/wiki/Chinese_remainder_theorem">Chinese Remainder Theorem</a>. 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.  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_theoremChinese 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. 
Line 106:  Line 116: 
....: Mdiv = map(lambda x: Integer(Mprod / x), M)  ....: Mdiv = list(map(lambda x: Integer(Mprod / x), M)) 
Line 108:  Line 118: 
....: x = sum([A[i]*X[i]*Mdiv[i] for i in xrange(len(A))])  ....: x = sum(A[i]*X[i]*Mdiv[i] for i in range(len(A))) 
Line 110:  Line 120: 
....:  
Line 123:  Line 132: 
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] }}} 

Line 127:  Line 199: 
The function <a href="http://docs.python.org/library/functions.html#reduce">`reduce()`</a> takes a function of two arguments and apply it to a given sequence to reduce that sequence to a single value. The function <a href="http://docs.python.org/library/functions.html#sum">`sum()`</a> 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:  The function [[http://docs.python.org/library/functions.html#reducereduce()]] 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#sumsum()]] is an example of a `reduce()` function. The following sample code uses `reduce()` and the builtin function `operator.add()` to add together all integers in a given list. This is followed by using `sum()` to accomplish the same task: 
Line 137:  Line 209: 
In the following sample code, we consider a vector as a list of real numbers. The <a href="http://en.wikipedia.org/wiki/Dot_product">dot product</a> is then implemented using the customdefined `add()` and `mult()` functions, in conjunction with the builtin Python functions `reduce()` and `map()`.  In the following sample code, we consider a vector as a list of real numbers. The [[http://en.wikipedia.org/wiki/Dot_productdot product]] is then implemented using the functions `operator.add()` and `operator.mul()`, in conjunction with the builtin Python functions `reduce()` and `map()`. We then show how `sum()` and `map()` could be combined to produce the same result. 
Line 142:  Line 214: 
sage: reduce(add, map(mult, U, V))  sage: reduce(add, map(mul, U, V)) 23 sage: sum(map(mul, U, V)) 
Line 155:  Line 229: 
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 redefines `mult()` to multiply three numbers instead of two. {{{ sage: mult = lambda a, b, c: a * b * c 
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. {{{ 
Line 163:  Line 236: 
....: x = reduce(add, map(mult, A, X, Mdiv))  ....: mul3 = lambda a, b, c: a * b * c ....: x = reduce(add, map(mul3, A, X, Mdiv)) 
Line 176:  Line 250: 
The Python builtin 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]) 
The Python builtin 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])) 
Line 183:  Line 257: 
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 $latex \mathbf{Z}/p\mathbf{Z}$.  For a given positive integer `n`, the [[https://en.wikipedia.org/wiki/Euler%27s_totient_functionEuler 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}`. 
Line 191:  Line 280: 
....: all_primroots = [power_mod(g, k, p) for k in good_odd_integers] ....: all_primroots.sort() ....: return all_primroots ....: 
....: return sorted(power_mod(g, k, p) for k in good_odd_integers) 
Line 219:  Line 305: 
This has been a rather short introduction to functional programming with Python. The Python standard documentation has a list of <a href="http://docs.python.org/library/functions.html">builtin functions</a>, many of which are useful in functional programming. For example, you might want to read up on <a href="http://docs.python.org/library/functions.html#all">`all()`</a>, <a href="http://docs.python.org/library/functions.html#any">`any()`</a>, <a href="http://docs.python.org/library/functions.html#max">`max()`</a>, <a href="http://docs.python.org/library/functions.html#min">`min()`</a>, and <a href="http://docs.python.org/library/functions.html#zip">`zip()`</a>. Another useful resource is the <a href="http://docs.python.org/howto/functional.html">Functional Programming HOWTO</a> by A. M. Kuchling. Steven F. Lott's book <a href="http://homepage.mac.com/s_lott/books/python.html#bookpython">Building Skills in Python</a> has a chapter on <a href="http://homepage.mac.com/s_lott/books/python/html/p02/p02c10_adv_seq.html">Functional Programming using Collections</a>. See also the chapter <a href="http://www.diveintopython.org/functional_programming/index.html">Functional Programming</a> from Mark Pilgrim's book <a href="http://www.diveintopython.org">Dive Into Python</a>.  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.htmlbuiltin 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#allall()]], [[http://docs.python.org/library/functions.html#anyany()]], [[http://docs.python.org/library/functions.html#maxmax()]], [[http://docs.python.org/library/functions.html#minmin()]], and [[http://docs.python.org/library/functions.html#zipzip()]]. The Python module [[http://docs.python.org/library/operator.htmloperator]] has numerous builtin 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 builtin function that satisfies your requirement. The module [[http://docs.python.org/library/itertools.htmlitertools]] has numerous builtin 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.htmlFunctional Programming HOWTO]] by A. M. Kuchling. Steven F. Lott's book [[http://homepage.mac.com/s_lott/books/python.html#bookpythonBuilding Skills in Python]] has a chapter on [[http://homepage.mac.com/s_lott/books/python/html/p02/p02c10_adv_seq.htmlFunctional Programming using Collections]]. See also the chapter [[http://www.diveintopython3.org/functional_programming/index.htmlFunctional Programming]] from Mark Pilgrim's book [[http://www.diveintopython3.orgDive Into Python]]. You might also want to consider experimenting with [[http://www.haskell.orgHaskell]] 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.htmlUnbounded Spigot Algorithms for the Digits of Pi]] in the American Mathematical Monthly. 
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 objectoriented 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 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 builtin 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 objectoriented programming. Think of an object as code that encapsulates both data and functionalities. You could encapsulate integer addition and multiplication as in the following objectoriented 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 builtin functions map(), 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 elementwise. 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 builtin 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, oneliner function. You could rewrite 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_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 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 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 builtin 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 dot product is then implemented using the functions operator.add() and operator.mul(), in conjunction with the builtin 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 builtin 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 builtin 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 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..p1, 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 builtin functions, many of which are useful in functional programming. For example, you might want to read up on all(), any(), max(), min(), and zip(). The Python module operator has numerous builtin 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 builtin function that satisfies your requirement. The module itertools has numerous builtin 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 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.
You might also want to consider experimenting with Haskell for expressing mathematical concepts. For an example of Haskell in expressing mathematical algorithms, see J. Gibbons' article Unbounded Spigot Algorithms for the Digits of Pi in the American Mathematical Monthly.