The function (.).(.) in haskell

Question

I am trying to find the type of (.).(.) in Haskell, manually.

My attempt was the following:

(.).(.) = \x -> (.).(.) x

(.)     :: (     b   ->             c         )  ->  ((     a    ->           b        ) -> (a -> c))
(.)     :: (d -> e)  ->  ((f -> d) -> (g -> e))
(.)     ::                                              (h -> i) -> (j -> h) -> (h -> k)

-----------------------------------------------------------------------------------------------------
b ~ (d -> e) ~ (j -> h) -> (h -> k)
c ~ ((f -> d) -> (g -> e))
a ~ (h -> i)
d ~ h
e ~ i                 

so (a->c)~     (h->i) -> ((f -> h) -> (g -> i))

What is wrong in my way of thinking? The actual type is

(.).(.) :: (b -> c) -> (a1 -> a2 -> b) -> a1 -> a2 -> c

Answer 1

Let's look at the equivalent (.) (.) (.)

The first dot type: (b -> c) -> (a -> b) -> a -> c

Second: (e -> f) -> (d -> e) -> d -> f

Hence:

b is the same as e -> f

c is the same as (d -> e) -> d -> f

Third: (h -> i) -> (g -> h) -> g -> i

Hence:

a is the same as h -> i

b is the same as (g -> h) -> g -> i

e -> f is (g -> h) -> g -> i

e is g -> h

f is g -> i

Since (.) (.) (.) :: a -> c from the first dot type, we have:

a -> c is (h -> i) -> (d -> e) -> d -> f

substituting e and f: (h -> i) -> (d -> g -> h) -> d -> g -> I

Answering your question, I think that what is wrong with your thinking are last two lines e.g.:

d ~ h, e ~ i

Answer 2

Your derivation should have been :

(.).(.) = (.) (.) (.)

(.) :: (   b      ->           c          )  ->  (   a      ->           b          ) -> (a -> c) 
(.) ::  (d -> e)  ->  (f -> d) -> (g -> e)   -- WRONG
(.) ::                                            (h -> i)  ->  (j -> h) -> (h -> k)  -- WRONG
(.) ::  (d -> e)  ->  (f -> d) -> (f -> e)   -- correct
(.) ::                                            (h -> i)  ->  (j -> h) -> (j -> i)  -- correct

Thus the overall type is

(.) (.) (.) ::   a    ->                c                   ,   b ~ b
            ~  (h->i) ->  (f ->   d   ) -> (f ->   e   )    ,   (j -> h) -> (j -> i) ~ 
                                                               (   d     ->    e    )
             --------------------------------------------
               (h->i) ->  (f -> j -> h) -> (f -> j -> i)

Or,

               (                     h             -> i) 
                      ->  (f -> j -> h)
             --------------------------------------------
                                        -> (f -> j -> i)

---

The types of such composition chains are often easier to follow with (>>>) = flip (.):

(.) . (.) = comp2  .  comp1
          = comp1 >>> comp2    where   comp1 = (.) ; comp2 = (.)

(>>>)    ::   (  a    ->         b         ) -> 
                        (        b           ->         c         )  ->  (a -> c)
comp1    ::    (e->f) -> ((d->e) -> (d->f))
comp2    ::              (  h    ->   i   )  -> ((g->h) -> (g->i))
-------------------------------------------------------------------------
               (e->f)                        -> ((g->h) -> (g->i))
                         h~(d->e)   i~(d->f)
-------------------------------------------------------------------------
               (e->f) -> (g->d->e) -> (g->d->f)

Thus, again,

((.) . (.)) :: (c->r) -> (a->b->c) -> (a->b->r)
((.) . (.)) f g a b = f (g a b)

Indeed,

((.) . (.)) f g a b = ((.) . (.)) f  g  a  b
                    =  (.) ( (.)  f) g  a  b
                    =      ((f .)  . g) a  b     -- NB
                    =       (f .)  ( g  a) b
                    =       (f .     g  a) b

                    =        f (     g  a  b)

NB:

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

---

You can also verify that

((.) . (.) . (.)) :: (d->r) -> (a->b->c->d) -> (a->b->c->r)
((.) . (.) . (.)) f g a b c = f (g a b c)

Why? (.) is fmap for functions, and so we can re-write the above as

(fmap . fmap . fmap) f g a b c =
   fmap (fmap (fmap f)) g a b c =
   (do { x <- g ; return $ fmap (fmap f) x }) a b c =
   (do { x <- g ; return $ do { y <- x ; return $ fmap f y } }) a b c =
   (do { x <- g ; return $ do { y <- x ; return $ do { z <- y ; return $ f z } } }) a b c =
   let x=g a in (const $ do { y <- x ; return $ do { z <- y ; return $ f z } }) a b c =
   let x=g a in (do { y <- x ; return $ do { z <- y ; return $ f z } }) b c =
   let x=g a in let y=x b in (const $ do { z <- y ; return $ f z }) b c =
   let x=g a in let y=x b in (do { z <- y ; return $ f z }) c =
   let x=g a in let y=x b in let z=y c in const (f z) c =
   let x=g a in let y=x b in f (y c) =
   let x=g a in f (x b c) =
   f (g a b c)

This obviously works for any number of the chained compositions of fmaps that way.