Yet another programming language (and only AQA), but it's OK because we'll be using Python as well as Haskell.

We are learning ...


So that we can ...


Up until now, we have mainly been learning procedural and object-oriented programming. We dabbled a little with a declarative programming language (SQL) but now, we learn the fundamentals of a fully blown declarative language!



We have met functions before. A function is a rule which relates an input to an output. It maps values in a domain to values in a codomain. The values in the codomain to which our function maps are in the range of the function. We met this definition before when we learnt about vectors.





Function type

The domain and the codomain are also related to the function type. The type of a function states the data type of the argument the function requires (the value in the brackets) and the data type it will return. All elements in the domain must be of the same type as must all elements in the codomain.

The type of function f is written as ⨍ : A ⟼ B where A is the type of the domain and B is the type of the codomain.





Before you start, forget everything you already know about programming (eek!) You don't think imperatively and you don't code imperatively. Everything in functional programming is a function, just like everything in object oriented programming is an object (although the methods you code are imperative!) You have to think of the world as functions. Clearly, applications of functional programming lean towards mathematical problems which require lots of calculations.

In functional programming ...
useful functions return a value;


Function application

In mathematics, function applicationI have no idea what this means is the act of applying a function to argument(s), drawn from the domain, A, so as to obtain the corresponding value from its range within the codomain, B.

To define a function to

double

a value,

x

, in Python we could type ...

def double(x): return x*2

...whereas in a functional programming language, like Haskell, we write it like this ...

double x = x * 2

In imperative languages, function application is denoted using parentheses whereas in functional languages it is denoted using a space. In each case,

x

, is an argument to the function. The function is called

double

; its application is

double(x)

in Python and

double x

in Haskell.




Practical functional programming

To learn some functional programming, we're going to use a very widely implemented platform called Haskell.


You may wish to spend a little time on the tutorial that you can access by typing help in the 'Try It' section next to the lambda (λ) symbol (derived from it's history in Lambda calculus) ... see how far you can get before you get confused! To progress further, you can either install Haskell yourself on your own computer or ask your teacher to install it on your lab computers at school.

On Windows, Haskell comes with an interactive tool called WinGHCi or the Glasgow Haskell Compiler (Interactive) into which you can issue Haskell commands interactively or load and execute scripts.





First class objects / values

A first class object / value is any object / value that can ...


... which pretty much covers everything in most modern programming languages. As you can imagine, by these definitions, all simple scalarI have no idea what this means data types such as integer, float, bool and char are first class objects and so are data structures which contain them. In Python, objects also act as first class as we have seen before when we have included objects assigned to variables, stored in lists, passed as parameters to functions or returned from functions.



Lambda functions

Getting Python functions to behave like first class objects is a little more tricky because we need functions to act as values. In Python, we can use anonymous lambda functions (don't be scared). A lambda function is a 'throw-away' function that we define and use in context - it does not exist, nor can it be referenced, outside this context. We create lambda functions using the

lambda

keyword and we can assign them to variables, store them in lists, pass them to functions and return them from functions. Truly 'first class'!


Try using Lambda to create an anonymous function.

>>> lambda x : x*2
<function <lambda> at 0x02FFCC00>

This is clearly a function (because it says so) but we have no way of 'holding' onto the lambda function - it is anonymous and has no identifier! So, let's give it one.

>>> double = lambda x : x*2
>>> double(4)
8

We've created a function called double and we've assigned it straight to a variable (first class) so it acts like a value! Nooo way!! We could have done this ...

>>> def double(x):return x*2
>>> double(4)
8

...so why bother with lambda? Mainly because it's easier and clearer but mainly because it is the only sensible way (not the only way) of including a function inside another function. Seriously, you'll see the benefit of using lambda later on. We can even pass a lambda function as a parameter to another function ...

>>> def fourtimes(function,parameter):
        return function(parameter) * 2
>>> fourtimes(lambda x: x*2, 4)
16

Here, the function

fourtimes

is behaving as a higher order function - one which takes another function as a parameter. The most common (built in) higher order functions are

map

,

filter

and

reduce

/

fold

. We'll meet these later.

What about this?

>>> def exponent(n): return lambda m : m**n
>>> exponent(3)
<function exponent.<locals>.<lambda> at 0x02FFCD20>

So, the function exponent returns an actual function - this is clear (and totally first class). The function

exponent

is also behaving in a higher order fashion as it is returning a function. We certainly can't do this with normal functions (in Python at least).

If you think about it, if

exponent

returns a function rather than a value then the function has not been fully applied This is known, unsurprisingly, as partial function application - the function exponent has been partially applied and is waiting for it's missing argument,

m

.

We can complete the application of the function by using it to create other functions, like this ...

>>> cube = exponent(3)
>>> cube(2)
8
>>> cube(3)
27

Wow! Like, wow! The function

cube

, completed the application of the function exponent by providing the final argument that it needs. Nice!

Finally, let's create a list of anonymous functions and access them like value 🤯 to complete our proof of first classness!

>>> myfunctions = [lambda n:n*1,lambda n:n*2,lambda n:n*4]
>>> myfunctions[0](2)
2
>>> myfunctions[1](2)
4
>>> myfunctions[2](2)
8

Here, we've seen lambda functions behaving in a truly first class fashion. Nice.





Luckily, if we use Haskell, we don't generally have to use lambda functions for simple operations like this because in Haskell, the way that functions are defines is quite lambda like anyway. The safest way to conduct the next set of exercises is to use a script rather than the interactive console. Often Haskell requires you to be more explicit about the function types that you are defining and you can't define function types in Haskell at the interactive prompt 😔


Using your favourite text editor, create the a script called activity2.hs and save it in a suitable place. Make sure that the file extension is correct and close down your text editor. Now open up WinGHCi (if you haven't done already) and choose 'File > Load' and load in the script you have created. These are the two toolbar buttons you'll need next ...


Once the file is loaded, hit the 'Run Text Editor' button and Notepad should appear, as if by magic. Use WinGHCi and the default text editor to carry out the following tasks. Edit the script in the text editor, click save and then click the 'Reload Script' button before executing the commands given at the interactive prompt. Here we go ...

We can define the same double function in Haskell like this ...


In the text editor, you declare the function type explicitly so that Haskell knows what data type to expect and what data type it's meant to return. We can then use this double function in another function ...


This is a very simple example of a very common pattern you see in Haskell where basic functions are designed and combined to create more complex functions. Partial function application in Haskell is also straightforward. The exponent examples we saw before is easy but we need to make sure we declare a specific function type to allow us to perform all the operations we did with Python before.


Notice the the prime (') character after the

exponent'

function name. The prime has no special meaning in this context (although it is used to prevent laziness in functions when doing fierce recursion) and hence we can use it in function names. There is already a function built into Haskell called exponent so adding the prime after our function denotes that it's a slightly modified version. This example won't work without it being there because Haskell will try to use the built in function.


For the next section, unload the script by typing

:m

at the

*Main>

prompt and pressing ENTER and you should have your

Prelude>

prompt back again. Lambda functions in Haskell are declared similarly to the way they are in Python but since they are generally used 'on the fly', we'll define them at the interactive prompt rather than in a script. Lambdas are prefixed with a back slash (\) because it looks like a Greek letter lambda (λ), I suppose.

Prelude> multiplier = \x n -> x*n
Prelude> doubler = multiplier 2
Prelude> doubler 4
8
Prelude> tripler = multiplier 3
Prelude> tripler 4
12
Prelude> halver = multiplier 0.5
Prelude> halver 4
2.0

Don't worry too much if you aren't really following this (I wouldn't be surprised). Later on when we look at the main higher order functions

map

,

filter

and

reduce

/

fold

, you'll see how these can be used in context.







The three most common functions which facilitate a functional approach to programming in Python are

map

,

filter

and

reduce

. These three higher order functions form the backbone of most applications of functional programming in the field of big data, and they also make extensive use of the anonymous lambda functions we've just been learning about in the last activity (which is why we learnt about them!)


Map

The map function takes a list of values from a domain and applies a function to each value in the list, mapping the value to a range in the subdomain (remember them?)



The map function is built into the standard Python library so it's always available (noice). The blueprint is ...

map(function, *iterable) --> map object

The

map

object can be converted into list using the

list(object)

function. The function passed to

map

can be a built-in Python function. For instance, this

map

operation converts a string to a list of ASCII codes.

>>> list(map(ord,'Hello there!'))
[72, 101, 108, 108, 111, 32, 116, 104, 101, 114, 101, 33]

... and this one converts a list of numbers into a list of strings.

>>> list(map(str,[1,2,3,4,5]))
['1', '2', '3', '4', '5']

If the function takes more than one parameter, simply pass

map

multiple lists. For instance, for the power function,

pow(x,y)

which takes two arguments (and is equivalent to

x**y

) can be applied using a map function across two lists of values ...

>>> list(map(pow,[5,4,3,2,1],[1,2,3,4,5]))
[5, 16, 27, 16, 1]

Consider this mathematical delight ...

>>> import math
>>> list(map(math.sin,[34,54,65]))
[0.5290826861200238, -0.5587890488516163, 0.8268286794901034]

As you can imagine, you can also put lambda functions in the

map

function to achieve more complex functional application. For example a simple

map

function which squares every value in a list ...

>>> list(map(lambda x:x**2, [1,2,3,4,5]))
[1,4,9,16,25]

It's common to separate the function from the map operation, which would be especially useful if the function was more complicated. For instance ...

>>> double = lambda x:x**2
>>> list(map(double,[1,2,3,4,5]))
[1,4,9,16,25]

We can also design a map function which capitalises every letter in a string.

>>> ''.join(list(map(lambda x:chr(ord(x)-32),'hello')))
'HELLO'

The list is literally endless ...




It's worth noting that the result of the map function can be achieved using list comprehensions. For instance, both these statements are equivalent ...

>>> list(map(lambda x:x+1,[1,2,3,4,5]))
[2,3,4,5,6]
>>> [x+1 for x in [1,2,3,4,5]]
[2,3,4,5,6]

In Haskell, the map function is structured like this ...

map (function) [list]

The function can be a simple partial application like

(+1)

or a lambda function like

(\x -> x + 1)

. Both these functions are equivalent. Look ...

Predule> map (+1) [1,2,3,4,5]
[2,3,4,5,6]
Prelude> map (\x -> x+1) [1,2,3,4,5]
[2,3,4,5,6]

Haskell has many built in functions which we can use in the map function. For instance ...

Prelude> map (odd) [1,2,3,4,5]
[True,False,True,False,True]

Unfortunately, you can only provide one list as an argument to the Haskell

map

function, unlike Python, so you have to engage in some pretty funky tricks to get it to handle more complex situations where you might want to give the function multiple parameters.

Prelude> zip [5,7,6] [1,4,5]
[(5,1),(7,4),(6,5)]

The

zip

function takes two lists and creates a single list of tuples (you'll recognised the difference between lists and tuples from Python, I'm sure). Then, we can throw our list of tuples into the

map

function to do some groovy things.

Prelude> map (\(x,y) -> abs(x-y)) (zip [5,8,3] [6,6,6])
[1,2,3]
Prelude> map (\(x,y) -> maximum [x,y]) (zip [4,6,8] [1,2,9])
[4,6,9]

The first example generates a list of the absolute difference between related values in the lists and the second example generates a list of the maximum related values from the lists. Nice.





Once again, it's worth noting that the same can be achieved using list comprehensions. We haven't looked at list comprehensions in Haskell yet (and neither are we going to), however, you should be able to apply simple patterns using these examples. Notice the left facing '

<-

' which means 'is drawn from'.

Prelude> [x+1 | x <- [1,2,3,4,5]]
[2,3,4,5,6]
Prelude> [maximum [x,y] | (x,y) <- (zip [4,6,8] [1,2,9])
[4,6,9]

Filter

The

filter

function takes a list of values and applies a conditional filter to it using a lambda function. The value from the list will be returned if, and only if, the result of the function is

true

.



The filter function is also built into the Python standard library, so it's always available. The blueprint is ...

filter(function, iterable) --> filter object

Where the function is a conditional statement which returns

true

or

false

. Common uses include, extracting even numbers from a list ...

>>> list(filter(lambda x:x%2==0,range(1,21))
[2, 4, 6, 8, 10, 12, 14, 16, 18, 20]

... extracting odd numbers from a list ...

>>> list(filter(lambda x:x%2==1,range(1,21)))
[1, 3, 5, 7, 9, 11, 13, 15, 17, 19]

You can truncate a list based in the value ...

>>> list(filter(lambda x:x>0,range(-5,5))]
[1,2,3,4]

... and even use string operations to search for matching values in a list or words.

>>> names = ['Anne', 'Amy', 'Bob', 'David', 'Carrie', 'Barbara', 'Zach']
>>> list(filter(lambda s: s.startswith('B'), names)
['Bob', 'Barbara']
>>> list(filter(lambda s: 'a' in s.lower(), names)
['Anne', 'Amy', 'David', 'Carrie', 'Barbara', 'Zach']

It is worth noting that you can achieve pretty much the same outcomes using list comprehensions. For instance, we can generate our list of even and odd numbers like this ...

>>> [x for x in range(1,21) if x%2 == 0]
[2, 4, 6, 8, 10, 12, 14, 16, 18, 20]
>>> [x for x in range(1,21) if x%2 == 1]
[1, 3, 5, 7, 9, 11, 13, 15, 17, 19]

... which some programmers find easier / clearer.


In Haskell, we use the

filter

function in a similar way. This is the blueprint ...

filter (predicate) [list]

... where the

predicate

is a conditional statements which returns

true

or

false

and is applied to each element of the list. If the predicate is

true

, the list value is returned, if it is

false

, it is not. The

filter

function returns a list of values which satisfy the predicate.

We can filter out all odd values from a list like this ...

Prelude> filter (even) [1,2,3,4,5]
[2,4]

Notice the result of the application of even in this case is very different to that of its use in the

map

function. The predicate can look like part of a conditional statement, as in these examples ...

Prelude> filter (>0) [-5..5]
[1,2,3,4,5]
Prelude> filter (==3) [-5..5]
[3]

Both these predicates are statements not functions (technically,

>

and

==

are functions but we'll ignore that for now) and take parameters in a prefix fashion, i.e. before the operator. So

>0

is like

x>0

. So, these are equivalent to the following filter operations using lambda functions ...

Prelude> filter (\x -> x>0) [-5..5]
[1,2,3,4,5]
Prelude> filter (\x -> x==3) [-5..5]
[3]

Once again, it's worth noting that we can use list comprehensions in Haskell to achieve the same outcome ...

Prelude> [x | x <- [-5..5], x>0]
[1,2,3,4,5]
Prelude> [x | x <- [-5..5], x==3]
[3]

We could define a slightly more complicated (and totally pointless) even number filter in three slightly different ways (just to prove some points and introduce some other points) ...

a) Using the built in even function as the predicate. We've seen this before 😄

Prelude> filter (even) [1..10]
[2,4,6,8,10]

b) Using a lambda function. This uses the Haskell mod operator which prefixes it's arguments.

Prelude> filter (\x -> mod x 2 == 0) [1..10]
[2,4,6,8,10]

c) Using a lambda function. I've modified the mod operator to an infix operator by surrounding it with backticks.

Prelude> filter (\x -> x `mod` 2 == 0) [1..10]
[2,4,6,8,10]

d) Defining a separate function and using that as the predicate. Sometimes better, sometimes not.

Prelude> evens x = mod x 2 == 0
Prelude> filter (evens) [1..10]
[2,4,6,8,10]

e) Using function composition. You should have met function composition in Task 1.1...

Prelude> filter ((==0).(`mod` 2)) [1..10]
[2,4,6,8,10]

The predicate is evaluated from right to left. For each value in the list, the result of the

mod

operation is passed to the

==0

statement. If the output of that is

True

, the value is added to the filtered list.

 1 :  1 `mod` 2 = 1 -> 1 == 0 -> False
 2 :  2 `mod` 2 = 0 -> 0 == 0 -> True -> Add 2
 3 :  3 `mod` 2 = 1 -> 1 == 0 -> False
 4 :  4 `mod` 2 = 0 -> 0 == 0 -> True -> Add 4
 5 :  5 `mod` 2 = 1 -> 1 == 0 -> False
 6 :  6 `mod` 2 = 0 -> 0 == 0 -> True -> Add 6
 7 :  7 `mod` 2 = 1 -> 1 == 0 -> False
 8 :  8 `mod` 2 = 0 -> 0 == 0 -> True -> Add 8
 9 :  9 `mod` 2 = 1 -> 1 == 0 -> False
10 : 10 `mod` 2 = 0 -> 0 == 0 -> True -> Add 10

Even though we learnt that the open circle (∘) represents function composition, there is no open circle available to show this in Haskell (or any other language), so the dot is used. Sorry 😔



Reduce / Fold

Finally, the

reduce

(or

fold

) function completes our toolkit of standard functional programming tools. Unfortunately, the

reduce

function is not built into the standard Python library so we need to import it ...

from functools import reduce

...before we can use it. Basically, reduce takes a list and, through the application of a function, reduces the list to a single value.



The

reduce

function is not built into the Python standard library, so it requires importation before we can use it. The blueprint is ...

reduce(function, iterable[, initialiser])

The function takes two arguments due to the way it operates on the list. Consider this simple

reduce

operation which adds up a list of numbers.

>>> reduce(lambda x,y:x+y,[1,2,3,4,5],0)
15

The operation of

reduce

is essentially

(((((0+1)+2)+3)+4)+5)

folding from the left side of the list (technically a left fold). The fold operation is recursive. Starting with the (optional) initialiser, the function adds this to the first item in the list, then adds the result of this addition to the second value in the list and so on until only one value is left which it returns.

You can also use

reduce

to work out the maximum number in a list of values.

>>> reduce(lambda a,b:a if a>b else b, [45,12,102,14,9])
102

The

reduce

function also works with strings.

>>> names = ['British','Broadcasting','Corporation']
>>> reduce(lambda a,b:a+b[0],names,'')
'BBC'

Notice that the initialiser for this operation is an empty string. Try it without that and see what happens (lol).





There is no reduce function in Haskell 🙄; it's called

fold

. In fact there are two different fold functions in Haskell,

foldl

(fold left) and

foldr

(fold right). They both operate recursively eating up values from the left hand side and the right hand side of the list respectively.

The blueprint for the functions is ...

foldl (function) initialiser [List]
foldr (function) initialiser [List]

The initialiser gives a special variable called the accumulator its initial value. The

foldl

function recursively adds the accumulator to each item in the list whereas the

foldr

function recursively adds each item in the list to the accumulator (i.e. the reverse). READ THAT AGAIN.

Here is a nice way of looking at both situations based on a common food chain.


In a left fold, the food chain is accumulated from the owl to the grass; from left to right. The owl eats the mouse, then the owl (which has eaten the mouse) eats the grasshopper and finally the owl (which has eaten the mouse and the grasshopper) eats the grass.


In a right fold however, the food chain is accumulated from the grass to the owl; from right to left. The grasshopper eats the grass then the mouse eats the grasshopper (which has eaten the grass) then the owl eats the mouse (which has eaten the grasshopper which has eaten the grass). In any event, the owl is full up.

Enough about food. Consider these two real examples ...

Prelude> foldl (+) 0 [1,2,3,4,5]
15

In essence, the

foldl

evaluates as

(((((0+1)+2)+3)+4)+5) = 15

Prelude> foldr (+) 0 [1,2,3,4,5]
15

In essence, the

foldr

evaluates as

(1+(2+(3+(4+(5+0))))) = 15

In this instance, the order of the fold makes no difference to the result since addition is commutative (order is unimportant). However, subtraction is not and the following two functions yield very different results.

Prelude> foldl (-) 0 [1,2,3,4,5]
-15
Prelude> foldr (-) 0 [1,2,3,4,5]
3

Why does this happen? Let's evaluate the expression manually to find out ...






This situation gets even more complicated with function composition and we are really getting way out of our depth here! However, when we were using Python, we managed to generate an acronym for the British Broadcasting Corporation using a Lambda function. However, the same process in Haskell is slightly more confusing (but I feel duty bound to tell you about it). The

foldl

and

foldr

functions evaluate composed functions in the reverse order so, to get the same outcome, we have ...

Prelude> foldl (\acc a -> acc ++ take 1 a) "" ["British","Broadcasting","Corporation"]
"BBC"
Prelude> foldr (\a acc -> take 1 a ++ acc) "" ["British","Broadcasting","Corporation"]
"BBC"

However, trying to use normal function composition causes problems ...

Prelude> foldl ((++).(take 1)) "" ["British","Broadcasting","Corporation"]
"BCorporation"
Prelude> foldr ((++).(take 1)) "" ["British","Broadcasting","Corporation"]
"BBC"

The

foldl

function evaluates like this :

(take 1 (take 1 (take 1 "" ++ "British") ++ "Broadcasting") ++ "Corporation)
(take 1 (take 1 "British" ++ "Broadcasting") ++ "Corporation)
(take 1 "BBroadcasting" ++ "Corporation)
"BCorporation"

The

foldr

function evaluates like this :

(take 1 "British" ++ (take 1 "Broadcasting" ++ (take 1 "Corporation")))
(take 1 "British" ++ (take 1 "Broadcasting" ++ "C"))
(take 1 "British" ++ "BC")
"BBC"

... which explains it all, quite clearly!



Back to Haskell for this last section and the fabulous 'Learn You a Haskell for Great Good' - my favourite book!






How about these?

END OF TOPIC ASSESSMENT