Composition of compositions in Haskell

4
votes

I am learning Haskell recently, and I was reading Functors in Learn You a Haskell from which I came to know

  1. Functions ((->)r) which take one parameter, are also in a way Functors.
  2. Composition (.) is equivalent to fmap

So with what I have understood, fmap takes two parameters. First is the function to be applied, and the second one is the functor.

However, I am confused with this expression (.) (.) (.). This is a composition of two composition, with the type (b -> c) -> (a1 -> a2 -> b) -> (a1 -> a2 -> c)

So here is my doubt arising. The first (.) has two parameters, first one being composition function itself. The second parameter also being the composition function. And composition function as such is not a functor. So how is this a valid expression?

I am sure that I am missing something here. Could someone fill in the gaps and help me get how the expression is correct?

1
haskellfunctional-programmingfunctor
There's some confusion here. A function is a value, while a functor is a type-level object which maps types to types. The application (.)(.)(.) can be understood without thinking about functors. – chi

1 Answers

7
votes

Ignore the Functor instance for ((->) r); it is irrelevant. Only two tings matter here: The type of (.), namely

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

, and the fact that function application is left associative. The latter means that (.) (.) (.) is the same as ((.) (.)) (.).

Let us first try to find the type of (.) (.) (the leftmost ones, if you will). Let us write the type of the first (.) as (b1 -> c1) -> (a1 -> b1) -> a1 -> c1 and the second as (b2 -> c2) -> (a2 -> b2) -> a2 -> c2. We apply the first to the second, which gives us that b1 is (b2 -> c2) and c1 is (a2 -> b2) -> a2 -> c2. Thus we have

(.) (.) :: (a1 -> (b2 -> c2)) -> a1 -> ((a2 -> b2) -> a2 -> c2)

which can be simplified to

(.) (.) :: (a1 -> b2 -> c2) -> a1 -> (a2 -> b2) -> a2 -> c2

Let's now apply this to to the last (.) (the rightmost one, if you will). If it has signature (b3 -> c3) -> (a3 -> b3) -> a3 -> c3, then we see that a1 must be (b3 -> c3), b2 must be (a3 -> b3) and c2 must be a3 -> c3. Thus,

((.) (.)) (.) :: (b3 -> c3) -> (a2 -> (a3 -> b3)) -> a2 -> a3 -> c3

which is the same as

((.) (.)) (.) :: (b3 -> c3) -> (a2 -> a3 -> b3) -> (a2 -> a3 -> c3)

This is the same as what you have in your question if you do some renaming.