# A-level Computing/AQA/Paper 2/Fundamentals of functional programming/Higher order functions

Higher-order functions are functions that take one or more functions as arguments or return as function as a result. Three common higher order functions are the map, filter and reduce/fold functions:
* Extension: Functors and non-list mapping
* Whilst the examples here are about using the map, filter and reduce/fold functions with lists, other data types can used instead of lists. For example you might map a function across the elements of a tree. In Haskell anything of the Functor type class can be used in a map function.

## The map function

The map function is given a list and a function to apply to the list. It applies this given function to every element in the given list, creating a new list, that is then returned. Another way of defining map, is that it maps each item of the given list to the output list:
Map can also work on a list of lists, where the function that is being mapped is applied to each sub list in turn. For example if you wanted to find the smallest value from a set of lists, you could write:
Note here that we appear to have a smaller list than we started with. Whilst this is true in terms of the length of the inner lists, which each now have one item, the original list passed to the map function had three items (lists [1, 3], [2, 7, 5], [9, 6]), and the returned list also has three items ([1,2,6]).

## The filter function

The filter function is passed a list and filter criteria, it applies the filter criteria to the list, returning a list of items that match the filter criteria. The filter criteria is sometimes called a predicate function, where TRUE or FALSE is returned from applying the criteria to each element of the original list. In Haskell this is performed using the filter command, for example:
This looks at each item in list1 and checks whether they are greater than 5. Setting those that are to True and those that aren't to False:
    [1,2,3,4,5,6,7,8,9]
    [F,F,F,F,F,T,T,T,T]
It returns the list of all the items that are True:
    [6,7,8,9]
Other filter examples with the odd and even commands:
Other programming languages might not have a filter command but might achieve similar output by using select case, switch, if then else.

## The reduce or fold function

The reduce or fold function takes as inputs a list, a function to apply to the list and a start value. There are two types of fold command, the foldl and foldr, the examples here are using foldl.
Fold applies the given function to the first element of the list (starting from the left) and the start value and then applies the fold command to result of this and the remainder of the list. It does this recursively until the fold command is applied to an empty list, at which point it returns the calculated value. Another way of describing this, from the Haskell wiki:
To see this in action, look at the haskell command foldl (*) 1 [1,2,3,4], this code will recursively multiply the elements of a list together
this matches rule 2. f = *, z = 1, x = 1, xs = [2,3,4]. As the list on the right of the command, xs, isn’t empty, we therefore do the following
foldl f z (x:xs) = foldl f (f z x) xs
This makes the next call:
List xs isn't empty so we apply rule 2. again, with f = *, z = * 1 1, x = 2, xs = [3,4]. The next call is:
List xs isn't empty so we apply rule 2. again, with f = *, z = * (* 1 1) 2, x = 3, xs = [4]. The next call is:
List xs still isn't empty so we apply rule 2. again, with f = *, z = * (* (* 1 1) 2) 3, x = 4, xs =. Therefore the the next foldl call is:
List xs is now the empty list. This matches rule 1. and z is returned:
We can rewrite the prefix notation (e.g. * 1 1) as infix notation (e.g. 1 * 1), and calculate the brackets out, starting at the innermost brackets:
A more condensed example of adding the values together using infix notation:
* Exam Questions
* What is a higher-order function?
* Answer:
* a function that takes a function as an argument or returns a function as a result, or does both
* What is the output from the Haskell command filter (>5) [32, 32, 1, 3, 5, 31, 3, 5, 212]?
* Answer:
* [32, 32, 31, 212]
* What is the output from the Haskell command filter (odd) [32, 32, 1, 3, 5, 31, 3, 5, 212]?
* Answer:
* [1, 3, 5, 31, 3, 5]
* What is the output from the Haskell command map ('+' :) ["good", "excellent", "brill"]?
* Answer:
* ["+good","+excellent","+brilliant"]
* Note: using single quotation marks on the '+' operator means we can use the prepend command. It treats the '+' as a single item. This code doesn't work with "+" as it treats the "+" as a list, and prepend cannot deal with lists as the first item.
* What is the output from the Haskell command map (+5) (filter (<30) [29, 31, 30])?
* Answer:
* [34]
* What is the result of foldl (+) 6 [9, 2, 13]
* Answer:
* 30
* What is the result of foldl (*) 1 [2, 3, 4]
* Answer:
* 24
* What is the result of foldl (^) 1 [2, 3, 4]
* Answer:
* 1
* What is the result of foldl (^) 2 [2, 1, 2, 1]
* Answer:
* 16
* Write down all the foldl function calls involved in the execution of foldl (^) 2 [3, 2, 1]
* Answer:
* foldl (^) 2 [3, 2, 1]
* foldl (^) (2^3) [2, 1]
* foldl (^) ((2^3)^2) [1]
* foldl (^) (((2^3)^2)^1)
* (((2^3)^2)^1)
* (((8)^2)^1)
* ((64)^1)
* 64
* Describe the difference between a first-class object and a high-order function
* Answer:
* A first class object is an object which can be passed as an argument or returned by a function. A higher order function can accept another function as an argument.