Here we are going to look into how to implement a right fold generically, given only a left fold and no other information about the data structure. The idea is that we fold the structure up, from the left, *into a function*, where the resulting function is designed to evaluate the right-most values first. Here’s what that looks like:

```
foldr : Foldable t => (a -> b -> b) -> b -> t a -> b
= (foldl foo bar t) z where
foldr f z t = _
foo = _ bar
```

This is pretty much a direct translation of the idea above: we left-fold (somehow) the structure `t`

into a function that evaluates from the right, then kick it off with the given starting value. Now we just need to figure out what to use for `foo`

and `bar`

! Let’s start by looking at their types, to see if they give us any clues. We know that `foldl foo bar t`

must be a function, and it should have type `b -> b`

. If we compare that to the type of `foldl`

,

`foldl : Foldable t => (c -> a -> c) -> c -> t a -> c`

in order to have the correct result type, we must have

```
foo : (b -> b) -> a -> (b -> b)
bar : (b -> b)
```

The second one is easy: whenever you need a value that fits that type signature, it almost certainly should be the identity function `id`

. What about `foo`

? Well let’s treat it as a function of two arguments:

```
foo : (b -> b) -> a -> (b -> b)
= _ foo g x
```

At this point, let’s consider what gadgets we have available to us. We haven’t yet used `f : a -> b -> b`

, and now we also have `g : b -> b`

and `x : a`

. In general, unless you have a good reason, you want to try to use all of the variables you have handy. Interestingly, `f x`

will have type `b -> b`

, so what if we just compose that with `g`

?

```
foldr : Foldable t => (a -> b -> b) -> b -> t a -> b
= (foldl foo id t) z where
foldr f z t = g . f x foo g x
```

If you try this out, you’ll find that this definition works exactly as we wanted it to! This is actually somewhat amazing, which is a pretty common occurrence with “type-driven development” as this method is usually called. We could have arrived at the same result if we sat down and worked out exactly what it means to “left-fold a structure into a function that executes a right-fold”, but that would have required a lot more noodling.

To be honest, though, we cheated a little bit. Doing the composition in `foo`

the other way around would have typechecked, but produces the wrong results:

```
notFoldr : Foldable t => (a -> b -> b) -> b -> t a -> b
= (foldl foo id t) z where
notFoldr f z t = f x . g foo g x
```

If you work out an example, this turns out to look like a right fold…but for a reversed input! This is the price of type-driven development: sometimes there is more than one choice to fill in a value for a given type, and the only way to determine which choice is correct is by testing it out yourself. Static type checking is not a substitute for *all* tests!