Why does (.) map have this type?

Question

I tried to find the type of the function (.) map but somehow find that it is ((a -> d) -> (a -> e)) -> ([d] -> [e]) which according to GHCI is not correct because it should be (.) map :: (a1 -> a2 -> b) -> a1 -> [a2] -> [b].

What am I doing wrong?

Answer 1

You have probably tried to match the functions by looking at the definition

Types of the two functions
(.) :: ((b -> c) -> (a -> b) -> a -> c)
map :: (d -> e) -> [d] -> [e]

and then trying to match d to b and e to c. Which gives you ((a -> d) -> (a -> e)) -> ([d] -> [e]), now you could match [d] to a and [e] to d. This is however not correct because according to the type definition of map, e and d could be of different type, i.e. d could be of type [e] but it doesn't have to.

The correct way to find the type of this function is to look at the definition of the types

Types of the two functions
(.) :: ((b -> c) -> (a -> b) -> a -> c)
map :: (d -> e) -> [d] -> [e]

and then to match (d -> e) to b and [d] -> [e] to c which gives you (a -> (d -> e)) -> a -> ([d] -> [e]), by removing the superfluous brackets and renaming the type variables you get (a -> b -> c) -> a -> [b] -> [c]. This is the same result GHCI gives you.

Answer 2

Deriving the type...

We have as ingredients:

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

(here I used different type identifiers for the two functions to avoid any confusion). A more verbose form (where we make it more explicit that every function takes exactly one parameter) is:

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

Since map is the first parameter of (.) that means that its type (d -> e) -> ([d] -> [e]) should match the input type of the (.) function (so b -> c). This thus means:

  b        -> c
~ (d -> e) -> ([d] -> [e])
------------------------------
b ~ (d -> e), c ~ ([d] -> [e])

So that means that the result type of (.) map is:

(a -> b) -> (a -> c)

which is equivalent to:

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

or less verbose:

(.) map :: (a -> d -> e) -> a -> [d] -> [e]

... and its implementation

The (.) function can be seen as (.) f g == \x -> f (g x). So that means that our function

h = (.) map

is equivalent to:

h f x = map (f x)

It thus takes as input a function f and an object x, and than performs a map with f x as function.

Semancially you could say that we make a "map where one has to inject a 'contect'-objecct" of type a. This context is then taken into account by the processor. This could be useful if we want to apply multiple maps, each with a small change, and thus first pass a "context-object". This is of course an interpretation of humans. For a compiler, the x can have any use, interpretation, etc.

Answer 3

When I don't understand the type of a function, I write types using different letters:

(.) :: (b -> c) -> (a -> b) -> a -> c
map :: (x -> y) -> [x] -> [y]

now we are providing map as the first argument of (.) so we can deduce:

b -> c == (x -> y) -> [x] -> [y] -- by matching first arguments we get...
b == x -> y                      
c == [x] -> [y]

since we have already provided the first argument of (.), the whole b -> c part disappears.

(.) map :: (a -> b) -> a -> c                -- Using the above equations for b and c
(.) map :: (a -> x -> y) -> a -> [x] -> [y]  -- changing variables names
(.) map :: (a1 -> a2 -> b) -> a1 -> [a2] -> [b]

as GHCi plots