Haskell: function composition has just damaged my brain

Question

If

*Main> :t concatMap
concatMap :: (a -> [b]) -> [a] -> [b]

and

*Main> :t replicate
replicate :: Int -> a -> [a]

then how does that work

*Main> :t concatMap . replicate
concatMap . replicate :: Int -> [b] -> [b]

given:

*Main> :t (.)
(.) :: (b -> c) -> (a -> b) -> a -> c

?

I mean, my understanding of function composition is that replicate should return whatever concatMap expects as arguments in order for (.) to work. But it does not LOOK to be the case. So what is the catch?

Answer 1

It might help you to see what's going on if you add parentheses to the signatures and then line them up:

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

Now it should be fairly obvious that the output of replicate fits the input of concatMap if we unify b and a, in which case the output type of the composition is [b] -> [b].

Answer 2

The difficulty probably comes from confusing type variables and how you reason about type unification. The trick is to consider, as others have said, that (->) is right-associative, meaning you can line things up like this (making new type variables for each signature to avoid confusion):

(.)       :: (b         ->  c         ) -> (a    -> b        )  -> a -> c
concatMap :: (q -> [r]) -> ([q] -> [r])
replicate ::                               (Int  -> (s -> [s])

This essentially gives us some constraints we need to resolve. Let's say that "a ~ b" means "a is the same type as b" or equivalently "a can be substituted with b."

From just the above, we can infer the following facts:

a ~ Int
b ~ (q -> [r]) ~ (s -> [s])
c ~ ([q] -> [r])

But the two equivalences for b tell us that

(q -> [r]) ~ (s -> [s])

which entails that

q ~ s and [r] ~ [s]

So then we rewrite c as:

c ~ ([q] -> [r]) ==> ([s] -> [s]))

Plugging the substitutions for a and c back into the original type of (.) with the two functions applied yields

a -> c ~ Int -> ([s] -> [s]) 

which of course is now in the form that ghci reports: Int -> [b] -> [b].