# Higher order functions

## List-based recursion

Consider the `length`

function that finds the length of a list. Below is a recursive definition.

The type signature tells us that `length`

is a function that accepts a list of an arbitrary type `a`

, and returns an `Int`

. The `(x:xs)`

term binds `x`

to the head of the list and `xs`

to the tail.

This works by pattern matching on the type constructor `(:)`

. If we had recursively defined our list as

then the same length function would be written as follows.

## Abstracting to map

Suppose we’re writing a function that doubles every element in a list of `Int`

s. We might write the following.

We can easily generalize this, for example to a function that multiplies every element in a list of `Int`

s by \(m\).

```
multiplyList :: Int -> [Int] -> [Int]
multiplyList _ [] = []
multiplyList m (x:xs) = (m * x) : multiplyList m xs
```

Here, the naive reading of the type signature is as a function from an `Int`

and a `[Int]`

to a `[Int]`

. However, since the `->`

operator is right associative, we can read the type signature as

meaning `multiplyList`

takes an `Int`

and returns a function from `[Int]`

to `[Int]`

. In particular, note that we can recover `doubleList`

by passing one argument to `multiplyList`

. The following code gives us a function equivalent to the original.

Functions in Haskell are “first-class citizens,” and behave exactly like any other value. As we’ve seen, functions can return other functions. Similarly, functions can accept other functions as arguments. To generalize `multiplyList`

further, we can write

```
applyToInts :: (Int -> Int) -> [Int] -> [Int]
applyToInts _ [] = []
applyToInts f (x:xs) = (f x) : applyToInts f xs
```

`applyToInts`

accepts a function from integers to integers, with type signature `Int -> Int`

, and returns a function that applies that function to each element in a list.

We can further generalize `applyToIntegers`

. While its type signature is `(Int -> Int) -> [Int] -> [Int]`

, the definition is not integer specific. We can make a polymorphic version with the type signature `(a -> b) -> [a] -> [b]`

. This function is called `map`

, which you might be familiar with.

## The filter function

Besides `map`

, Haskell contains numerous other higher-order functions for list operations. As in other languages, `filter`

is a function that takes a predicate and a list, and returns the list of elements that satisfy the predicate.

```
filter :: (a -> Bool) -> [a] -> [a],
filter _ [] = []
filter pred (x:xs)
| pred x = x : filter pred xs
| otherwise = filter pred xs
```

Looking at the type signature, we can see that the predicate, which is the first argument, has type `(a -> Bool)`

where `a`

is the type of the list elements.

Here are some examples.

As with `map`

, we can define more specific functions using filter. For example, the following function `justEvens`

takes a list of type `[Int]`

and returns a list of its even elements.