In this topic we look at how Python can support yet another programming style: Functional Programming(FP). As with Recursion this is a genuinely advanced topic which you may wish to ignore for the present. Functional techniques do have some uses in day to day programming and the supporters of FP believe it to be a fundamentally better way to develop software.
Functional programming should not be confused with imperative (or procedural) programming. Neither is it like object oriented programming. It is something different. Not radically so, since the concepts that we will be exploring are familiar programming concepts, just expressed in a different way. The philosophy behind how these concepts are applied to solving problems is also a little different.
Functional programming is all about expressions. In fact another way to describe FP might be to term it expression oriented programming since in FP everything reduces to an expression. You should recall that an expression is a collection of operations and variables that results in a single value. Thus x == 5 is a boolean expression. 5 + (7-Y) is an arithmetic expression. And string.search("Hello world", "Hell") is a string expression. The latter is also a function call within the string module and, as we shall see, functions are very important in FP (You might already have guessed that from the name!).
Functions are used as objects in FP. That is they are often passed around within a program in much the same way as other variables. We have seen examples of this in our GUI programs where we assigned the name of a function to the command attribute of a Button control. We treated the event handler function as an object and assigned a reference to the function to the Button. This idea of passing functions around our program is key to FP.
Functional Programs also tend to be heavily List oriented.
Finally FP tries to focus on the what rather than the how of problem solving. That is a functional program should describe the problem to be solved rather than focus on the mechanism of solution. There are several programming languages which aim to work in this way, one of the most widely used is Haskell and the Haskell web site ( www.haskell.org) has numerous papers describing the philosophy of FP as well as the Haskell language. (My personal opinion is that this goal, however laudable, is rather overstated by FP's advocates.)
A pure functional program is structured by defining an expression which captures the intent of the program. Each term of the expression is in turn a statement of a characteristic of the problem (maybe encapsulated as another expression) and the evaluation of each of these terms eventually yields a solution.
Well, that's the theory. Does it work? Yes, sometimes it works very well. For some types of problem it is a natural and powerful technique. Unfortunately for many other problems it requires a fairly abstract thinking style, heavily influenced by mathematical principles. The resultant code is often far from readable to the layman programmer. The resultant code is also very often much shorter than the equivalent imperative code and more reliable. It is these latter qualities that have drawn many conventional imperative or object oriented programmers to investigate FP. Even if not embraced whole heartedly there are several powerful tools that can be used by all.
Python provides several functions which enable a functional approach to programming. These functions are all convenience features in that they can be written in Python fairly easily. What is more important however is the intent implicit in their provision, namely to allow the Python programmer to work in a FP manner if he/she wishes.
We will look at some of the functions provided and see how they operate on some sample data structures that we define as:
spam = ['pork','ham','spices'] numbers = [1,2,3,4,5] def eggs(item): return item
This function applies a Python function, aFunction to each member of aSequence. The expression:
L = map(eggs, spam) print L
Results in a new list (in this case identical to spam) being returned in L.
We could have done the same thing by writing:
for i in spam: L.append(i) print L
Notice however, that the map function allows us to remove the
need for a nested block of code. From one point of view that
reduces the complexity of the program by one level. We'll see
that as a recurring theme of FP, that use of the FP functions
reduces the relative complexity of the code by eliminating
blocks.
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:
Alternatively we can write:
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.
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:
As before we could do this more conventionally like this:
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:
Once more we see the FP technique reducing the complexity of
the code by avoiding the need for an indented block of code.
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
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:
Thus the add function above could be rewritten as:
Similarly we can rewrite our map and filter
examples like so:
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:
Which is equivalent to:
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:
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:
Now let's create a list of the squares of the first 5 numbers:
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:
This could be used to replace the following filter function:
Which style seems 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.
Finally, 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 just for
the sake of being clever!
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.
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:
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:
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 1 or 0, rather it
returns the actual value of the expression. Thus if testing for
an empty string (which would count as False) like this:
Python just returns the string itself!
We can use these properties to reproduce branching like
behaviour. For example suppose we have a piece of code like the
following:
We can replace that with the FP style construct:
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 recursion instead of
a loop and short circuit evaluation instead of if/else: 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.
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 namespace 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:
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:
We can also employ lambda when using the bind technique,
which sends an event object as an argument:
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.
If anyone else finds a good reference drop me an email via the
link below.
If you have any questions or feedback on this page send me mail at:
alan.gauld@btinternet.comfilter(aFunction, aSequence)
def isOdd(n): return (n%2 != 0) # use mod operator
L = filter(isOdd, numbers)
print L
def isOdd(n): return (n%2 != 0)
for i in numbers:
if isOdd(i):
L.append(i)
print L
reduce(aFunction, aSequence)
def add(i,j): return i+j
print reduce(add, numbers)
res = 0
for i in range(len(numbers)): # use indexing
res = res + numbers[i]
print res
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]
lambda
lambda <aParameterList> : <a Python expression using the parameters>
add = lambda i,j: i+j
And we can avoid the definition line completely by creating the
lambda within the call to reduce, like so:
print reduce(lambda i,j:i+j, numbers)
L = map(lambda i: i, spam)
print L
L = filter(lambda i: (i%2 != 0), numbers)
print L
List Comprehension
[<expression> for <value> in <collection> if <condition>]
L = []
for value in collection:
if condition:
L.append(expression)
>>> [n for n in range(10) if n % 2 == 0 ]
[0, 2, 4, 6, 8]
>>>def isEven(n): return ((n%2) == 0)
>>> [ n for n in range(10) if isEven(n) ]
[0, 2, 4, 6, 8]
>>> [n*n for n in range(5)]
[0, 1, 4, 9, 16]
>>> values = [1, 13, 25, 7]
>>> [x for x in values if x < 10]
[1, 7]
>>> filter(lambda x: x < 10, values)
[1, 7]
Other constructs
Short Circuit evaluation
>>> def TRUE():
... print 'TRUE'
... return 1 # boolean TRUE
...
>>>def FALSE():
... print 'FALSE'
... return 0 # boolean FALSE
...
>>>print TRUE() and FALSE()
TRUE
FALSE
0
>>>print TRUE() and TRUE()
TRUE
TRUE
1
>>>print FALSE() and TRUE()
FALSE
0
>>>print TRUE() or FALSE()
TRUE
1
>>>print FALSE() or TRUE()
FALSE
TRUE
1
>>>print FALSE() or FALSE()
FALSE
FALSE
0
if "This string is not empty": print "Not Empty"
else: print "No string there"
if TRUE(): print "It is True"
else: print "It is False"
V = (TRUE() and "It is True") or ("It is False")
print V
def factorial(n):
return ((n <= 1) and 1) or
(factorial(n-1) * n)
Conclusions
def write(s): print s
b = Button(parent, text="Press Me",
command = lambda : write("I got pressed!"))
b.pack()
b2 = Button(parent, text="Or Me",
command = lambda : write("So did I!"))
b2.pack()
b3 = Button(parent, text="Press me as well")
b3.bind(
Other resources
Previous
Next
Contents