0

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

But I don't know how to get there.

halfer
  • 19,824
  • 17
  • 99
  • 186
David Vives
  • 55
  • 1
  • 5
  • 1
    Write the type of `(.)` as `A -> B` for some A and B. Then write the type of the second `(.)` as `C -> D` -- it will be the same as `A -> B`, but using distinct type variables. Unify `B = C`, finding the values for some type variables. Then, the type `A -> D` (after unification) will be the one you mentioned. – chi Nov 05 '21 at 11:05
  • See also https://stackoverflow.com/questions/69851325/generic-type-of-map-filter for a similar example. – Paul Johnson Nov 05 '21 at 11:46
  • see [this](https://stackoverflow.com/a/34701189/849891) for a very close duplicate. – Will Ness Nov 05 '21 at 12:33
  • also [this](https://stackoverflow.com/questions/15029843/how-can-i-understand/849891) is closely related. – Will Ness Nov 05 '21 at 12:37
  • [How to determine type of Haskell functions?](https://stackoverflow.com/q/11638232/791604) includes some tips on solving questions like this. – Daniel Wagner Nov 05 '21 at 14:32

2 Answers2

5

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

Micha Wiedenmann
  • 19,979
  • 21
  • 92
  • 137
matj1
  • 158
  • 1
  • 11
0

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.

Will Ness
  • 70,110
  • 9
  • 98
  • 181