Higher order functions

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

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 function

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 function

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