map map vs map.map

Question

I'm new to Haskell and I thought that the functions map map and map.map are the same in Haskell. My terminal gives me two different types,

(map.map) :: (a -> b) ->  [[a]]  ->  [[b]]

and

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

How are those functions different from eachother, in terms of syntax, and what does each one of them mean exactly?

Answer 1

The map map expression will take second map as the parameter of the first one. So that means that if we derive the type, we see:

map :: (  a     ->      b     ) -> ([a] -> [b])
map :: (c -> d) -> ([c] -> [d])
-----------------------------------------------
a ~ (c -> d), b ~ [c] -> [d]

This thus means that a has the same type as c -> d, and b has the same type as [c] -> [d]. It thus means that the type of map map is:

map map :: [a] -> [b]
        :: [c -> d] -> [[c] -> [d]]

Here map map thus takes as parameter a list of functions of type c -> d, and it will generate a list of functions that performs a mapping with these functions.

It thus means that if you write:

(map map) [(+1), (*2), (-3)]

you retrieve something like:

[map (+1), map (*2), map (-3)]

---

That is not the case for map . map. This expression is equivalent to (.) map map. The (.) :: (b -> c) -> (a -> b) -> a -> c function takes two functions f and g, and combines these as \x -> f (g x). The type thus means:

(.) :: (  b     ->      c     ) -> ((  a     ->      b     ) -> (a -> c))
map :: (d -> e) -> ([d] -> [e])
map ::                              (f -> g) -> ([f] -> [g])
-------------------------------------------------------------------------
b ~ d -> e ~ [f] -> [g], c ~ [d] -> [e], a ~ f -> g, d ~ f, e ~ g

The type of (.) map map is thus:

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

This function takes a single function of type f -> g, and will generate a function that takes a list of list of fs and it can map these to gs.

So (map . map) (+1) will generate a function such that for:

(map . map) (+1) [[1,4,2,5],[1,3,0,2]]

it will generate:

[[2,5,3,6], [2,4,1,3]]

Answer 2

map . map ≡ (\x -> map (map x))
          ≡ (\x y -> map (map x) y)

map map   ≡ map (map)
          ≡ (\x -> map map x)

So, basically the . smuggles an extra variable into the “function bracket” of the outer map.

It turns map (map) x into map (map x). Both mean something quite different, as the types demonstrate.

In map (map x) y, the x is a function that'll be applied to the inner elements of the nested list y, because map x (partial application) is a list-mapping function. Whereas in map map x, the higher-order function map itself is mapped over the list. That sounds strange but it is possible, it just requires a list of functions (which will be the functions that the inner map maps) and spits out another list of functions (each of which does the mapping over one particular inner list).