> import Data.Monoid
In his recent blog post What is foldr made of?, Tom Ellis made the clever observation that foldr
is equivalent in power to the combination of map
and compose
, where
> compose :: [a > a] > a > a
> compose [] = id
> compose (f:fs) = f . compose fs
We can then write
> foldr' :: (a > b > b) > b > [a] > b
> foldr' g z xs = compose (map g xs) z
which (as Tom proves) is exactly equivalent to the usual foldr
.
This is a really neat idea which I don’t remember ever seeing before. But now that I have, I realized that I could expand on it a bit—compose
doesn’t come out of thin air quite as much as it might first appear.
Consider the standard function mconcat
(from Data.Monoid
), which combines a list of values from some Monoid
:
mconcat :: Monoid m => [m] > m
mconcat [] = mempty
mconcat (m:ms) = m `mappend` mconcat ms
I claim that in the presence of map
, compose
and mconcat
are equivalent. Why is that? First, it’s easy to see that compose
can be implemented in terms of mconcat
—we just instantiate it to the monoid of endofunctions (where mempty = id
and mappend = (.)
), with a little bit of syntactic noise due to the need to convert in and out of the Endo
newtype:
> compose' :: [a > a] > a > a
> compose' = appEndo . mconcat . map Endo
Proving that compose'
is the same as compose
is not hard; I leave it to you as an exercise.
Implementing mconcat
in terms of compose
is a bit more interesting:
> mconcat' :: Monoid m => [m] > m
> mconcat' = ($mempty) . compose . map mappend
The key idea is that we can turn any value from some monoidal type m
into a function m > m
by partially applying mappend
; composing these functions then corresponds to combining the original values, and the final value can be recovered by applying the resulting function to mempty
.^{1} That is,
(where I have used and to represent mappend
and mempty
, respectively). Written out this way, I hope you can see why the equality holds by thinking about what the composition on the right evaluates to (and remembering the right identity law, ).
So we can also say that foldr
= map
+ mconcat
! This gets at the idea that lists are free (or initial) monoids, which intuitively means that of all monoids, they “preserve the most information”—up to the monoid laws, combining lists preserves all the information about the original lists and how you have combined them. This also means that there is a canonical way to “convert” a list into any other Monoid
: that is, given a mapping f :: a > m
, there is a canonical way to take a list [a]
and turn it into an m
, namely, mconcat . map f
.
Let’s make the connection to foldr
even more explicit. First, let’s swap around the order of arguments and add some parentheses which aren’t strictly necessary:
foldr'' :: (a > (b > b)) > [a] > (b > b)
Hmm, b > b
… why does this look so familiar? I claim we can actually pull a similar trick^{2} as with compose
/mconcat
, and replace b > b
with Monoid m => m
to come up with a function equivalent to foldr''
(and hence foldr
as well):
fold :: Monoid m => (a > m) > [a] > m
Hmm, so how would this be implemented? Let’s see…
> fold :: Monoid m => (a > m) > [a] > m
> fold f = mconcat . map f
So actually, fold
itself (and hence, equivalently, foldr
) is the canonical mapping from a list down to any monoid which I mentioned earlier! And here we can see quite directly that fold
is indeed equivalent to mconcat
+ map
.
In summary: foldr
is equivalent to map
plus compose
/mappend
, because lists are free monoids.

Incidentally, this amounts to saying that
mappend
itself is a monoid homomorphism (a structurepreserving map between monoids), and this is where difference lists come from. For more, see my recent paper, Monoids: Theme and Variations.↩ 
I leave this as an exercise too.↩