Lambda the Ultimate

This is not an appropriate question for LtU. If you have Haskell-specific questions then the Haskell mailinglists (haskell-cafe@haskell.org or beginners@haskell.org), the Haskell IRC channel (#haskell on freenode.net), or the Haskell newsgroup (comp.lang.haskell) are the places to ask.

Map applies a function of one argument to a list of items.

double n = n*2
map double [x,y,z] => [double x, double y, double z]

But map isn't a one argument function: it takes two arguments. So what happens if you apply map to one argument? map double returns a function that doubles all numbers in a list.

double_all = map double
double_all [1,2,3] => [2,4,6]

Instead of thinking of map as taking a function and a list, try to think of it as a function transformer. map fn transforms the function fn to work on lists. double doubles a number; map double doubles a list of numbers.

map transforms a function; map map transforms a list of functions. So map takes a function (type a -> b) and transforms the function to operate on lists (type [a] -> [b]). map map is a function that takes a list of functions [a -> b] and returns a list of transformed functions [[a] -> [b]].

I hope this helps.

It's also possible to derive the type by syntactic transformations and substitutions like the Haskell implementation, but that doesn't teach you as much about the function.

The type of map is represented as map :: (a -> b) -> [a] -> [b]. You could think of this as a 2-argument function or, thanks to currying, think of it as a function taking one function argument and returning another. You should recognize that the function operator (->) is right-associative, so if you add some extra parentheses for clarity, you get map :: (a -> b) -> ([a] -> [b]).

Suppose you had a place in code requiring some vague polymorphic function of type c -> d. Now, knowing what you learned above, you can see how map can be substituted in this location. (a -> b) generalizes to c, and ([a] -> [b]) generalizes to d.

It turns out the map is itself such a function that takes an argument of type c -> d (or use your favorite two different type variables). The rest is just algebraic substitution.

Suppose we have these two functions (for the sake of argument and clarity):

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

Let's write map map'. First, we substitute (a -> b) for c. Then, we substitute ([a] -> [b]) for d. Lastly, we remove the first argument, because it has already been applied (it is map' after all).

(0) map :: (c -> d) -> ([c] -> [d])
(1) map :: ((a -> b) -> d) -> ([a -> b] -> [d])
(2) map :: ((a -> b) -> ([a] -> [b])) -> ([a -> b] -> [([a] -> [b])])
(3) map map' :: [a -> b] -> [[a] -> [b]]

Of course, really map == map'. And that's it!