Lists and List Comprehensions
The primitive we’re going to look at today is called a list comprehension. A list comprehension is similar to how we’re used to specifying sets in mathematics. If I wanted to A define as the set of all integers between 1 and 999 which are divisible by 3, I’d write:
See how similar this to the Python code that uses a list comprehension to generate the same set.
X = range(1, 1000)
A = [ x for x in X if x % 3 == 0 ]
The Reduce Function
The reduce builtin function takes as arguments a function and a list (any sequence actually, if you want to be pedantic) and applies the function to the first two elements of the list, it then calls the function with the result of the first call and the third element, and so on.
That was confusing, so lets take an example.
def add(x,y): return x+y
print reduce(add, [1, 2, 3, 4, 5]
The reduce call in this program translates to a set of operations like this:
r1 = add(1, 2)
r2 = add(r1, 3)
r3 = add(r2, 4)
r4 = ad(r3, 5)
You can think of reduce as applying a binary operator recursively on a vector to produce a scalar. The interesting thing about reduce is that in the case of an associative operator, you can easily parallelize the operation.
Example 1: Problem 1 from Project Euler
Find the sum of all the multiples of 3 or 5 below 1000.
The problem is trivial to solve imperatively, but our goal is to write this using as many functional constructs as possible.
Instead of solving it for the specific case of integers between 1 and 1000, lets generalize the problem and solve for the arbitrary range .
def sum35multiple(a, b):
L = range(a, b)
C = lambda n: n%3 == 0 or n%5 == 0
S = [ x for x in L if C(x) ]
return reduce(lambda x,y:x+y, S)
Note the trick we play in lines 3 and 5. Line 3 creates a local variable that holds a reference to an anonymous function and line 5 is the place where it is invoked. Combined with closures, this can be used to implement some powerful idioms. We’ll see one example of that when we get around to currying.
A closure is a somewhat more complicated concept and it will probably take more than one blog entry to get through. So, in this post, we’re going to dive in and use the damn thing before trying to understand it works.
Again our target is a problem from Project Euler - Problem 6.
The sum of the squares of the first ten natural numbers is,1² + 2² + … + 10² = 385
The square of the sum of the first ten natural numbers is,(1 + 2 + … + 10)² = 55² = 3025
Hence the difference between the sum of the squares of the first ten natural numbers and the square of the sum is 3025 − 385 = 2640.
Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum.
This problem is also rather trivial to solve both imperatively as well as mathematically. But for the purposes of this post, we’re going to take a hybrid semi-computational solution. We need to get through a little math before we get down to code.
Our goal is to find:
I’ll skip the details here, but it is easy to show that:
Here is straightforward translation of this equation into python code.
Sn = n*(n+1)/2
i = range(1, n+1)
d = map(lambda x,y: (Sn - x)*y, i, i)
return reduce(lambda x,y: x+y, d)
I’ve introduced a new built-in function in this code, the
map function. The map function takes a variable number of arguments, the first of which is always a function, and the remaining all sequences. It iterates over each sequence “in-step” and returns a new sequence that is generated by applying the function on each element of the input sequences.
Again, this is the kind of thing that is best explained with an example.
def print_add(x, y):
print "adding", x, y
print map (print_add, [1, 2, 3], [4, 5, 6])
Running this snippet produces the output:
adding 1 4
adding 2 5
adding 3 6
[5, 7, 9]
With that explanation, it should be clear that the function call to map in the function D is simply to calculate each term of the first summation in the equation for D(n).
I guess you’re wondering how is all this related to a closure. In fact, I’ve sneaked a closure into the function D(n).
Look at line 4 again, I’m using the local variable Sn inside of the anonymous function. Notice how this is fundamentally different from a function that you could create in a C-like language. The function created by the lambda is not even completely defined until line 2 in the function D(n) calculates Sn. Conceptually, we’re creating a different function to pass to map during each invocation of D(n). One of the reasons why people claim that functional languages afford large gains in productivity and elegance of expression is this ability to “close state” and create functions at runtime.
There’s a bit more to this business of passing functions around that I want to cover, but I hope I’ve whetted your appetite enough for now. Until the next post, tata, bye-bye and let me know in the comments how you’re liking/disliking this.