This playground shows the useful, but lesser known, functional programming features of Python. Python is well known for its object oriented programming features: classes, methods, inheritance... However, Python is not restricted to object oriented programming, it offers several very useful features that enables the programmer to use the regular functional programming idioms, such as higher order functions and operations on data collections. These programming patterns are a useful addition to the toolbox of the regular Python developer. Along the way, we will also learn some functional programming concepts and techniques.
Higher order functions
One of the main concepts of functional programming is first class functions. Simply said, it means that functions can be used like any other data type. You can :
- store a function in a variable;
- pass a function as an argument to another function;
- return a function as the result of a function call;
- make a list of function;
A function that takes another function as an argument is called a higher order function. A well known higher order function of Python is
sorted. In its simplest form,
sorted can be used to sort a list of integers:
sorted has an optional argument
key, which is a function with one argument.
sorted will call the
key function for each element and use the returned values to sort the list. Consider the following class, which models a bonus chest in an adventure game:
class BonusChest(object): def __init__(self,x,y,numCoins): self.x = x self.y = y self.numCoins = numCoins def getNumCoins(self): return self.numCoins
To sort a list of bonus chests with respect to the number of coins they contain, you can call:
BonusChest.getNumCoins is actually a function which takes a
BonusChest instance as unique parameter.
sorted will call this function on each chest and use the result to sort them. Python calls such a function an unbounded method.
Getters and setters are less common within Python programs, so the instances you are sorting may not provide the needed
key function to pass to
sorted. You can create a function, outside the
BonusChest class and pass it to
def getNumCoins(chest): return chest.numCoins sortedChests = sorted(chestList,key=getNumCoins)
Writing a separated function each time you want to sort a collection is not very practical, especially if this function will only be used by
sorted. For such situations, Python offers the
lambda keyword, which enables you to define a function on the fly:
sorted(chestList, key=lambda chest:chest.numCoins).
Don't be afraid by the lambda keyword. Here, it just means: "I'm defining a function which takes a single argument
chest and returns the value of the expression
chest.numCoins. The body of a lambda function is defined after the column and must be a single expression. The returned value is the value of this expression. Python uses the keyword
lambda as a reference to Lambda calculus, the grand father of functional programming.
Hands on session
Now that you know what is a higher order function, it's time for you to write one.
In this first exercise, you are asked to complete the
sortedWithCmp sorts the
values list and returns it. Sorting is not done in place, a new list is returned.
cmpFunc, the second argument, is a comparison functions which takes two arguments. If the first one is greater than the second one, it returns
True. Otherwise, it returns
False. Right now,
sortedWithCmp uses the default comparison operation of Python. You have to modify the code of
sortedWithCmp so that it uses
cmpFunc to compare the elements.
sortedWithCmp is based on merge sort. If your unfamiliar with this algorithm, the main point for this exercise is to know that it relies on a comparison and that is where you have to operate. In any case, I encourage you to discover the algorithm, it's simple and efficient ; a good introduction to recursive algorithms.
For this second exercise, you have again to modify merge sort, but this time you will add support for a key function. This is to obtain a similar behavior as the built-in sorted function. The exercise contains a sorted function which is a raw merge sort, with just the list to be sorted as the single argument. You have to implement the
sortedWithKey function which takes two arguments: (1) the list of values to sort; (2) a function which returns a key for each value. Values are sorted with respect to their key.
sortedWithKey will call the provided