Superjazz

SPOILER ALERT: This post contains a solution to Project Euler problem 20.

I gave some more Project Euler a go last week and when I came across problem 20, I knew it was time for me to finally learn how to use closures. I could not find much accessible information for beginners, so I figured I would write up what I discovered. That means it’s time to grab a cup of coffee and put on your theory cap, because this topic needs a bit of explanation.

Closures and Anonymous Functions

It is important to make a distinction between these two concepts. Too often I have seen technical books and manuals introduce them as the same thing.

A closure is a very important part of recursive programming. To unashamedly copy Wikipedia’s definition, a closure is, “a function that is evaluated in an environment containing one or more bound variables.” This means that there are one or more variables that are useable by the function in the form of local variables or arguments.

An anonymous function is a function that is not given a name.

Closure + Anonymous Function = ?

My suspicion as to why people so many people get closures and anonymous functions mixed up is because in python, they are both used for 99% of cases. The keyword used in python for this is lambda. There are also many recursion specific functions, but I will only be mentioning map() and reduce().

So first up, lets look at how one would solve this problem without recursion.

Project Euler Problem 20
n! means n*(n-1)*...*3*2*1
Find the sum of the digits in the number 100!

This is easily solvable with a few for loops:

# problem20_norecursion.py
# solving problem 20 without using recursion techniques
 
factorial_result = 1
sum_result = 0
 
for number in range(1,101): # from 1 to 100
	factorial_result *= number
 
for number in str(factorial_result):
	sum_result += int(number)
 
print sum_result

Now this works very well, but the problem seems like it can be solved in less than 7 lines. It is only two very simple operations that could be easily combined.

lambda
As mentioned previously, lambda allows us to create both anonymous functions and use closures in python. The name is derived from the calculus of recursion and function definition, lambda calculus. Creating an anonymous function is just as easy as creating a regular function, only it needs to be assigned somewhere so you can access it. Return values are not needed; they are handled automatically by the interpreter. For now, we will just use a variable. Anyone who has done a reasonable amount of python before should understand what is going on in this example:

# lambda_examples.py
# examples of the usage of lambda
 
f = lambda x: x+1
g = lambda x: x*2
h = lambda x, y: x*y
 
print f(5)
print g(5)
print h(5,6)

And the output is:

6
10
30

As you can see, the syntax is identical to a def statement.
map() and reduce()
map() and reduce() are the two most useful recursion functions in python (in my opinion anyway). Let’s take a closer look at them.

The map() function takes two arguments, the first being a function with one argument and second being a sequence. It is essentially a condensed for-loop; it takes the function and feeds it every element in the sequence individually and returns a list of the results. The trick here is to not create a function outside the map() brackets, rather to create a temporary one and pass it as an argument using lambda. A few examples might help explain this:

# examples demonstrating the map() function
 
the_list = [1, 2, 3, 4, 5, 6, 7, 8]
new_list = map(lambda x: x+1, the_list)
# new_list = [2, 3, 4, 5, 6, 7, 8, 9]
 
new_list = map(lambda x: x%2, the_list)
# new_list = [1, 0, 1, 0, 1, 0, 1, 0]

Simple, isn’t it?

reduce() is slightly more complicated. It again takes two arguments, however the function now must take two arguments. This is because after performing the operation, the return value is passed as the first argument of the next iteration. So having

result = reduce(lambda x,y: x*y, range(1,10))

is equivalent to

result = ((((((((1*2)*3)*4)*5)*6)*7)*8)*9)

It is pretty obvious which looks nicer! Hopefully you can see that reduce() will allow us to do what we need to solve this problem.

Problem 20 with Recursion

# problem20_recursion.py
# solving problem 20 using recursion techniques
 
print reduce( lambda x,y: int(x)+int(y), str( reduce( lambda x, y: x*y, range(1,101)) ))

Granted, this is not the prettiest line of code I have ever written but it clearly demonstrates how recursion allows you to pack significant complexities into a single statement. lambda with a few other functions means you can turn whole loops into a single line or perform complex operations with simple lines of code.

Besides, all the cool kids are doing it.