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!

See also