What does concatMap do?

Checking the documentation reveals:

concatMap :: (a -> [b]) -> [a] -> [b]

Map a function over a list and concatenate the results

And that its definition is thus:

-- | Map a function over a list and concatenate the results.
concatMap               :: (a -> [b]) -> [a] -> [b]
concatMap f             =  foldr ((++) . f) []

Compare the following output from ghci:

*Main> concatMap (++"! ") ["one", "two", "three"]
"one! two! three! "
*Main> concat $ map (++"! ") ["one", "two", "three"]
"one! two! three! "

Conceptually, yes, but the actual implementation is different:

concatMap :: (a -> [b]) -> [a] -> [b]
concatMap f =  foldr ((++) . f) []

Yes, the concatMap function is just concat and map put together. Hence the name. Putting functions together simply means composing them:

(.) :: (b -> c) -> (a -> b) -> a -> c

However concat and map cannot be put together by simply using function composition because of the type signature of map:

map :: (a -> b) -> [a] -> [b]
       --------    ---    ---
          a         b      c

As you can see function composition expects a function of type a -> b, but map is of type a -> b -> c. To compose concat with map you need to use the .: operator instead:

(.:) :: (c -> d) -> (a -> b -> c) -> a -> b -> d

The concat function has a type signature of:

concat :: [[a]] -> [a]
          -----    ---
            c       d

Hence concat .: map is of type:

concat .: map :: (a -> [b]) -> [a] -> [b]
                 ----------    ---    ---
                     a          b      d

Which is the same as that of concatMap:

concatMap :: (a -> [b]) -> [a] -> [b]

The .: operator itself can be written in terms of function composition:

(.:) = (.) (.) (.)

-- or

(.:) = (.) . (.)

Hence concatMap can be written as:

concatMap = (.) (.) (.) concat map

-- or

concatMap = (concat .) . map

-- or

concatMap = concat .: map

If you flip the arguments of concatMap you get the >>= (bind) function of the list monad:

instance Monad [] where
    return x = [x]
    (>>=) = flip concatMap
    fail _ = []

flip concatMap :: [a] -> (a -> [b]) -> [b]

>>= :: Monad m => m a -> (a -> m b) -> m b

This makes it the same as the =<< function of the list monad:

concatMap :: (a -> [b]) -> [a] -> [b]

=<< :: Monad m => (a -> m b) -> m a -> m b

So now you know everything that there is to know about concatMap. It's just concat applied to the result of a map. Hence the name.

Tags:

Haskell