> 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.↩
I am really confused. Does this mean that the difference list optimization can be done to other data structures too?
I know the following data structure is a monoid, and has a function similar to mconcat (because it is a tree) does the same idea work with it as well?
data Tree a = LNil  RNil  Fork a (Tree a) (Tree a)
It’s fold can be massaged to have the type (a > (b, b) > b) > Tree a > (b, b) > b. The type (b, b) > b is a monoid.
I still can’t get what the type for the optimized version of tree would be.
* I meant to say that (b, b) > b is the monoid not the Tree structure.
I don’t understand what you mean. In what sense is
(b,b) > b
a monoid? How would you implementmappend :: ((b,b) > b) > ((b,b) > b) > ((b,b) > b)
?No, the difference list optimization can be done to any monoid. So you can do it with data structures that have a monoid instance, but your
Tree
is not such a data type (at least not in any obvious way that I can see). You say “the following data structure is a monoid” — what exactly wouldmappend
do (say, when given twoFork
s)?For a generalization of difference lists, see the “Asymptotic Improvement of Computations over Free Monads” paper.
That signature is the same as Data.Foldable.foldMap. Is that the same function?
Yes, it is the same function, specialized to lists. But note that lists really are special: in some sense you can think of
Foldable
as the class of types which have a canonical implementation oftoList
. The generic version offoldMap
is equivalent (but often more efficient than) callingtoList
followed byfold
on the list. From another point of view, note that lists are the only type for which the catamorphism andData.Foldable.foldMap
coincide. For all other types,foldMap
is actually a weaker operation than the catamorphism, because it forces you to “forget all the nonlist structure”.I’m somewhat surprised that noone mentioned Foldable yet…. http://www.haskell.org/ghc/docs/latest/html/libraries/base/DataFoldable.html – or even http://learnyouahaskell.com/functorsapplicativefunctorsandmonoids (search for foldable … ) :D
The compose/mconcat equivalence looks like Cayley’s theorem.
http://en.wikipedia.org/wiki/Cayley%27s_theorem
Nice observation! Yes, I think it is exactly analogous to Cayley’s theorem, specialized to monoids instead of groups. I suspect there is also a relationship to the Yoneda lemma but I am not sure how to make it precise.
I think you meant “(where mempty = id and mappend = (.))” =).
Good catch, thanks! Fixed now.
This reminds me of Exerise 2.11 from Burstall’s Computational Category Theory: “Notice that the definition of list processing functions like length, member, sum and maplist all have the same general form. This may be explained by the fact that lists form a free monoid. The monoid structure is that of concatenating lists with the empty list as the identity. There is a function h : A → list(A) which returns the singleton list on an element. The freeness is expressed by the unique existence of a homomorphism as follows: For any monoid (B, ∗, e) and function f : A → B, there is a unique homomorphism f# from the monoid of lists to (B, ∗, e) such that the following commutes: f# ∘ h = f. Given the monoid (B, ∗, e), the map f → f # can be constructed and the construction can be expressed as a program in ML. Representing the target monoid as a pair of a binary function and a constant, write this program. It is an example of an encapsulation of recursion, in that functions (like those mentioned above) normally defined through explicit recursion, can be obtained by passing suitable parameters to this program.”
E.g. one can define length as:
type Monoid b = (b > b > b, b)
the_map :: Monoid b > (a > b) > ([a] > b)
the_map ((*), e) = \f > foldr (*) e . map f
sum_monoid :: Monoid Int
sum_monoid = ((+), 0)
f_length = const 1
length = the_map sum_monoid f_length
Pingback: Okay, this is cool.
Very nice blog post. I have two reflections:
The function fold very neatly captures the essence of the MapReduce framework. The function argument is the function being mapped and the use of mappend corresponds to reduce.
The generalization to the scan function is a nice way to think about parallel prefix computations.
scan :: (a > m) > [a] > [m]