In this series, Pramod Subramanyan will introduce and explore functional programming for newbies. Pramod is a software engineer working at National Instruments, India. He is fascinated by the process of computation, the algorithms, the hardware, the software and the mathematical theory that goes behind it. His blog is an account of his adventures as a voyager delving into this intriguing domain. He also maintains a "proper" website at http://pramod.sub.googlepages.com/.
In the Beginning
Lets use a simple example: I have a list of integers and I want to create another list that contains only those elements from this list that are greater than 5. The straightforward way to write this is like below:
o =  # initialize empty list
for num in l: # iterate over list
if num > 5: o.append(num)
return o # return filtered list
I wrote the snippet above in python, but hopefully, it is easy enough to read even if you haven't seen the language before.
Shown below is example of how you'd use the filter_above_5 function.
print "original list:", l
print "filtered list:", filter_above_5(l)
Simple enough, isn't it? For reasons that we will come to later, people like to call this an imperative implementation.
Lets Make This Functional
If you think about it, filter_above_5 is a special case of a generic filter function which iterates over an input list and produces an output list that contains all the elements from the input list that satisfy some condition. [If you wanted to make things sound complicated, you'd use predicate instead of "some condition" and sequence and sub-sequence instead of input and output list. :-)] Jokes apart, it would be cool if we could write a general function like this:
def filter_list(predicate, l): o =  for element in l: if predicate(element): o.append(element) return ofilter_list is a function that takes a list and a function (our predicate) as parameters and iterates over each element of the input list, and adds only those elements to the output list that satisfy the predicate. Then you'd call filter_list like below:
def greater_than_5(x): return x > 5It turns out that python already has a builtin function filter that does exactly what our filter_list function does. So our implementation just boils down to calling the that function with our custom predicate:
print "original list:", l
print "filtered list:", filter_list(greater_than_5, l)
def greater_than_5(x): return x > 5 print "original list:", l print "filtered list:", filter(greater_than_5, l)Notice the difference between our initial implementation and new one. filter_above_5 did not just tell the interpreter what to do, it also specified exactly how to do it using a series of commands. For that reason, we call it an imperative implementation.
Our newest implementation that uses the builtin filter function does not specify how the filtering should be done. For instance, with all this ado about multi-core, it is not far fetched to think of a version of filter that spawns a number of threads and splits up the work of filtering among these threads. The cool thing is, if, say, Python 3.1 implemented such a multi-threaded filtering function, all our code which used the filter function would get the performance improvement for free.
Plus, notice that this version contains much lesser code, and we're programming at a much higher level of abstraction, not to mention the fact that the new version is more elegant.
All put together, I think it is fair to say, that the implementation that is based on filter is "better" than the imperative implementation.
Notice an important thing about filter - we are passing a function as a parameter to another function. Programming languages which allow this kind of thing - passing and returning functions from other functions, construction of functions at runtime etc. - are said to have first class functions. Now, exactly what set of attributes are required for a language to be deemed to have first class function support is a controversial topic, and so we will side-step that issue here.  The important point is passing functions to other functions doing so is a key aspect of functional programming. And since we're doing this in our filtering snippet, we're going to call it a functional implementation.
Enter the Lambda
Nothing we've done so far can't be done from, say, C/C++. In C for instance, we could've created a filter function that operated on array of void*, and used a function pointer to pass the predicate around. [Similar in spirit to the qsort library function]. In C++, we could have created a templatized version of filter that was allegedly more elegant and worked in more or less the same way, but would claim to be "safer" because it would be type-checked. 
Recognize that functions like greater_than_5 are use and throw functions. They are created only for the purpose of being called from the filtering function, and then they are never used again. Unfortunately, despite the fact that these functions are going to be called from exactly one place, they will still be sitting in source code polluting our namespace. What would be cool is a way of creating the function greater_than_5 specifically for the purpose of passing it to filter and then "forgetting about it".
The solution to this problem is called a lambda function. In python it looks like this:
print "original list:", l print "filtered list:", filter(lambda x: x>5, l)Pay attention to the first argument to filter: "lambda x: x>5". What it means is: create a function that takes one parameter as input - "x", and returns the value of the expression x>5 and then return that function that just got created. Note that the created function is anonymous. The key benefit now is that if I had to call filter in a hundred different places with 50 different filtering predicates, I needn't create a 50 predicates similar to greater_than_5 just to pass them to filter. I can create each of these functions at the point at which filter is called.
This means my code will look much cleaner; there will be no namespace pollution and most importantly I will have to write lesser code.
So, in summary lambda forms allow the functional programmer to create anonymous functions that can be passed around to other functions. Or even be stored for later use [although this is somewhat uncommon].
Isn't this just syntactic sugar?
The thing is, besides the lack of namespace pollution, and some fewer keystrokes to type [not that these aren't important things, but lets play the devil's advocate here], we still haven't gained much by using the lambda. And the fact is, if these were the only advantages of the lambda, lambda's would just be cute syntactic sugar.
But there is more - the key advantage of lambda's is when they are combined with a language that supports closures. We will look at closures in the next post.
In the meantime, if any of the above didn't make sense, or you have some feedback, please comment below.
 Point is that it is is not correct to call python a functional programming language. If you want to be politically correct, it is a multi-paradigm language with some functional programming features. Anyway, lets not get into these religious wars and concentrate on the fun stuff instead. :-)
 Ensuring const-correctness on your elegant function, making it behave like a STL function so that it works correctly for everything that implements forward_iterators and/or const_forward_iterators and fun times spent debugging the wonderfully cryptic error messages that compilers spit out for templates are but minor prices to pay for that elegance. [Sorry, I couldn't resist that crack :-)]