What is the type of the function g = (.).(.)? [Haskell]-CodePudding

The answer is: (a -> b) -> (c -> d -> a) -> c -> d -> b

But I don't know how to get there.

CodePudding user response：

(.) has the type (b -> c) -> ((a -> b) -> (a -> c)). I intentionally added some parentheses for clarity. There are three instances of (.) in the expression (.) . (.) so having the type in three versions using different letters will be handy.

(.) :: (b -> c) -> ((a -> b) -> (a -> c)) – the first instance of (.)
(.) :: (e -> f) -> ((d -> e) -> (d -> f)) – the second instance of (.)
(.) :: (h -> i) -> ((g -> h) -> (g -> i)) – the third instance of (.)

(.) . (.) is aequivalent to ((.) (.)) (.), it's applying (.) to (.) and then applying the result of the first application to (.).

Application of the first instance to the second instance

Match the type of the argument ((e -> f) -> ((d -> e) -> (d -> f))) to the input type of (.) (b -> c):

b = (e -> f)
c = ((d -> e) -> (d -> f))

Then substitue the type variables in the result type of (.) ((a -> b) -> (a -> c)) by the matches from the argument:

(.) (.) :: (a -> (e -> f)) -> (a -> ((d -> e) -> (d -> f)))

Application of the result of the first application to the third instance

Match the type of the argument ((h -> i) -> ((g -> h) -> (g -> i))) to the input type of (.) (.) (a -> (e -> f)):

a = (h -> i)
e = (g -> h)
f = (g -> i)

Then substitue the type variables in the result type of (.) (.) (a -> ((d -> e) -> (d -> f))) by the matches from the argument:

(.) (.) (.) :: (h -> i) -> ((d -> (g -> h)) -> (d -> (g -> i)))

That has the same type as what you have in the question, just with more parentheses and different letters. If I remove unnecessary parentheses, this is the result:

(.) (.) (.) :: (h -> i) -> (d -> g -> h) -> d -> g -> i

What does it do? It takes two arguments of types d and g, applies a function of type d -> g -> h to them, then applies a function of type h -> i to the result.

CodePudding user response：

The type (.) :: (b->c) -> (a->b) -> (a->c) means

    g :: a -> b
f     ::      d -> c
--------------------    d ~ b
f . g :: a ->      c

and hence

      (.) :: (b->c) -> ((a->b) -> (a->c))
(.)       ::           (   s   ->    r  ) -> (t->s) -> (t->r)
-------------------------------------------------------------
(.) . (.) :: (b->c) ->                       (t->s) -> (t->r)
          ~  (b->c) ->                    (t->a->b) ->  t->a->c

which makes sense, because

  ((.) . (.))   f                            g          x  y =
 = (.) ((.) f) g x y
 =    ((f .) . g) x y = (f .) (g x) y 
                      = (f . g x) y    = f ( g          x  y )

because (.) f g x = (f .) g x = (f . g) x = f (g x) (and also = (. g) f x).

(f .) is known as operator section (with the (.) operator). It is a convenient shortcut for writing (.) f.