by *Tom Ellis* on **4th November 2012**

`foldr`

made of?This is a common recursion pattern:

```
func1 [] = []
func1 (x:xs) = f x : func1 xs
```

It is so common that there is a version of it parameterised in `f`

. It is called `map`

:

```
map :: (a -> b) -> [a] -> [b]
map f [] = []
map f (x:xs) = f x : map f xs
```

Here is another common recursion pattern:

```
func2 [] = z
func2 (x:xs) = g x (func2 xs)
```

Again there’s a parameterised version, this time in `g`

and `z`

. It is called `foldr`

:

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

Using `foldr`

we can implement `map`

:

```
map' :: (a -> b) -> [a] -> [b]
map' f = foldr ((:) . f) []
```

for then

```
map' f [] == foldr ((:) . f) [] [] == []
map' f (x:xs) == foldr ((:) . f) [] (x:xs) == ((:) . f) x (foldr ((:) . f) xs
== f x : (foldr ((:) . f) xs = f x : map' f xs
```

But using `map`

alone we cannot implement `foldr`

. (This statement is morally true, but I’m not sure of the formal sense in which it is true). Is there something less powerful than `foldr`

that we can combine with `map`

to recover `foldr`

? Surprisingly the answer is “yes”! Define

```
compose :: [a -> a] -> a -> a
compose [] = id
compose (f:fs) = f . compose fs
```

Then write

```
foldr' :: (a -> b -> b) -> b -> [a] -> b
foldr' g z xs = compose (map g xs) z
```

and we have

```
foldr' g z [] == compose [] z == id z == z
foldr' g z (x:xs) == compose (map g (x:xs)) z
== compose (g x : map g xs) z
== (g x . compose (map g xs)) z
== g x (compose (map g xs) z)
== g x (foldr' g z xs)
```

And from `foldr`

we can recover `compose`

:

`compose' fs = foldr (.) id fs`

Then

```
compose' [] == foldr (.) id [] == id
compose' (f:fs) == foldr (.) id (f:fs) == (.) f (foldr (.) id fs)
== f . (foldr (.) id fs) = f . compose' fs
```

`foldr`

made of?`foldr`

is made of `map`

, plus the ability to compose a chain of endomorphisms. For some reason I find this fascinating!