As the name suggests filter extracts each element in the sequence for which the function returns True. Consider our list of numbers. If we want to create a new list of only odd numbers we can produce it like so:

def isOdd(n): return (n%2 != 0) # use mod operator
L = filter(isOdd, numbers)
print L

Alternatively we can write:

def isOdd(n): return (n%2 != 0)
for i in numbers:
   if isOdd(i):
      L.append(i)
print L

Again notice that the conventional code requires two levels of indentation to achieve the same result. Again the increased indentation is an indication of increased code complexity.

reduce(aFunction, aSequence)

The reduce function is a little less obvious in its intent. This function reduces a list to a single value by combining elements via a supplied function. For example we could sum the values of a list and return the total like this:

def add(i,j): return i+j
print reduce(add, numbers)

As before we could do this more conventionally like this:

res = 0
for i in range(len(numbers)): # use indexing
   res = res + numbers[i]
print res

While that produces the same result in this case, it is not always so straightforward. What reduce actually does is call the supplied function passing the first two members of the sequence and replaces them with the result. In other words a more accurate representation of reduce is like this:

def reduce(numbers):
  L = numbers[:] # make a copy of original
  while len(L) >= 2:
     i,j = L[0],L[1] # use tuple assignment
     L = [i+j] + L[2:]
  return L[0]

One feature you may have noticed in the examples so far is that the functions passed to the FP functions tend to be very short, often only a single line of code. To save the effort of defining lots of very small functions Python provides another aid to FP - lambda. The name lambda comes from a branch of mathematics called lambda calculus which uses the Greek letter Lambda to represent a similar concept.

Lambda is a term used to refer to an anonymous function, that is, a block of code which can be executed as if it were a function but without a name. Lambdas can be defined anywhere within a program that a legal Python expression can occur, which means we can use them inside our FP functions.

A Lambda looks like this:

lambda <aParameterList> : <a Python expression using the parameters>

Thus the add function above could be rewritten as:

add = lambda i,j: i+j

print reduce(lambda i,j:i+j, numbers)

Similarly we can rewrite our map and filter examples like so:

L = map(lambda i: i, spam)
print L
L = filter(lambda i: (i%2 != 0), numbers)
print L

List Comprehension

List comprehension is a technique for building new lists borrowed from Haskell and introduced in Python since version 2.0. It has a slightly obscure syntax, similar to mathematical set notation. It looks like this:

[<expression> for <value> in <collection> if <condition>]

Which is equivalent to:

L = []
for value in collection:
    if condition:
        L.append(expression)

As with the other FP constructs this saves some lines and two levels of indentation. Lets look at some practical examples.

First let's create a list of all the even numbers:

>>> [n for n in range(10) if n % 2 == 0 ]
[0, 2, 4, 6, 8]

That says we want a list of values (n) where n is selected from the range 0-9 and n is even(i % 2 == 0).

The condition at the end could, of course, be replaced by a function, provided the function returns a value that Python can interpret as boolean. Thus looking again at the previous example we could rewrite it as:

>>>def isEven(n): return ((n%2) == 0)
>>> [ n for n in range(10) if isEven(n) ]
[0, 2, 4, 6, 8]

Now let's create a list of the squares of the first 5 numbers:

>>> [n*n for n in range(5)]
[0, 1, 4, 9, 16]

Notice that the final if clause is not needed in every case. Here the initial expression is n*n and we use all of the values from the range.

Finally let's use an existing collection instead of the range function:

>>> values = [1, 13, 25, 7]
>>> [x for x in values if x < 10]
[1, 7]

This could be used to replace the following filter function:

>>> filter(lambda x: x < 10, values)
[1, 7]

List comprehensions are not limited to one variable or one test however the code starts to become very complex as more variables and tests are introduced.

Whether comprehensions or the traditional functions seem most natural or appropriate to you is purely subjective. When building a new collection based on an existing collection you can use either the previous FP functions or the new list comprehensions. When creating a completely new collection it is usually easier to use a comprehension.

Remember though that while these constructs may seem appealing, the expressions needed to get the desired result can become so complex that it's easier to just expand them out to their traditional python equivalents. There is no shame in doing so - readability is always better than obscurity, especially if the obscurity is just for the sake of being clever!

Other constructs

Of course while these functions are useful in their own right they are not sufficient to allow a full FP style within Python. The control structures of the language also need to be altered, or at least substituted, by an FP approach. One way to achieve this is by applying a side effect of how Python evaluates boolean expressions.

Short Circuit evaluation

Because Python uses short circuit evaluation of boolean expressions certain properties of these expressions can be exploited. To recap on short-circuit evaluation: when a boolean expression is evaluated the evaluation starts at the left hand expression and proceeds to the right, stopping when it is no longer necessary to evaluate any further to determine the final outcome.

Taking some specific examples let's see how short circuit evaluation works:

>>> def TRUE():
...   print 'TRUE'
...   return True
...   
>>>def FALSE():
...   print 'FALSE'
...   return False
...

First we define two functions that tell us when they are being executed and return the value of their names. Now we use these to explore how boolean expressions are evaluated:

>>>print TRUE() and FALSE()
TRUE
FALSE
False
>>>print TRUE() and TRUE()
TRUE
TRUE
True
>>>print FALSE() and TRUE()
FALSE
False
>>>print TRUE() or FALSE()
TRUE
True
>>>print FALSE() or TRUE()
FALSE
TRUE
True
>>>print FALSE() or FALSE()
FALSE
FALSE
False

Notice that only IF the first part of an AND expression is True then and only then will the second part be evaluated. If the first part is False then the second part will not be evaluated since the expression as a whole cannot be True.

Likewise in an OR based expression if the first part is True then the second part need not be evaluated since the whole must be True.

There is one other feature of Pythons evaluation of boolean expressions that we can take advantage of, namely that when evaluating an expression Python does not simply return True or False, rather it returns the actual value of the expression. Thus if testing for an empty string (which would count as False) like this:

if "This string is not empty": print "Not Empty"
else: print "No string there"

Python just returns the string itself!

We can use these properties to reproduce branching like behavior. For example suppose we have a piece of code like the following:

if TRUE(): print "It is True"
else: print "It is False"

We can replace that with the FP style construct:

V =  (TRUE() and "It is True") or ("It is False")
print V

Try working through that example and then substitute the call to TRUE() with a call to FALSE(). Thus by using short circuit evaluation of boolean expressions we have found a way to eliminate conventional if/else statements from our programs. You may recall that in the recursion topic we observed that recursion could be used to replace the loop construct. Thus combining these two effects can remove all conventional control structures from our program, replacing them with pure expressions. This is a big step towards enabling pure FP style solutions.

To put all of this into practice let's write a completely functional style factorial program using lambda instead of def, recursion instead of a loop and short circuit evaluation instead of if/else:

>>> factorial = lambda n: ( (n <= 1) and 1) or
...                       (factorial(n-1) * n)
>>> factorial(5)
120

And that really is all there is to it. It may not be quite so intelligible as the more conventional Python code but it does work and is a purely functional style function in that it is a pure expression.

Conclusions

At this point you may be wondering what exactly is the point of all of this? You would not be alone. Although FP appeals to many Computer Science academics (and often to mathematicians) most practicing programmers seem to use FP techniques sparingly and in a kind of hybrid fashion mixing it with more traditional imperative styles as they feel appropriate.

When you have to apply operations to elements in a list such that map, reduce or filter seem the natural way to express the solution then by all means use them. Just occasionally you may even find that recursion is more appropriate than a conventional loop. Even more rarely will you find a use for short circuit evaluation rather than conventions if/else - particularly if required within an expression. As with any programming tool, don't get carried away with the philosophy, rather use whichever tool is most appropriate to the task in hand. At least you know that alternatives exist!

There is one final point to make about lambda. There is one area outside the scope of FP that lambda finds a real use and that's for defining event handlers in GUI programming. Event handlers are often very short functions, or maybe they simply call some larger function with a few hard-wired argument values. In either case a lambda function can be used as the event handler which avoids the need to define lots of small individual functions and fill up the name space with names that would only be used once. Remember that a lambda statement returns a function object. This function object is the one passed to the widget and is called at the time the event occurs. If you recall how we define a Button widget in Tkinter, then a lambda would appear like this:

def write(s): print s
b = Button(parent, text="Press Me", 
           command = lambda : write("I got pressed!"))
b.pack()

Of course in this case we could have done the same thing by just assigning a default parameter value to write() and assigning write to the command value of the Button. However even here using the lambda form gives us the advantage that the single write() function can now be used for multiple buttons just by passing a different string from the lambda. Thus we can add a second button:

b2 = Button(parent, text="Or Me", 
           command = lambda : write("So did I!"))
b2.pack()

We can also employ lambda when using the bind technique, which sends an event object as an argument:

b3 = Button(parent, text="Press me as well")
b3.bind(<Button-1>, lambda ev : write("Pressed"))

Well, that really is that for Functional Programming. There are lots of other resources if you want to look deeper into it, some are listed below. Neither VBScript nor JavaScript directly support FP but both can be used in a functional style by a determined programmer. The key features being to structure your programs as expressions and not to allow side-effects to modify program variables.

Other resources