# Higher order functions

The material for this page was originally written for isaac computer science |

**Higher-order function**- a function that takes a function as an argument or returns a function as a result, or does both

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 |

## The map functionEdit

**Map function**- a higher-order function where a given function is applied to every element of a given list resulting in a new output list

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 (+10) [1,2,3,4,5]
[11, 12, 13, 14, 15]
.> map (^2) [20, 3, 51, 6, 3, 7]
[400,9,2601,36,9,49]
.> map (++ "!") ["scary", "weird", "spooky", "kooky"]
["scary!", "weird!", "spooky!", "kooky!"]
.> map ("NOT " ++) ["scary", "weird", "spooky", "kooky"]
["NOT scary", "NOT weird", "NOT spooky", "NOT kooky"]
.> map (replicate 2) ['a', 'b', 'c']
["aa","bb","cc"]
.> map (replicate 2) ["a", "b", "c"]
[["a","a"],["b","b"],["c","c"]]
```

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:

```
.> map minimum [[1, 3], [2, 7, 5],[9, 6]]
[1,2,6]
```

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 functionEdit

**Filter function**- a higher-order function that returns the elements of a given list that meet given criteria

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:

```
.> let list1 = [1,2,3,4,5,6,7,8,9]
.> filter (>5) list1
```

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:

```
.> let list1 = [1,2,3,4,5,6,7,8,9]
.> let list2 = filter even list1
.> list2
[2, 4, 6, 8]
.> filter odd list1
[1, 3, 5, 7, 9]
.> filter odd list2
[]
```

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 functionEdit

**Reduce/fold function**- a higher-order function that recursively applies a function to elements of a list until the list is empty

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:

```
-- [] represents the empty list,
-- and (x:xs) represents the list starting with x and where the rest of the list is xs.
-- if the list is empty, the result is the initial value; else
-- we recurse immediately, making the new initial value the result
-- of combining the old initial value with the first element.
rule 1. foldl f z [] = z
rule 2. foldl f z (x:xs) = foldl f (f z x) xs
```

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

```
foldl (*) 1 [1,2,3,4]
```

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:

```
foldl (*) (* 1 1) [2,3,4]
```

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:

```
foldl (*) (* (* 1 1) 2) [3,4]
```

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:

```
foldl (*) (* (* (* 1 1) 2) 3) [4]
```

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:

```
foldl (*) (* (* (* (* 1 1) 2) 3) 4) []
```

List `xs`

is now the empty list `[]`

. This matches *rule 1.* and z is returned:

```
(* (* (* (* 1 1) 2) 3) 4)
```

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:

```
((((1*1)*2)*3)*4)
(((1*2)*3)*4)
((2*3)*4)
(6*4)
24
```

A more condensed example of adding the values together using infix notation:

```
foldl (+) 0 [1,2,3,4]
foldl (+) (0+1) [2,3,4]
foldl (+) ((0+1)+2) [3,4]
foldl (+) (((0+1)+2)+3) [4]
foldl (+) ((((0+1)+2)+3)+4) []
((((0+1)+2)+3)+4)
((((1)+2)+3)+4)
(((3)+3)+4)
((6)+4)
10
```

Exam Questions What is a higher-order function?
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
What is the output from the Haskell command
What is the output from the Haskell command
What is the output from the Haskell command
What is the result of
What is the result of
What is the result of
What is the result of
Write down all the foldl function calls involved in the execution of
```
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
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. |