6. Lecture 3a - Functional Patterns (Python Version)#
Functional programming means thinking in terms of mathematical functions. Strict functional programming languages, such as Haskell, Idris, F#, OCaml, and scala provide abstractions for functions which a very similar to their mathematical counterparts. However, most programming languages do not do this so well. Does this mean that the idea of modelling our abstractions in terms of mathematical functions is inappropriate when using these languages ?
A basic assumption of this course is that, at least for many modern programming languages, this is not the case. The key to making this approach work is to understand the differences between a mathematical function and a function within the language being used, and then find effective ways of working around these differences.
What then are the minimal requirements of a programming language for it to be able to support the use of functional patterns ? The primary requirement is the availablity of Higher Order Programming.
6.1. Higher Order Programming#
Higher Order Programming perhaps sounds more impressive than it actually is. Put simply it means that functions and other “higher order” types can be passed to and returned from functions in the same way as more traditional data e.g. floating point numbers and strings.
6.1.1. Example#
from math import sin,pi
def g(f,x) :
return f(x)
g(sin,pi/6)
0.49999999999999994
6.1.2. Example#
def f(a) :
def g(x) :
return x + 2
return g if a == 1 else sin
f(2)(5)
-0.9589242746631385
f(1)(5)
7
Notice that in the second example a new function g is defined inside an enclosing function f.
When higher order programming is available most of the main functional design patterns can be implemented in some form.
6.2. Pattern 1 - Composition#
6.2.1. Exercise#
Write a function compose which accepts two functions f and g and returns a function h where $\(h(x) = f(g(x))\)$
6.2.2. Solution#
Show code cell source
def compose(f,g) :
def h(x) :
return f(g(x))
return h
def f(x) :
return 2*x
def g(x) :
return x + 2
h = compose(f,g)
print(h(3))
h = compose(g,f)
print(h(3))
Show code cell output
10
8
6.2.3. Exercise#
What limitations, if any, are there with your implementation of the compose function ?
6.2.4. A more versatile compose#
from functools import reduce
def compose(*funcs):
return reduce(lambda f,g : lambda x : f(g(x)), funcs, lambda x : x)
h = compose(f,g,sin,g,f)
h(3)
5.978716493246764
6.3. Pattern 2 - Currying#
In mathematics a function \(f\) can be completely specified in terms of its graph \(\Gamma_{f}\). The graph is a (possibly infinite) set of ordered pairs, for example
\(\Gamma_{f} = \left\{ (1,1),(2,4),(3,9) \right\}\)
Conceptually the graph shows how to map the first element of a given pair to the second. This is emphasised through the notation \(f(1) = 1\) and \(f(3) = 9\) and so on.
6.3.1. Exercise#
Give a small example of a graph of function of the form \(f(x,y)\).
Write a function in python that implements it.
How many “arguments” does the mathematical function “take” ?
How many “arguments” does your python function “take” ?
So, mathematical functions map single entities to single entities. To make python functions behave in this way they can be curried. Here is an example.
from pymonad.tools import curry
@curry(2)
def f(x,y) :
return x + y
z = f(2,3) # function taking two arguments ???? No.
print(z)
5
g = f(2) # f is a function of one argument that returns a function
z = g(3) # g is a function (with one argument)
print(z)
5
z = f(2)(3)
print(z)
5
The “curry” pattern is slightly odd in that most functional programming languages do not need it since functions are curried by design.
6.3.2. Exercise#
How can currying be put to practical use ?
6.3.3. Solution#
Currying allows a programmer to provide a way of adding extra parameters to a function whilst still allowing it to be Reused in other code. A strategy in the pig game provides an excellent example of a use case for the curry pattern.
6.3.4. Exercise#
Try and use curried strategies in your pig competition code.
6.4. Pattern 3 - Partial Application#
Closely related to Currying, partial application accepts a function, freezes one or more of its arguments , and returns a new function with a reduced number of arguments. The frozen arguments are often referred to as the “bound” arguments or “bound” values.
def f(a,b,c) :
return (2**a)*(3**b)*(5**c)
f(2,3,2)
2700
from functools import partial
g = partial(f,b=3)
g(a=2,c=2)
2700
6.4.1. Exercise#
How does partial application differ from Currying ?
What effect does the position of the “bound” arguments have on the way the partially applied function is used ?
6.5. Pattern 4 - Classes and Objects#
6.5.1. Motivating Problem#
Here is a simple function
def f(x) :
return 2*x
Now imagine you want to keep track of how many times this function gets used in a big program.
6.5.2. Solution#
count = 0
for i in range(10) :
f(i)
count = count + 1
# ... lots more code
# ...
# somewhere else in your program
y = f(8)
count = count + 1
# ... lots more code
# ...
# somewhere else in your program
z = f(3)/2
count += 1
# ... lots more code
# ...
### and finally
print("f was called " + str(count) + " times")
f was called 12 times
6.5.3. Exercise#
What are the potential problems with this solution ?
Broadly speaking, how would you score this solution with respect to the 5Rs ?
6.5.4. Exercise#
Design an alternative approach counting the number of times f gets used.
Does your approach have any advantages over the original solution ?
How would you rate your solution with respect to the 5Rs
6.5.5. Exercise#
Consider the following function
def agent() :
state = 0.71
def update(x) :
nonlocal state
state = sin(state)
return x*state
return update
and see if you can predict what the following code does.
agent_1 = agent()
agent_2 = agent()
print(agent_1(1))
print(agent_2(1))
print(agent_1(1))
print(agent_1(1))
print(agent_2(1))
Show code cell output
0.6518337710215366
0.6518337710215366
0.6066452227835972
0.5701145050885391
0.6066452227835972
6.5.6. Closures, Classes, and Objects#
The function logf is called a closure. It is a function. However, it is a function with extra information. The extra information is provided by the enclosing scope of the function (f in this case) within which the (nested) function g is defined.
In general, a function that returns other functions is called a class, and the functions returned are called objects. If the objects have access to the data inside the scope of the class then they are closures. Note a closure is not a nested function, it is the object that corresponds to the nested function that is the closure.
A program that makes use of classes and objects employs the programming paradigm known as object based programming.
6.5.6.1. Exercise#
Think of, and then describe, some use cases for object based programming.
6.5.7. Example#
Show code cell source
def logger(f) :
count = 0
def call(x) :
nonlocal count
count += 1
return f(x)
def log() :
nonlocal count
return count
return call,log
6.5.7.1. Exercise#
How do you think the logger class might be used ?
How does using the logger class rate as a solution to the motivating problem ?
What problem(s) does using the logger class present ?
Can you modify the logger class to overcome this problem(s) ?
6.5.7.2. Solution#
Show code cell source
call,log = logger(f)
for i in range(10) :
call(i) ## function gets used in the same way as the original
log()
Show code cell output
10
6.6. Pattern 5 - Memoisation#
Memoisation is an example of an object based pattern. Here is a way it might be implemented in python.
def memoise(f) :
cache=dict()
def mf(x) :
nonlocal cache
if not x in cache :
cache[x] = f(x)
return cache[x]
return mf
6.6.1. Exercise#
Can you work out what this pattern is designed to do ?
Experiment with the following code to see what memoisation does.
def f(x) :
print("calling f")
return 2*x
y = f(3)
print(y)
y = f(3)
print(y)
Show code cell output
calling f
6
calling f
6
mem_f = memoise(f)
y = mem_f(3)
print(y)
y = mem_f(3)
print(y)
Show code cell output
calling f
6
6
6.6.2. Exercise#
Think of, and describe, some use cases for memoisation.
6.6.3. Exercise#
If you can, have a go at implementing memoisation in another language.
6.6.4. Exercise#
Are there any obvious problems with the memoise function presented above ?
6.6.5. A more robust implementation of memoisation#
from functools import cache
@cache
def g(x,y) :
print("adding !!")
return x +y
g(1,2)
g(3,4)
g(1,2)
adding !!
adding !!
3
6.7. Map, Filter, Reduce#
6.7.1. Map#
Map is a higher order function that applies a function to each member in a sequence
\({\bf map} : (X \rightarrow Y) \times [ X ] \rightarrow [ Y ]\)
Pythons implementation of map returns an iterator type which can be used to construct a sequence of the required type from the iterator.
6.7.1.1. Exercise#
What do yo think the result of the following code will be ?
@curry(2)
def f(x,y) :
return x + y
list(map(f(3),[1,2,3,4,5]))
[4, 5, 6, 7, 8]
The application of the map pattern has several advantages over an imperative loop. Firstly, it can be composed with other functions. Secondly, since it is a function it can be curried over its first arguments to provide a “vectorised” of the underlying function. And thirdly, it is readily parallelisable.
6.7.2. Parallel Map#
#### setup a pool of processors
from multiprocess import Pool
p = Pool(4) # use 4 processors
list(p.map(f(3),[1,2,3,4,5])) # executes f in parallel
[4, 5, 6, 7, 8]
#### free up the processors
p.close()
It might be difficult to appreciate the above example since each call of the underlying function takes very little time to run.
6.7.2.1. Exercise#
Try running the following function using parallel map. How long do you expect it to take ?
@curry(2)
def f(t,x) :
from time import sleep
sleep(t)
return 3*x
6.7.2.2. Solution#
Show code cell source
p = Pool(5) # use 5 processors
results = list(p.map(f(5),[1,2,3,4,5,6,7,8,9,10,11])) # executes f in parallel
p.close
print(results)
Show code cell output
[3, 6, 9, 12, 15, 18, 21, 24, 27, 30, 33]
6.7.3. Reduce#
Reduce is a higher order function that uses a binary operator to combine the values in a sequence into a single value.
\({\bf reduce} : (X \times X \rightarrow X) \times [ X ] \rightarrow X\)
Pythons implementation of reduce returns an iterator type which can be used to construct a sequence of the required type from the iterator.
6.7.3.1. Exercise#
Predict the result of running the following code.
from functools import reduce
def g(x,y) :
print(x,y)
return x + y
reduce(g,[4,3,2,1])
Show code cell output
4 3
7 2
9 1
10
6.7.4. Filter#
The filter pattern removes elements form a sequence depending on the value of a predicate function.
\({\bf filter} : X \rightarrow \left\{true,false\right\} \times [X] \rightarrow [X]\)
Pythons implementation of filter returns an iterator type which can be used to construct a sequence of the required type from the iterator.
6.7.4.1. Exercise#
Predict the result of running the following code.
def h(a) :
return a > 5
list(filter(h,[1,2,3,4,5,6,7,8,9]))
Show code cell output
[6, 7, 8, 9]
6.7.5. Combining Map, Reduce, and Filter#
The utility of map, filter, and reduce becomes very apparent when they are curried.
cmap = curry(2,map)
creduce = curry(2,reduce)
cfilter = curry(2,filter)
6.7.5.1. Exercise#
Predict the result of running the following code.
method = compose(creduce(g),cfilter(h),cmap(f(1)))
method([1,2,3,4,5,6,7,8,9])
Show code cell output
6 9
15 12
27 15
42 18
60 21
81 24
105 27
132
6.7.5.2. Exercise#
Implement the above code using an imperative style.
A parallel version of map can also be curried. For example.
@curry(3)
def pmap(f,cores,args) :
with Pool(cores) as p:
result = p.map(f, args)
p.close()
return result
6.7.5.3. Example#
The parallelised solution to the previous exercise is then
method = compose(creduce(g),cfilter(h),pmap(f(1))(5))
method([1,2,3,4,5,6,7,8,9])
6 9
15 12
27 15
42 18
60 21
81 24
105 27
132
You are invited to reflect on how concise and readable the previous example is given what it achieves.
6.8. Practical Considerations#
As some of the examples above demonstrate, it is certainly possible to employ certain functional patterns using programming systems which, in themselves, do not have all the characteristics of a fully functional system. However, it is important to note certain limitations that arise in non-functional systems. In particular, most “fully” functional languages have the following
pure functions
immutable data structures
strong type systems
For now, the first two are the most important to consider.
6.8.1. Pure Functions#
What are pure functions ? A pure function does not modify any existing data or arguments. As a consequence they are like a mathematical functions in that they always give the same outputs for the same inputs, and they do not change anything when evaluated. For example, the following function is not pure.
6.8.1.1. Example#
def impure_function(X) :
X.append(1)
return X
X = [1,2,3,4,5]
print(X)
Y = impure_function(X)
print(Y)
print(X)
[1, 2, 3, 4, 5]
[1, 2, 3, 4, 5, 1]
[1, 2, 3, 4, 5, 1]
Not all languages behave in this way. For example, compare the following R version of the above function
pure_function <- function(X)
{
X <- c(X,5)
return(X)
}
X = list(1,2,3,4)
head(X)
Y <- pure_function(X)
head(Y)
head(X)
6.8.1.2. Exercise#
How would you make the python version of pure_function ?
6.8.2. Immutability#
In most functional programming languages data is immutable. Once a value has been created and assigned to a variable it cannot be changed - ever !!
How can this possibly work ? Every time you need to change some data you have to have a function that takes the data and generates a modified copy of it - simples !!
But how can this possible be efficient ? Behind the scenes a full copy is not actually made, just a record of the modification and which parts of the program can see this modification. In fact, this is how the R version of pure_function works (the original data in the list will not have been copied). To achieve this, R uses a model called copy on write, or COW.
6.8.3. Immutability and state#
How can state be modelled without immutability ?
def counter(count = 0) :
def bump() :
nonlocal count
return counter(count+1)
def counts() :
nonlocal count
return count
return bump,counts
6.8.3.1. Example#
bump_1,counts_1 = bump_2,counts_2 = counter()
bump_2,counts_2 = bump_2()
print(counts_1())
print(counts_2())
0
1