One of the exercises in Introduction to Functional Programming by Richard Bird and Philip Wadler is to work out the type signature of `map map`

(i.e. calling `map`

with `map`

as its first argument). I’ve generally struggled to deal with all but the simplest of partial function application, but I found a great thread on the Lambda the Ultimate forums that really helped me out with this. Two commenters suggested different approaches: going through the maths, and understanding the abstraction.

## Solving algebraically

The signature for $map$ is:

$map :: (a \to b) \to [a] \to [b]$

The first argument is a function which takes an $a$ and returns a $b$. The second argument is a list of $a$. The last type, a list of $b$, is the function’s return value.

To work out the signature of $map\;map$, we need to substitute in what we know about $map$’s type signature to work out the resulting combination of $a$ and $b$. I found this really tricky, but by applying a few rules we can work it out.

First, let’s pass some arbitrary function $f :: c \to d$ as the first argument to $map$.

$map :: (a \to b) \to [a] \to [b]$ $f :: c \to d$ $map\;f :: [c] \to [d]$

In our case, we want to pass $map$ as $f$. But $f$ is a function that takes one argument, while $map$ takes two. So how can we use it in place of $f$? Well, the $\to$ operator is right-associative, which means we can re-write $map$ like this:

$map :: (a \to b) \to ([a] \to [b])$

This is know as *currying*. In Haskell, all functions can be considered to take one argument, and return a function that takes the remainder of the arguments. Here, we’re thinking of $map$ as a function which takes a function from $a \to b$, and returns a function that takes a $[a]$ and returns a $[b]$.

Now we have $map$ in a form that matches $f :: c \to d$:

$f :: c \to d$ $map :: (a \to b) \to ([a] \to [b])$

So: $c :: (a \to b)$ $d :: ([a] \to [b])$

Now we can substitute back into our $map\;f$ type declaration:

$map\;f :: [c] \to [d]$ $map\;map :: [(a \to b)] \to [([a] \to [b])]$ $map\;map :: [a \to b] \to [[a] \to [b]]$

So $map\;map$ takes a list of functions of the form $(a \to b)$ and returns a list of functions that take $[a]$ an returns $[b]$ (i.e. $([a] \to [b])$).

## Solving intuitively

The other suggested approach was to think about the abstractions being used, rather than the mathematical basis for the functions. I tend to struggle with this, but it is worth trying to come to grips with the concepts and intention, and not just rely on somewhat-blindly applying maths principles.

The $map$ function conceptually represents transforming a function to work on a list. For example, `(+1)`

adds one to a single number, while `map (+1)`

adds on to a list of numbers. This corresponds to the step in our last approach where we starting thinking of $map$ as $map :: (a \to b) \to ([a] \to [b])$.

Continuing this line of thinking, $map\;map$ will then take a list of functions $[a \to b]$ and return a list of transformed functions that work on lists of $a$, or $[[a] \to [b]]$. This gives us the same result as last time, $map\;map :: [a \to b] \to [[a] \to [b]]$.

I tend to get lost when I try to think about it this way, but hopefully I’ll start to get the hang of reasoning about functions this way as I get more practice. If not, there is always the option of falling back on the maths.