**Learning goals**

- To be able to explain precisely what a higher-order function is and what the type of a higher-order function is
- To be able to explain precisely higher-order functions on lists including map, filter, foldr and foldl
- To be able to explain and understand the recursive definitions of common higher-order functions on lists
- To be able to use higher-order functions, including map, filter , foldr and foldl , for solving programming problems in Haskell
- To be able to explain and use function composition in Haskell

## Higher-order functions

Functions that either takes a function as an argument or returns a function.

Lecture talks about

`map`

, which applies a given function to a given list

`filter`

which does the same, but selects all elements from the list that satisfy the predicate in the function.

`foldr`

(for ‘fold right’) abbreviates the below simple pattern of (primitive) recursion. Example use: `sum = foldr (+) 0`

, where the operator section `(+)`

is the operator to apply and `0`

is the base case value. Another example: `or = foldr (||) False`

.

```
f [] = v
-- <op> is some generic operator
f (x:xs) = x <op> f xs
-- Mental model for foldr
-- You can imagine it non-recursively as replacing the cons : operator with the given operator and empty list [] with the v (base case) value in the 'alternative' list representation.
-- Worked example:
sum [1,2,3,4]
-- is equivalent to
foldr (+) 0 (1:(2:(3:(4:[]))))
-- so you can imagine it just transforms it to
(1+(2+(3+(4+0))))
```

You can even define `length`

using `foldr`

:

```
-- We need to pass the lambda because this use case doesn't
-- quite match the aforementioned recursive pattern that foldr
-- matches. But by passing a lambda, we can make it work for this use case.
length = foldr (\_ n -> 1 + n) 0
-- You can imagine it doing
length [1,2,3,4]
-- being the same as
length (1:(2:(3:[])))
-- evaluates to
1+(1+(1+0))
-- resulting in
3
```

Likewise for `reverse`

:

```
reverse = foldr (\x xs -> xs ++ [x]) []
-- Explanation
reverse [1,2,3]
reverse (1:(2:(3:[])))
(([] ++ [3]) ++ [2]) ++ [1]
[3,2,1]
```

When using `foldr`

rather than explicit recursion, the GHC is able to use algebraic properties to perform program optimisations.

**The library function** `(.)`

returns the composition of two functions as a single function, i.e. function composition.

```
odd :: Int -> Bool
odd = not . even
```

**The library function** `all`

checks if every element of a list satisfies a given predicate.

**The library function** `any`

checks if any element of a list satisfies a given predicate.

**The library function** `takeWhile`

selects elements from a list while a predicate holds for all the elements.

**The library function** `dropWhile`

drops elements from a list while a predicate holds for all the elements.

`foldl`

vs. `foldr`

```
-- Imagine a function with a type like this
f :: a -> a -> a
-- And you have a list like this
[a1, a2, a3, a4]
-- A left fold does: f (f ( f a1 a2) a3) a4
-- While a right fold does: f a1 (f a2 (f a3))
-- Right fold implementation:
foldr :: (a -> a -> a) -> [a] -> a
foldr f [] = error "empty list"
foldr f [x] = x
foldr f (x:xs) f x (foldr f xs)
-- Left fold implementation:
```

# Flashcards