# Jaguarpaw Blog - What is foldr made of?

by Tom Ellis on 4th November 2012

# What is `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``````

## So what is `foldr` made of?

`foldr` is made of `map`, plus the ability to compose a chain of endomorphisms. For some reason I find this fascinating!