1
CMPSC-132: Programming and Computation II
Department of Computer Science & Engineering
The Pennsylvania State University
1. Functional Programming
Functional programming decomposes a problem into a set of functions. In a functional program, input
flows through a set of functions. Each function operates on its input and produces some output. Functional
style discourages functions with side effects that modify internal state or make other changes that are not
visible in the function’s return value. Functions that have no side effects at all are called purely functional.
Avoiding side effects means not using data structures that get updated as a program runs; every function’s
output must only depend on its input. However, it is difficult to avoid all side effects. Printing to the screen
or writing to a disk file are examples of side effects.
Functional programming can be considered the opposite of object-oriented programming. Objects are
little capsules containing some internal state along with a collection of method calls that let you modify
this state, and programs consist of making the right set of state changes. Functional programming wants to
avoid state changes as much as possible and works with data flowing between functions. In Python you
might combine the two approaches by writing functions that take and return instances representing objects
in your application. Functional design may seem like an odd constraint to work under but it has theoretical
and practical advantages for formal provability, molarity, composability and ease of debugging and testing.
1.1 Higher-Order functions
We have seen that functions are a method of abstraction that describe compound operations
independent of the particular values of their arguments. For example:
def square(x):
return x * x
in the square function from above, we are not talking about the square of a particular number, but rather
about a method for obtaining the square of any number. Of course, we could get along without ever defining
this function, by always writing expressions such as 3 * 3, 9 * 9, 12 * 12, etc. This practice would suffice
for simple computations such as square, but would become arduous for more complex examples such as fib
(Fibonacci series). In general, lacking function definition would put us at the disadvantage of forcing us to
work always at the level of the particular operations that happen to be primitives in the language
(multiplication, in this case) rather than in terms of higher-level operations. Our programs would be able
to compute squares, but our language would lack the ability to express the concept of squaring.
One of the things we should demand from a programming language is the ability to build abstractions
by assigning names to common patterns and then to work in terms of the names directly. Functions provide
this ability. To express certain general patterns as named concepts, we will need to construct functions that
2
can accept other functions as arguments or return functions as values. Functions that manipulate functions
are called higher-order functions.
1.1.1 Functions as arguments
Consider the following two functions, which all compute summations. The first, sum_naturals,
computes the sum of natural numbers up to n:
def sum_naturals(n):
total, k = 0, 1
while k <= n:
total, k = total + k, k + 1
return total
sum_naturals(100) #5050
The second, sum_cubes, computes the sum of the cubes of natural numbers up to n:
def sum_cubes(n):
total, k = 0, 1
while k <= n:
total, k = total + k*k*k, k + 1
return total
sum_cubes(100) #25502500
These two functions clearly share a common underlying pattern. They are for the most part identical,
differing only in name and the function of k used to compute the term to be added. We could generate each
of the functions by filling in slots in the same template:
def
total, k = 0, 1
while k <= n:
total, k = total +
return total
The presence of such a common pattern is strong evidence that there is a useful abstraction waiting to be
brought to the surface. Each of these functions is a summation of terms. When designing your programs,
you would like your language to be powerful enough so that you can write a function that expresses the
concept of summation itself rather than only functions that compute particular sums. We can do so readily
in Python by taking the common template shown above and transforming the “slots” into formal
parameters. In the example below, summation() takes as its two arguments the upper bound n together with
the function term that computes the k-th term. We can use summation just as we would any function, and
it expresses summations succinctly. Take the time to step through this example, and notice how binding
cube to the local name term ensures that the result 1*1*1 + 2*2*2 + 3*3*3 = 36 is computed correctly:
def summation(n, term):
total, k = 0, 1
while k <= n: total, k = total + term(k), k + 1 return total def cube(x): return x*x*x def sum_cubes(n): return summation(n, cube) result = sum_cubes(3) print(result) 3 1.1.2 Functions as returned values We can achieve even more expressive power in our programs by creating functions whose returned values are themselves functions. An important feature of lexically scoped programming languages is that locally defined functions maintain their parent environment when they are returned. Once many simple functions are defined, function composition is a natural method of combination to include in our programming language. That is, given two functions f(x) and g(x), we might want to define h(x) = f(g(x)). We can define function composition using our existing tools: def compose_f(f, g): def h(x): return f(g(x)) return h The following example illustrates the utility of this feature: def square(x): return x * x def successor(x): return x + 1 def fun_compose(f, g): def h(x): return f(g(x)) return h square_successor = fun_compose(square, successor) result = square_successor(10) print(result) #121 Both square and successor functions take one argument, thus, the fun_composed functions all take a single argument as well. 1.2 Lambda Expressions So far, each time we have wanted to define a new function, we needed to give it a name. The lambda expression is a way to create small anonymous functions (functions without a name). These functions are throw-away functions (just needed where they have been created). Lambda functions are mainly used in combination with the functions filter(), map() and reduce(). The following example of a lambda function returns the sum of its two arguments: sum = lambda x, y : x + y sum(3,4) >>> 7
In general, Python style prefers explicit def statements to lambda expressions, but allows them in cases
where a simple function is needed as an argument or return value. Such stylistic rules are merely guidelines;
you can program any way you wish. However, as you write programs, think about the audience of people
who might read your program one day and think if your program is easy to understand.
def sum(x,y):
return x + y
sum(3,4)
>>> 7
4
1.2.1 The map() function
map() takes a function and a collection of items. It makes a new, empty collection, runs the function on
each item in the original collection and inserts each return value into the new collection. It returns the new
collection.
r = map(function_to_apply, list_of_inputs)
The code below is a simple map that takes a list of names and returns a list of the lengths of those
names:
name_lengths = map(len, [“Alex”, “Sandy”, “Jeffrey”])
print(list(name_lengths))
# >>> [4, 5, 7]
The advantage of the lambda operator can be seen when it is used in combination with the map()
function:
squares = map(lambda x: x * x, [0, 1, 2, 3, 4, 5])
print(list(squares))
# >>> [0, 1, 4, 9, 16, 25]
This is a map that squares every number in the passed collection and does not take a named function. It
takes an anonymous, inlined function defined with lambda. The parameters of the lambda are defined to
the left of the colon. The function body is defined to the right of the colon. The result of running the function
body is implicitly returned. map() can be applied to more than one list, however, the lists must have the
same length.
1.2.2 The filter() function
filter() offers an elegant way to filter out all the elements of a sequence for which a function returns
True:
r = filter(function_to_apply, list_of_inputs)
The function filter(function_to_apply, list_of_inputs) needs a function as its first argument. This function
has to return a Boolean value and will be applied to every element of the list. The example below outputs
First, turn the map into a list…
Before Python 3, map() used to return a list, where each element of the result list was the result of
the function applied on the corresponding element of the list or tuple. With Python 3, map() returns an
iterator.
5
all the negative values in a sequence of numbers (In this example, the filter resembles a for loop but it is a
faster built-in function):
number_list = range(-5, 5)
less_than_zero = filter(lambda x: x < 0, number_list) print(list(less_than_zero)) # Output: [-5, -4, -3, -2, -1] 1.2.3 The reduce() function reduce() is a really useful function for performing some computation on a list and returning the result. While map will apply a function over a sequence, producing a sequence as output, reduce will apply a function of two arguments cumulatively to the items in a sequence, in order to reduce the sequence to a single value. In Python 3, reduce() is not a core built-in function anymore and it has been moved to functools (still part of the standard library), thus, in order to use it you need to import it like this: from functools import reduce. To illustrate how reduce works, lets use as an example the product of a list of integers. The common way this task can be programmed in python is using a basic for loop: product = 1 list = [1, 2, 3, 4, 5] for num in list: product = product * num print(product) # Output: 120 Using reduce, the code above can be written like this: from functools import reduce product = reduce((lambda x, y: x * y), [1, 2, 3, 4, 5]) print(product) # Output: 120 The function reduce((lambda x, y: x * y), [1, 2, 3, 4, 5]) continually applies the lambda function to the sequence [1, 2, 3, 4, 5] returning a single value. 1 2 3 4 5 2 6 24 120 6 At first the first two elements of the sequence will be applied to the function. In the next step the function will be applied on the previous result and the third element of the list, continuing like this until just one element is left and returning this element as the result of reduce(). 1.3 Operators There are many built-in functions in Python that accept functions as arguments. An example is the filter() function that was used previously. However, there are some basic actions that use operators instead of functions (like +, [], or . operators). The operator module provides function versions of these operators. import operator operator.add(1, 6) # Output: 7 It is possible to create functions dynamically that can know which item to get from a list: import operator get_second = operator.itemgetter(1) get_second(['a', 'b', 'c', 'd']) # Output: 'b' The itemgetter() function will return a tuple if it is given more than one index. import operator get_two = operator.itemgetter(0, 2) get_two(['a', 'b', 'c', 'd']) # Output: ('a', 'c') A typical use for the itemgetter() function is as the key argument to a list sort. import operator band = [('Guitar', 'Jimmy'), ('Vocals', 'Robert'), ('Bass', 'John'), ('Drums', 'John')] sorted(band) [('Bass', 'John Paul'), ('Drums', 'John'), ('Guitar', 'Jimmy'), ('Vocals', 'Robert')] sorted(band, key=operator.itemgetter(1)) [('Guitar', 'Jimmy'), ('Drums', 'John'), ('Bass', 'John'), ('Vocals', 'Robert')] For more operators, read https://docs.python.org/3/library/operator.html 1.4 Function Decorators A function decorator is applied to a function definition by placing it on the line before that function definition begins: @myDecorator def aFunction(): print("inside aFunction") https://docs.python.org/3/library/operator.html 7 When the compiler passes over this code, aFunction() is compiled and the resulting function object is passed to the myDecorator code, which does something to produce a function-like object that is then substituted for the original aFunction(). Function decorators are simply wrappers to existing functions. Putting the ideas mentioned above together, we can build a decorator. In this example lets consider a function that wraps the string output of another function in
tags.
def get_text(name):
return “Dear {0}, Thank you for your note…”.format(name)
def p_decorate(func):
def func_wrapper(name):
return “
{0}
“.format(func(name))
return func_wrapper
my_get_text = p_decorate(get_text)
print(my_get_text(“John”))
# Output:
Dear John, Thank you for your note…
A function that takes another function as an argument, generates a new function, augmenting the work of
the original function, and returning the generated function so we can use it anywhere. To have get_text
itself be decorated by p_decorate, we just have to assign get_text to the result of p_decorate:
def get_text(name):
return “Dear {0}, Thank you for your note…”.format(name)
def p_decorate(func):
def func_wrapper(name):
return “
{0}
“.format(func(name))
return func_wrapper
get_text = p_decorate(get_text)
print(get_text(“John”))
# Output:
Dear John, Thank you for your note…
Another thing to notice is that our decorated function takes a name argument. All what we had to do in the
decorator is to let the wrapper of get_text pass that argument. Because this is such a common programming
idiom in Python, there is a special decorator syntax to simplify its use which is to mention the name of the
decorating function before the function to be decorated. The name of the decorator should be perpended
with an @ symbol:
def p_decorate(func):
def func_wrapper(name):
return “
{0}
“.format(func(name))
return func_wrapper
@p_decorate
def get_text(name):
return “Dear {0}, Thank you for your note…”.format(name)
print(get_text(“John”))
# Output:
Dear John, Thank you for your note…
8
In other words, this Python syntax:
@some_decorator
def some_function():
# statements
is equivalent to:
def some_function():
# statements
some_function = some_decorator(some_function)
Now, imagine you want to decorate the get_text function by 2 other functions to wrap a
tag around the string output.
def get_text(name):
return “Dear {0}, Thank you for your note…”.format(name)
def p_decorate(func):
def func_wrapper(name):
return “
{0}
“.format(func(name))
return func_wrapper
def strong_decorate(func):
def func_wrapper(name):
return “{0}“.format(func(name))
return func_wrapper
def div_decorate(func):
def func_wrapper(name):
return “
“.format(func(name))
return func_wrapper
With the basic approach, decorating get_text would be along the lines of:
get_text = div_decorate(p_decorate(strong_decorate(get_text)))
print(get_text(“John”))
With Python’s decorator syntax, same thing can be achieved with much more expressive power:
@div_decorate
@p_decorate
@strong_decorate
def get_text(name):
return “Dear {0}, Thank you for your note…”.format(name)
print(get_text(“John”))
# Output:
Dear John, Thank you for your note…
One important thing to notice here is that the order of setting our decorators matters. If the order was
different in the example above, the output would have been different.
9
The examples above are a little taste of how much you can do with decorators. They can give so much
power and elegance to your program. In general, decorators are ideal for extending the behavior of
functions that you do not want to modify.
You can visit https://wiki.python.org/moin/PythonDecoratorLibrary for a great list of useful decorators.
https://wiki.python.org/moin/PythonDecoratorLibrary
10
Appendix 1. Iterators
Iterators are a Python language feature that is an important foundation for writing functional-style
programs. An iterator is an object representing a stream of data; this object returns the data one element at
a time. A Python iterator must support a method called __next__() that takes no arguments and always
returns the next element of the stream. If there are no more elements in the stream, __next__() must raise
the StopIteration exception. Iterators don’t have to be finite, though; it’s perfectly reasonable to write an
iterator that produces an infinite stream of data.
The built-in iter() function takes an arbitrary object and tries to return an iterator that will return the object’s
contents or elements, raising TypeError if the object doesn’t support iteration. Several of Python’s built-in
data types support iteration, the most common being lists and dictionaries. An object is called iterable if
you can get an iterator for it.
You can experiment with the iteration interface manually:
>>> L = [1,2,3]
>>> it = iter(L)
>>> it
<...iterator object at ...>
>>> it.__next__() # same as next(it)
1
>>> next(it)
2
>>> next(it)
3
>>> next(it)
Traceback (most recent call last):
File “
StopIteration
Python expects iterable objects in several different contexts, the most important being the for statement. In
the statement for X in Y, Y must be an iterator or some object for which iter() can create an iterator. These
two statements are equivalent:
for i in iter(obj):
print(i)
for i in obj:
print(i)
Iterators can be materialized as lists or tuples by using the list() or tuple() constructor functions:
>>> L = [1,2,3]
>>> iterator = iter(L)
>>> t = tuple(iterator)
>>> t
(1, 2, 3)
>>> L = [1,2,3]
>>> iterator = iter(L)
>>> a,b,c = iterator
>>> a,b,c
(1, 2, 3)
https://docs.python.org/3/library/stdtypes.html#iterator.__next__
https://docs.python.org/3/library/stdtypes.html#iterator.__next__
https://docs.python.org/3/library/exceptions.html#StopIteration
https://docs.python.org/3/library/functions.html#iter
https://docs.python.org/3/library/exceptions.html#TypeError
https://docs.python.org/3/glossary.html#term-iterable
https://docs.python.org/3/reference/compound_stmts.html#for
https://docs.python.org/3/library/functions.html#iter
https://docs.python.org/3/library/stdtypes.html#list
https://docs.python.org/3/library/stdtypes.html#tuple
11
Built-in functions such as max() and min() can take a single iterator argument and will return the largest or
smallest element. The “in” and “not in” operators also support iterators: X in iterator is true if X is found
in the stream returned by the iterator. You’ll run into obvious problems if the iterator is
infinite; max(), min() will never return, and if the element X never appears in the stream, the “in” and “not
in” operators won’t return either.
Note that you can only go forward in an iterator; there’s no way to get the previous element, reset the
iterator, or make a copy of it. Iterator objects can optionally provide these additional capabilities, but the
iterator protocol only specifies the __next__() method. Functions may therefore consume all of the
iterator’s output, and if you need to do something different with the same stream, you’ll have to create a
new iterator.
https://docs.python.org/3/library/functions.html#max
https://docs.python.org/3/library/functions.html#min
https://docs.python.org/3/library/functions.html#max
https://docs.python.org/3/library/functions.html#min
https://docs.python.org/3/library/stdtypes.html#iterator.__next__
12
References
https://docs.python.org/3/library/functional.html
https://docs.python.org/3/howto/functional.html
https://www.tutorialspoint.com/python/index.htm
https://pythonspot.com/en/python-lambda/
https://docs.python.org/3/howto/functional.html#iterators
https://docs.python.org/3/library/functional.html
https://www.tutorialspoint.com/python/index.htm
https://pythonspot.com/en/python-lambda/
https://docs.python.org/3/howto/functional.html#iterators