# Reversing A List With Folds

### Reversing a List with Folds

It’s possible to easily implement a `reverse`

function using folds. Try to
implement a function that will reverse a list using both `foldl`

and
`foldr`

. Which one is simpler? why? Might one be more efficient than the other?

### Hints

## Click to reveal

Reversing a list is really just creating a new list one element at a time so that by the time you’re done adding elements, the final list is in the reverse order. For both of your folds, the initial accumulator value should be an empty list.

## Click to reveal

Regardless of the fold you are using, the general shape of the solution will look something like this:

`= fold insertElem [] reverseFold `

The definition of `insertElem`

will different depending on the
fold you are using.

*Remember*: For a left fold, you’ll add new elements to the list from first to
last. For a right fold, you’ll be adding elements from last to first.

## Click to reveal

Imagine that you want to reverse the list `[1,2,3]`

. You could rewrite
thestarting list more explicitly as:

`1 : 2 : 3 : []`

The reversed version of that list is `[3,2,1]`

or, more explicitly:

`3 : 2 : 1 : []`

For a *left fold* the first call to `insertElem`

will pass in the
starting accumulator and the first value of the list:

`1 [] insertElem `

The second call will pass in the next value, and the previous accumulator, and
so on. For our list `[1,2,3]`

the calls will end up looking like this:

```
3 $
insertElem 2 $
insertElem 1 [] insertElem
```

Try to compare that to the shape of our reversed list and see if you can spot a function you already know that would do that. You might need to consider reversing the order of arguments of that function.

### Solution

## Click to reveal

Reversing a list using a `foldl`

can be done by prepending each new element to
the front of the new list. Since `foldl`

is left-associative, we’ll start with
the first element of our old list. Adding each new element to the beginning of
the reversed list means we’ll finish by adding the final element of the original
list to the beginning of the new list. Following the pattern from the earlier
hint, we could a solution like this:

```
= foldl insertElem []
reverseLeft where insertElem reversed a = a : reversed
```

Alternatively, we can use the `flip`

function to make this a bit more
compact. Remember that `flip`

just flips the arguments of a function:

`flip f b a = f a b`

Our `foldl`

version of `insertElem`

is just a flipped version of `(:)`

, so we
can rewrite our reverse function as:

`= foldl (flip (:)) [] reverseLeft `

We can also reverse a list using `foldr`

but this will be less efficient. Since
`foldr`

is right associative, we start adding elements from the end of the input
list. That means each new element we process needs to be added to the end of our
accumulated list:

```
= foldr insertElem []
reverseRight where
= reversed <> [a] insertElem a reversed
```

This is less efficient because we have to walk through the entire reversed list for every item we add, so that we can insert new items at the end.