# Recursive Functions on Lists

More techniques for writing recursive functions on lists.

## We'll cover the following

After understanding polymorphic types, we will now put our newfound knowledge to use and write some more polymorphic list functions. We will cover the most important techniques used to write recursive functions on lists.

## (Re-)Constructing lists

So far all of the list functions we have written (e.g. `length`

, `containsMatching`

) returned a single value, like an integer or a boolean. Such functions that reduce a list to a single value are called **“folds”** in functional programming.

However, many functions that work on lists will return lists themselves after transforming, filtering, or combining the input lists. Some examples are the `take`

, `drop`

, or the `++`

and `concat`

functions. We will now see how to write such functions that (re-)construct lists themselves.

As an example, let’s reimplement the `++`

operator that appends two lists as a polymorphic function called `append`

.

```
append :: [a] -> [a] -> [a]
```

The base case of `append`

is when the first input list is the empty list. In that case, we can simply return the second input list.

```
append [] ys = ys
```

The interesting case is when the first list is a nonempty list `x : xs`

. What do we want the result of `append`

to look like? Certainly, the head of the result should be `x`

. The tail of the result should contain the elements of `xs`

followed by the elements of `ys`

. In other words, the tail of the result should be `xs`

appended to `ys`

.

```
append (x:xs) ys = x:(append xs ys)
```

We used the `:`

constructor on the right side here to implement the reasoning discussed above. The equation says that the head of the result is `x`

, and the tail of the result is `xs`

appended to `ys`

.

Get hands-on with 1200+ tech skills courses.