# Higher-Order Functions on Lists II: Folds

In this lesson, we look at list folds, higher-order functions that reduce lists.

In addition to `map`

and `filter`

from the last lesson, there is a third ubiquitous higher-order function on lists: the **fold** (or **reduce**) operation that reduces a list to a single value.

## List folds

Let’s first look at a few examples of this reduction pattern. The first one is a function which reduces a list of integers to their sum. It is defined in the Haskell Prelude as `sum`

.

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

The `sum`

function operates by providing an initial sum of `0`

for the empty list, and then successively adding list elements.

The second example is the `concat`

function (also from the Prelude) which operates on a list of lists and returns a single flattened list with all the elements of the list of lists.

```
concat :: [[a]] -> [a]
concat [] = []
concat (xs:xss) = xs ++ concat xss
```

Again this function accumulates the result by starting with the empty list and successively appending the elements of each list in the input.

The general recursion pattern captured by these functions is:

- The input is a list with elements of type
`a`

and the output is a value of type`b`

. - There is a base value
`z`

(e.g.`0`

,`[]`

) which is the result on the empty list. - The final result is computed by going over the input list element by element and modifying an
**accumulator**. Starting with the base value`z`

as the accumulator, a folding function`f`

(e.g.`+`

,`++`

) is used to combine the accumulator with successive list elements.

This pattern is captured by the `foldr`

function from the Prelude. Here is its implementation on lists:

```
foldr :: (a -> b -> b) -> b -> [a] -> b
foldr _ z [] = z
foldr f z (x:xs) = f x (foldr f z xs)
```

In many cases, the output type `b`

is the same as the list element type `a`

, and we can see `foldr`

as a **reduction** of the list to a single value. This is also where the name `fold`

originates: the idea is to successively fold together the linear list to a single value, like folding a piece of paper.

The function `sum`

and `concat`

from above can be written succinctly as:

Get hands-on with 1200+ tech skills courses.