CS50 : It's functional!


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

We are learning ...
  • About the meaning of the term function
  • How to implement functions in a functional programming language
  • Applications of functional programming
So that we can ...
  • State the format of a function as f : A → B
    - A → B is the function type
    - A is called the argument type or domain
    - B is called the result type or co-domain
    - A and B are always subsets of objects
  • Functions map one set of values (domain) to another set of values (drawn from codomain)
  • Describe a function as a first class object in functional programming
  • State that a function application means a function applied to it's arguments
  • State what is meant by partial function application for one, two and three argument functions
  • State what is meant by composition of functions
  • Show experience of constructing simple programs in a functional programming language
    - Map
    - Filter
    - Reduce / fold
  • Higher order functions
  • Be familiar with representing a list as a concatenation of a head and a tail
    - The head is an element of a list
    - The tail is a list
    - The list can be empty
    - Operations (return head, return tail, test for empty list, return length of list, construct empty list, prepend an item to a list, append an item to a list)
    - Have experience writing programs for list operations in functional programming language
  • Application of functional programming to big data / distributed code

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!

Activity 1 Functions

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.

Task 1.1
Maths is fun!

Visit the Maths is Fun website and read through the following pages ...
Make notes and answer questions 1 to 10 at the bottom of each page.

OUTCOME : Notes on functionsdomain, range and codomain when applied to functions.

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 f : A ⟼ B where A is the type of the domain and B is the type of the codomain.

Task 1.2
 Function types

Describe a function, f, with the function type stated.
  1. f : Integer ⟼ Integer
  2. f : Integer ⟼ Real
  3. f : Char ⟼ Integer
  4. f : String ⟼ Integer
  5. f : Real ⟼ Bool
OUTCOME : Examples of function types stated.

Activity 2 Functional programming

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 ...
  • functions are pure - they only modify their parameters and nothing else which prevents side effects;
  • functions with no arguments are called definitions (we'd know them as assignment);
  • useful functions return a value;
  • functions are predictable - they always produce the same outputs given the same inputs;
  • there are no variables!
  • there are no loops so we have to use recursion (yuk!)

OK, OK, keep calm ... here comes the maths!

Function application

In mathematics, function application is the act of applying a function to an argument(s) 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

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's 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.

Task 2.1
 Function application

In your notebooks : Explain the meaning of function application using suitable examples which are different than the examples I have used.

OUTCOME : Your own examples of function and partial function application

Practical functional programming

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

Click to visit the Haskell Website

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.

The Glasgow Haskell Compiler (Interactive) running on Windows

Task 2.2
 Keep it simple, Haskell!

To be honest, learning a whole new programming paradigm might be a bit too much to ask at this stage. However, I would like you to have a go the first part of the first chapter of the book Learn You a Haskell for Great Good up to but not including 'An intro to lists' - we'll cover that part later.

Use WinGHCi to try out the commands that you are taught. Don't worry about evidencing what you have done but do answer the following questions in your notebooks ...
  1. How do you carry out simple mathematical operations using Haskell?
  2. What are the symbols for Boolean AND and Boolean OR in Haskell?
  3. What are the symbols for equality and inequality in Haskell?
  4. What does the Haskell succ function do?
  5. What do the Haskell min and max functions do and how many arguments do they take?
  6. How do you create a simple function in Haskell? Can you give an example?
  7. How do you use selection in functions in Haskell? Why is the else part mandatory?

I bought a copy, so should you!

OUTCOME : Simple Haskell examples to whet your appetite. 

First class objects / values

A first class object / value is any object / value that can ...
  • appear in an 'expression';
  • be assigned to or named by a variable / identifier
  • be stored in a list or a dictionary
  • be passed as arguments to a function
  • be returned from a function
... which pretty much covers everything in most modern programming languages. As you can imagine, by these definitions, all simple scalar data types such as integer, float, bool and char are first class objects and so are data structures which contain them. In Python, objects are also 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.

Task 2.3
 First class objects

Your challenge is to come up with one example of either a scalar data type (EASY), a data structure (HARDER) or a simple object (HARDEST) and demonstrate it behaving like a first class object in Python. Present your findings using a suitable combination of screenshots and written explanation.

OUTCOME : A first class object behaving like a first class object.

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)

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

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

... 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 pass a lambda function as a parameter to another function ...

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

Here, the function fourtimes is behaving as a higher order function - one which takes another function as a parameter. The most common 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.

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

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

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)
>>> myfunctions[1](2)
>>> myfunctions[2](2)

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

So is mine!

Task 2.4
 Lambda functions

Anonymous lambda functions are somewhat of a mystery to most beginning Python programmers, but not you! Try the following exercises, providing evidence of what you have done through a suitable combination of screenshots and written explanation.

  • Create a lambda function, half, which returns half of it's argument
  • Create a lambda function, reciprocal, which returns the reciprocal of it's argument
  • Create a new function, polynomial, which returns the value of 2x2+3x-4
  • Using the existing function, exponent, create a new lambda function, squareroot, which returns the square root of it's argument
  • Create a new function, incrementer, with one argument, n, which returns a lambda function taking another argument, m, which returns m + n. Use this function to create two more lambda functions, successor and predecessor
Finished? Have a quick read through 'Yet Another Lambda Tutorial' - are you a convert?

 : Some groovy lambda functions.

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 ... (save) In WinGHCi ... (reload file and execute)
-- Define double function
double :: Integer -> Integer

double x = x*2
*Main> double 4

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 ...

In the text editor ... (save) In WinGHCi ... (reload file and execute)
-- Define double function
double :: Integer -> Integer

double x = x*2

-- Define quadruple function
quadruple :: Integer -> Integer
quadruple x = double (double x)
*Main> quadruple 4

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.

In the text editor ... (save) In WinGHCi ... (reload file and execute)
-- Define double function
double :: Integer -> Integer

double x = x*2

-- Define quadruple function
quadruple :: Integer -> Integer
quadruple x = double (double x)

-- Define exponent' function
exponent' :: Float -> Float -> Float
exponent' x y = y
*Main> exponent' 2 3
*Main> cube = exponent' 3
*Main> cube 2
*Main> cube 3

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 (λ).

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

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.


Task 2.5
 Haskell functions

Using the text editor and Haskell, your task is to try to construct some of the functions as you did using Python in Task 2.4. This will help you to practice constructing explicit function types in Haskell (which is like the ones you'll see on the examination!)

  • Create a Haskell function, half, which returns half of it's argument
  • Create a Haskell function, reciprocal, which returns the reciprocal of it's argument
  • Create a Haskell function, polynomial, which returns the solution to 2x2+3x-4
  • Using the existing Haskell function, exponent', create a new Haskell function, squareroot, which returns the square root of it's argument
  • Create a new function, incrementer, which returns a lambda function taking two arguments, m and n, which returns m + n. Use this function to create two more lambda functions, successor and predecessor. (HINT : You have to surround negative numbers with brackets or else Haskell gets confused)
OUTCOME : Some groovy lambda functions.

Activity 3 Map, filter and fold

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!)


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.

The map function using a lambda function

The map function is built into the standard Python library so it's always available. 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 treat ...

>>> 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]))

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]))

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

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

The list is endless ...

Task 3.1
 Map in Python

Write map functions for the following situations. I've given you a hint on the first four ...
  • Generate a list of the lengths of names in this list ...

    names = ['Charles','Andrew','Bob','Leanne','Beatrice']

  • Generate a list of the hex codes for [85,18,171,255,0].
  • Generate a list of the types for [1,True,'Hello',12.44].
  • Generate a list of the absolute values for [-5,12,-6,10,-7,-1].
  • Use a suitable lambda function to generate a list of the successors to [1,2,3,4,5].
  • Use a suitable lambda function to add together the two vectors [3,5,4] and [1,3,4].

OUTCOME : Evidence that you can use the map function in context.

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]))
>>> [x+1 for x in [1,2,3,4,5]]


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]
Prelude> map (\x -> x+1) [1,2,3,4,5]

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

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

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]

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])
Prelude> map (\(x,y) -> maximum [x,y]) (zip [4,6,8] [1,2,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.

Task 3.2
 Map in Haskell

Write map functions for the following situations in Haskell. I've given you a hint on some of them ...
  • Generate a list of the lengths of names in this list ...

    names = ["Charles","Andrew","Bob","Leanne","Beatrice"]

  • Generate a list of the even Bools for [1,2,3,4,5].
  • Generate a list of the absolute values for [-5,12,-6,10,-7,-1].
  • Generate a list of the predecessors to [1,2,3,4,5]. Show two different ways of accomplishing this; one using a partial function and the other using a lambda function.
  • Use a suitable lambda function and the zip operator to add together the two vectors [3,5,4] and [1,3,4].
  • Use a suitable lambda function and the zip operator to find generate a list containing the minimum values of the corresponding values in [4,6,8] and [1,2,9].

OUTCOME : Evidence that you can use the map function in context.

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]]
Prelude> [maximum [x,y] | (x,y) <- (zip [4,6,8] [1,2,9])

You've already asked me that!


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 through the application of a lambda function

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))]

... 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']

Task 3.3
 The filter function in Python

Use a combination of list, filter and lambda to answer the following problems ...
  • Write a filter function which returns every third item from a list of values from 12 to 57, inclusive.
  • Write a filter function which returns only items of type bool from the list [1,2,True,3,4,False]. You can use the function body type(x) is bool in the lambda function to achieve this.
  • Declare a list of names of various length ...

    names = ['Odis','Jovan','Tinisha','Gerda','Ayesha','Dorsey','Elton','Laila','Petronila']

    ... and write a filter function which only contains names over 6 characters in length
OUTCOME : Various applications of the filter function

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.

This is getting silly. Stop asking me!

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]

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]
Prelude> filter (==3) [-5..5]

... but perfectly valid as long as the ranges are predictable!

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]
Prelude> filter (\x -> x==3) [-5..5]

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]
Prelude> [x | x <- [-5..5], x==3]

No, no no!

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]

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]

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]

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]

e) Using function composition. You should have met function composition in Task 1.1 - you might need to revise it!

Prelude> filter ((==0).(`mod` 2)) [1..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 :(

Task 3.4
 The filter function in Haskell

Use the filter function from Haskell to solve the following problems ...
  • Write a filter function which returns every odd number from the list [1..10]
  • Write a filter function which returns every third item from a list of values from 12 to 57, inclusive. You should do this in three different ways, using a lambda function, a separate function, threes and using function composition. 
  • Declare a list of names of various length ...

    names = ["Odis","Jovan","Tinisha","Gerda","Ayesha","Dorsey","Elton","Laila","Petronila"]

    ... and write a filter function to generate a list which only contains names over 6 characters in length. You should do this using a lambda function, a separate function, long, and using function composition.
OUTCOME : Various applications of the filter function in Haskell.

Reduce / Fold

Finally, the reduce (or fold) function completes our toolkit of standard functional programming, er, 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 operation using a lambda function

The reduce function is not built into the Python standard library, so it requires importation. 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)

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])

Reduce also works with strings.

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

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

Task 3.5

Use a combination of reduce and lambda to solve the following problems.
  • Write a reduce function which finds the product of [1,2,3,4,5].
  • Write a reduce function which finds the minimum number in the list [45,12,102,14,9].
  • Write a reduce function to calculate the dot product of ... [12,6,6] and [13,12,10]
  • Write a reduce function which generates an acronym for the North Atlantic Treaty Organisation.

OUTCOME : Applications for the reduce function

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 (functioninitialiser [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).

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

Demonstrating a left fold

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.

Demonstrating a right fold

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]

In essence, the foldl evaluates as (((((0+1)+2)+3)+4)+5) = 15

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

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]
Prelude> foldr (-) 0 [1,2,3,4,5]

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

Task 3.6
 Folding with Haskell

Use a the Haskell foldl function to solve the following problems.
  • Write a foldl function which finds the product (*) of [1,2,3,4,5]. (Initialiser : 1)
  • Write a foldl function which concatenates (++) the list ["H","E","L","L","O"]. (Initialiser : "")

OUTCOME : Applications for the fold function

Do not attempt this section unless you are ready for a challenge!

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. 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"]
Prelude> foldr (\a acc -> take 1 a ++ acc) "" ["British","Broadcasting","Corporation"]

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

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

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)

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")

... which explains it all, quite clearly!

... and no task!

Activity 4 List operations

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

Task 4.1
 Learn me a Haskell

Go back onto the web version of Learn You a Haskell for Great Good and continue working through the first part of the first chapter up to but not including 'Texas Ranges'.

Again, use WinGHCi to carry out the exercises in the book, reading the explanations carefully. Don't worry about evidencing your progress but do answer the following questions in your notebooks.
  1. How do you define a name in Haskell?
  2. What is the difference between the ++ operator and the : operator?
  3. Describe how you would prepend and append an item to an existing list. 
  4. What does [[],[],[]] mean?
  5. Write a Haskell command to retrieve the 4th item from the list [6,5,4,3,2]
  6. How do list comparisons work in Haskell?
  7. Draw a picture to represent the head, tail, init and last operations (don't use a caterpillar).
  8. Describe the purpose of the following list functions ...

    length, null, reverse, take, drop, maximum, minimum, sum, product, elem

OUTCOME : Descriptions of common list operations

Hello little caterpillar!

Extension Activities 

How about these?

What's next?

Before you hand your book in for checking, make sure you have completed all the work required and that your book is tidy and organised. Your book will be checked to make sure it is complete and you will be given a spicy grade for effort.