concatMap

Next we have

concatMap :: Foldable t => (a -> [b]) -> t a -> [b]

It takes a function f that turns an a into a list of bs, f :: a -> [b], and applies it to every element in the container. This gives us a container of lists of bs, which we can concatenate in the same way as concat would do it. Once again, this is simply the specialization of foldMap where the monoid m is the list monoid:

concatMap :: Foldable t => (a -> [b]) -> t a -> [b]
concatMap = foldMap

This may look familiar. Our earlier shenanigans to flatten a container into a list used the definition

toList = foldMap singleton

We could also define it as

toList = concatMap singleton

We convert each list element to a singleton list containing this element—that's the "map" part—and then we concatenate the resulting lists.

GHCi

>>> concatMap singleton tree
[5,3,1,2]

A comment is in order. I illustrated the use of concat in the previous section by evaluating the expression concat $ fmap singleton tree. First, we map singleton over the elements in the tree, turning each element into a singleton list, and then we concatenate the resulting lists. concatMap does the same. More importantly, when discussing concatMap as one of the functions available for lists, I explained that at least logically if not in terms of actual implementation, concatMap is simply the composition of concat and map:

concatMap f = concat . map f

This works for lists. It also works for trees, only we have to use fmap because map works only for lists:

concatMap f = concat . fmap f

This raises the question whether this definition works for any foldable container. The answer is no, and the reason is a subtle one.

The definition works, as long as our container is a functor. We could have defined

concatMap :: (Functor t, Foldable t) => (a -> [b]) -> t a -> [b]
concatMap f = concat . fmap f

However, this definition would not work for any foldable container because if you have a closer look at the Foldable class, it does not define Foldable as a subclass of Functor. Thus, we cannot rely on fmap being available for every foldable container.

I haven't come up with a natural example of a container type that is foldable but not a functor. So I'm not entirely sure why Foldable is not a subclass of Functor. In contrast, we discussed the Reader functor as an example of a container that is a functor but is not foldable.