What is the type of map.map in Haskell?

Question

I want to find the type of map.map. The first image is a solution that i have found, but i don't quite get. My solution would have been like in the second image, but it is wrong. I do not understand the marked bit of the solution. Why is it like that?

Answer 1

Short answer: the arrow type constructor (->) is a right associative operator.

The arrow is right associative. This means that if you write:

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

more verbose, you wrote:

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

So given the first parameter of (.) has type (a -> b), this thus means that the type (d -> e) -> ([d] -> [e]) ~ a -> b (~ means the same type), and thus a ~ d -> e and b ~ [d] -> [e]. The same of course holds when we type check with the second map.

With that in mind we thus, like the nodes say derive:

(.) map map :: (f -> g) -> ([[f]] -> [[g]])

This thus means that this function takes a function of type f -> g, and maps all the elements in the lists of a list to a list of lists maintaining the structure.

For example:

Prelude> (.) map map (+1) [[1,4,2,5], [], [1,3], [2]]
[[2,5,3,6],[],[2,4],[3]]