Haskell: functional composition just damaged my brain

Question

If a

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

and

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

then how does it work

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

Given:

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

?

I mean, my understanding of a compound function is that replicate must return all concatMap as arguments in order for (.) work. But this is not so. So what is the catch?

Answer 1

This can help you find out what happens if you add parentheses to the signatures, and then align them:

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

Now it should be pretty obvious that the replicate output is suitable for concatMap input if we combine b and a , in which case the output composition type is [b] -> [b] .

Answer 2

The difficulty is probably related to the confusing type variables and you are talking about type unification. The trick is to consider, as others have said that (->) is right-associative, i.e. you can (which makes 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 limitations that we need to solve. Let's say that "a ~ b" means "a is the same type as b" or equivalent to "a can be replaced with b".

From the foregoing, we can conclude about the following facts:

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

But two equivalences for b tell us that

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

what entails

 q ~ s and [r] ~ [s] 

So, rewrite c as:

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

Connecting the permutations for a and c back to the original type (.) With two yield functions attached

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

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