foldMap
Here's the type of the foldMap function:
foldMap :: Monoid m => (a -> m) -> t a -> m
foldMap f xs applies f to every element in the container to obtain a value
of type m. m is required to be a monoid, so we can use all of these values
of type m and combine them into a single value of type m using the monoid
multiplication (<>).
Let's play with this a little. We have the
Sum and Product monoids. Remember that data constructors are
really just functions. So we have Sum :: a -> Sum a and
Product :: a -> Product a. We also have the accessors getSum and
getProduct to extract the value of type a from a Sum a or Product a.
With these monoids, we can add or multiply the values in a list:
>>> import Data.Monoid
>>> getSum $ foldMap Sum [1..10]
55
>>> getProduct $ foldMap Product [1..10]
3628800
We can do the same for trees:
>>> tree = Node Empty 5 (Node (Node Empty 3 Empty) 1 (Node Empty 2 Empty))
>>> getSum $ foldMap Sum tree
11
>>> getProduct $ foldMap Product tree
30
Of course, this isn't as elegant as just using foldl and (+) or (*),
but there are more interesting (but also more complicated) monoids where
foldMap is the only way to go. I use Sum and Product here only to
illustrate that foldMap does the right thing. In the first example, we do
get the sum of all list elements. In the second example, we get their
product. In both cases, the monoid multiplication of the monoid is used,
which is addition for Sum and multiplication for Product.
A more useful application of foldMap is to collect a list of all elements in a
container. If we import the Data.List module, then we gain access to the
function
singleton :: a -> [a]
singleton x = [x]
It builds a list containing its argument as the only element:
>>> import Data.List
>>> singleton 1
[1]
By applying this function to every element in a container, we obtain a container whose elements are all singleton lists. Concatenating these lists gives the list of all elements in the container. It so happens that the multiplication operation of the list monoid is list concatenation:
>>> [1,2] <> [3,4,5]
[1,2,3,4,5]
Thus, to collect all the elements of a container in a list, we can use
foldMap singleton.
For a list, we get the original list back:
>>> foldMap singleton [1,2,3,4,5]
[1,2,3,4,5]
For Maybe, we get the empty list if the value we're converting to a list is
Nothing. That's correct because Nothing does not store any elements.
Just x stores x as its only element, so foldMap singleton (Just x) should
produce the list containing only x:
>>> foldMap singleton Nothing
[]
>>> foldMap singleton (Just 5)
[5]
Finally, given that a tree is a foldable container, we can also collect its elements in a list:
>>> tree = Node Empty 5 (Node (Node Empty 3 Empty) 1 (Node Empty 2 Empty))
>>> foldMap singleton tree
[5,3,1,2]
The default implementation of foldMap is
foldMap f xs = foldr ((<>) . f) mempty xs
Ugh. Maybe this needs some explanation. Remember, we want to produce a value
of type m. If we want to do so using foldr, we need an initial
accumulator value of type m, and mempty is the natural
choice.1 Indeed, our implementations of sum and product
using foldl for lists above used the unit for addition and multiplication
as the initial accumulator value. The elements in xs are of type a. So
the accumulator function we provide to foldr needs to be of type
a -> m -> m. The function f has type a -> m. It maps each element of
xs into a monoid value of type m. The monoid multiplication (<>) has
type m -> m -> m. The composition (<>) . f thus has type a -> m -> m.
It has the right type, and it does the right thing: It uses f to map the
current list element to a monoid value and then uses monoid multiplication
to combine this monoid value with the current accumulator value, to produce
the new accumulator value.
Since any instance of Foldable needs to implement only one of foldl and
foldMap, we need default implementations of these three functions (including
foldr) in terms of each other. We've just given the default implementation of
foldMap in terms of foldr. This leaves implementing foldl and foldr in
terms of foldMap.
These implementations are a mouthful, and reproducing them here would lead us
too far astray. If we assume we have custom implementations of foldl and
foldr for lists, as the ones discussed before, we can use them
to obtain simple implementations of foldl and foldr for arbitrary foldable
containers that first use foldMap to collect the elements of the container in
a list and then fold up the list using the list versions of foldl and foldr:
foldl f init xs = foldl f init $ foldMap singleton xs
foldr f init xs = foldr f init $ foldMap singleton xs
Haha, we're using foldMap singleton to "flatten" a container into a list
again, as we did for Maybe and trees above. foldl f init and
foldr f init then fold up this list from left to right or from right to
left, as required.
-
In fact, given that all that
foldMapknows is thatmis a monoid,memptyis the only value it knows how to generate. Somemptyis in fact the only choice for the initial accumulator value in this implementation offoldMapviafoldr. ↩