Composing concat and map to get concatMap: why the f?

Question

Those are my first explorations in Haskell, so pardon me if it should be obvious.

I have been playing all afternoon with Haskell, sifting through the tutorial 99 questions on HaskellWiki, using my own list type (typical Cons). I've added "obvious" functions as I went on, and I have tried to make them as concise as possible (employing point-free notation whenever possible)

The 12th problem is about decoding a run-length encoded list, that is:

> decode [Multiple 5 'a', Single 'b', Multiple 2 'c']
"aaaaabcc"

And I thought about using map to decode each element, then concat the result (thanks Google on this), and finally remembered that I had seen something like concatMap in my readings, which GHCi quickly confirmed:

> :t map
map :: (a -> b) -> [a] -> [b]
> :t concat
concat :: [[a]] -> [a]
> :t concatMap
concatMap :: (a -> [b]) -> [a] -> [b]

It looked like it would be obvious to reimplement concatMap:

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

Except that GHCi quite complains:

List.hs:110:15:
    Couldn't match expected type `[a] -> [b]'
                with actual type `[a0]'
    Expected type: [[a0]] -> [a] -> [b]
      Actual type: [[a0]] -> [[a0]]
    In the first argument of `(.)', namely `concat'
    In the expression: concat . map

I could not figure it out, so I looked up on the web, and the definition referenced in Prelude is actually:

concatMap f = concat . map f

And I don't quite understand why this f is necessary, since it's type is obviously a -> [b] as specified by the signature...

So why is f necessary here ?

Answer 1

Starting with the standard definition,

concat . map f 
 ≡ concat . (map f)
 ≡ \x -> concat ((map f) x)

Your first definition gives you:

(concat . map) f
 ≡ (\x -> concat (map x)) f
 ≡ concat (map f)

which doesn't type check because (map f) :: [a] -> [b], while concat takes [[a]], a list of lists.

Note the particular error message shown in the question doesn't describe the above type-check failure. The given message arises from declaring the return type concatMap as [a] -> [b], which isn't reconcilable with [a0], the return type of concat. If you leave off the type signature, the response is:

    Couldn't match type ‘[a1] -> [b]’ with ‘[[a]]’
    Expected type: (a1 -> b) -> [[a]]
      Actual type: (a1 -> b) -> [a1] -> [b]
    Relevant bindings include
      concatMap :: (a1 -> b) -> [a] (bound at :49:5)
    Probable cause: ‘map’ is applied to too few arguments
    In the second argument of ‘(.)’, namely ‘map’
    In the expression: concat . map

Here, the type error occurs when reconciling the return type of map with the argument type of concat. It turns out this case is more useful for debugging as it contains a hint why the type check failed.