# Higher-order functions

Higher-order functions are functions that take other function(s) as their argument(s). This mechanism allows functional languages to be more expressive and powerful. Higher-order functions enable encapsulating common programming patterns as functions. Here are few examples:

## Map

*Pattern: Create a new list by applying a function to all elements of an old list.*

```
-- definition
map :: (a -> b) -> [a] -> [b]
map f [] = []
map f (x:xs) = f x : map f xs
-- square of numbers
Prelude> map (^2) [1..10]
[1,4,9,16,25,36,49,64,81,100]
-- length of words in a string list
Prelude> map length ["hello", "bye"]
[5,3]
```

Note that it is defined as *“map takes a function (a -> b) and a list of type a as arguments and produces a list of type b as result”*.

It is worth noting that `map`

is *polymorphic*. Furthermore, it can be applied to itself to process nested lists:

```
Prelude> map (map signum) [[-100, 5, 0], [-9, -9, 0]]
[[-1,1,0],[-1,-1,0]]
```

## Filter

*Pattern: Create a new list by selecting elements of another list that meets a certain predicate.*

```
-- definition
filter :: (a -> Bool) -> [a] -> [a]
filter f [] = []
filter f (x:xs) | f x = x : filter f xs
| otherwise = filter f xs
-- odd numbers only
Prelude> filter odd [1..10]
[1,3,5,7,9]
-- vowels only
Prelude> filter (\x -> elem x "aeiou") ['a'..'z']
"aeiou"
```

## Foldr

*Pattern: process elements of the list using a right-asociative operator*, i.e., for some operator $@$ and list $[a,b,c]$, we have
$$ a @ (b @ c) $$
This is a recursive pattern with the following general structure:

```
f [] = v
f (x:xs) = x @ f xs
which can be encapsulated using foldr as:
foldr (@) v
```

So for an empty list, a value `v`

is returned while for non-empty list, head is combined (using operator) with the result of recursively calling the function on tail. For example, instead of writing the sum function as follows:

```
sum :: Num a => [a] -> a
sum [] = 0
sum (x:xs) = x + sum xs
```

We could use `foldr`

:

```
sum :: Num a => [a] -> a
sum = foldr (+) 0
```

A key observation can be made looking at the pattern that `foldr`

is encapsulating: `f (x:xs) = x @ f xs`

. The operator `@`

has two arguments - first is the head of the list and second is result of recursively applying f to the tail of the list. With this insight, we can write more functions beyond simple math operators. For example, recursive definition of reversing a list is:

```
reverse :: [a] -> [a]
reverse [] = []
reverse (x:xs) = reverse xs ++ [x]
```

Since expression for non-empty list contains 1. head of the list, x and 2. recursively applying reverse to the tail of the list, it meets the `foldr`

pattern. So we can define our operator as (with head as the first argument and tail as the second argument):

```
\x xs -> xs ++ [x]
```

And then write our `reverse`

using `foldr`

as:

```
reverse :: [a] -> [a]
reverse = foldr (\x xs -> xs ++ [x]) []
Prelude> reverse "hello"
"olleh"
Prelude> reverse [1..5]
[5,4,3,2,1]
```

## Foldl

*Pattern: process elements of the list using a left-associative operator*, i.e. for some operator $@$ and list $[a,b,c]$, we have
$$ (a @ b) @ c $$
This is a recursive pattern with the following general structure:

```
f v [] = v
f v (x:xs) = f (v @ x) xs
which can be encapsulated using foldl as:
foldl (@) v
```

Here, `v`

is the *accumulator* value which is returned for an empty list. For non-empty list, head is combined with accumulator using the operator and the function recursively called on this new accumulator and tail. Similar to `foldr`

, addition can now be defined as:

```
add :: Num a => [a] -> a
add = foldl (+) 0
```

Although it looks similar to `foldr`

, it is worth noting that while it is the last element that is processed first in `foldr`

, in `foldl`

head of the list is first element to be processed. When working with `foldl`

pattern, it may be useful to think about how the *operator @, processes the head x and the initial value of the accumulator v*. For example, for reversing a list, head will be consed to empty list in first step. Therefore, our function becomes `\xs x -> x:xs`

and we can write reverse like:

```
reverse' = foldl (\xs x -> x:xs) []
Prelude> reverse' "hello"
"olleh"
Prelude> reverse' [1..5]
[5,4,3,2,1]
```

Note that first argument now is the tail and second is the head.

## (.)

*Pattern: Composition, as in math:* $f.g$

Composition allows to write nested functions more clearly without worrying about initial argument. For example, removing empty list from list of lists can be written as:

```
rmempty :: [[a]] -> [[a]]
rmempty = filter (not . null)
Prelude> rmempty [[1], [],[2]]
[[1],[2]]
```

## Curry and uncurry

*Pattern: Convert a function on pair to curried function and vice-versa*

```
curry' :: ((a, b) -> c) -> a -> b -> c
curry' f x y = f (x,y)
uncurry' :: (a -> b -> c) -> (a,b) -> c
uncurry' f (x,y) = f x y
```

## More examples

### check if all elements satisfy a predicate

```
Prelude> all Data.Char.isLower "hello"
True
```

### check if any element satisfy a predicate

```
Prelude> any Data.Char.isUpper "hello"
False
```

### take elements from a list while they satisfy a predicate

```
Prelude> takeWhile (/= ' ') "hello world"
"hello"
```

### drop elements from a list while they satisfy a predicate

```
Prelude> dropWhile (\x -> sqrt x < 5) [1..30]
[25.0,26.0,27.0,28.0,29.0,30.0]
```