haskelltypestype-inferencecurryingparametric-polymorphism

What is the type of the function g = (.).(.)?


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

But I don't know how to get there.


Solution

  • (.) 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.

    (.) . (.) 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.