Why function composition sometimes requires two "." 's to combine two functions

Question

So this question is simple but I can't seem to grasp the concept.

To compose ordinary functions, one can just do something like below:

lowerNoSpaces = filter (/= ' ') . map toLower

But, on occasion, there are times where this won't work:

myConcatMap = concat . map

It gives the error:

<interactive>:236:1: error:
    * Non type-variable argument
        in the constraint: Foldable ((->) [a1])
      (Use FlexibleContexts to permit this)
    * When checking the inferred type
        concattMap :: forall a1 a2.
                      Foldable ((->) [a1]) =>
                      (a1 -> a2) -> [a2]

But when the same function is expressed like this:

myConcatMap = (concat .) . map

It works exactly as intended.

I know there is a reason for this, but I have been staring at it for a while and still don't quite understand why the original doesn't work and this one does.

Why is there two "." 's?

Answer 1

This is fairly easy to derive from the definition of (.) and knowledge of Haskell syntax.

You start with a more explicit definition of myConcatMap, which is

\f -> \xs -> concat (map f xs)

By definition of the composition operator, you can write this as

\f -> concat . (map f)

Rewrite this using . in prefix position rather than as an infix operator.

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

and add some redundant parentheses since function application is left-associative.

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

Rewrite this using section syntax to make . an infix operator again

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

and apply the definition of (.) one more time, using the functions (concat .) and map:

(concat .) . map

Answer 2

It's because map is a two-argument function, and you want to apply concat only after both arguments have been supplied. Keep in mind that Haskell multi-argument functions are curried, i.e. it's actually

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

Thus, if you write a composition c . map, the argument of c must be something of type [a]->[b]. But the argument of concat is supposed to be a list, i.e. something of type [b] or actually [[e]].

Solutions:

• Pass the first argument explicitly.

  myConcatMap f = concat . map f
  

  This works because map f is only a one-argument function anymore [a] -> [b], thus you can compose concat in front of it.

• Compose concat in front of the function that's the result of applying map to its first argument. That's what you're doing in your example.