Haskell partial application of functions, deriving types

4
votes

In GHCI prelude> using :t for finding the types of functions:

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

(:) :: a -> [a] -> [a]

((.)(:)) :: (a -> b) -> a -> [b] -> [b]   -- (what happened here?)

I understand the result of the single functions, but when partially applied I do not.

what is the type of map map ? I found an answer on this page, how to do this algebraically. But I have a problem applying the same method on the ((.)(:)).

What is the method when you want to know the type of ((.)(:))? Is there a way of thinking that can be used for any partial application of a function?

Thanks in advance.

2
haskell

2 Answers

9
votes

The best thing to do, when you want to infer a type for a partial application is to start from the most general types of your building blocks and search for matches between the types you're composing. Let me make this more clear by describing you the reasoning I followed for the type you was searching for.

First of all, let's rename the type variables for (:) in order to avoid confusion:

(.) :: (b -> c) -> (a -> b) -> a -> c
(:) :: d -> [d] -> [d]

(.) (:) partially applies (:) to (.), providing its first argument only. This means that the first argument of (.), that is of type (b -> c), is instantiated to (d -> ([d] -> [d])), with b == d and c == ([d] -> [d]) (remember that -> is right associative).

If you apply this type substitution in the whole thing, you get that the partially applied (.) loses its first argument (it has been fixed as (:)) and results in (a -> d) -> a -> ([d] -> [d]), that is equivalent to (a -> d) -> a -> [d] -> [d] (again, by right-associativity): this is the type expression you got from ghci.

6
votes

To expand on @Riccardo's answer:

  1. Correspondence of type signatures

    (b  ->       c     )       -- first argument of (.)
(d  ->  ([d] -> [d])       --   corresponds to type of (:)

  2. Substitution

    (a -> b) -> a ->      c    -- rest of (.)'s type, minus first argument

    to 

    (a -> d) -> a -> ([d] -> [d])

  3. Right associativity

    (a -> d) -> a -> [d] -> [d]