Working out function types: map map

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 mapmap is:

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

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

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

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

map::(ab)[a][b]map :: (a \to b) \to [a] \to [b] f::cdf :: c \to d mapf::[c][d]map\;f :: [c] \to [d]

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

map::(ab)([a][b])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 mapmap as a function which takes a function from aba \to b, and returns a function that takes a [a][a] and returns a [b][b].

Now we have mapmap in a form that matches f::cdf :: c \to d:

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

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

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

mapf::[c][d]map\;f :: [c] \to [d] mapmap::[(ab)][([a][b])]map\;map :: [(a \to b)] \to [([a] \to [b])] mapmap::[ab][[a][b]]map\;map :: [a \to b] \to [[a] \to [b]]

So mapmapmap\;map takes a list of functions of the form (ab)(a \to b) and returns a list of functions that take [a][a] an returns [b][b] (i.e. ([a][b])([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 mapmap 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 mapmap as map::(ab)([a][b])map :: (a \to b) \to ([a] \to [b]).

Continuing this line of thinking, mapmapmap\;map will then take a list of functions [ab][a \to b] and return a list of transformed functions that work on lists of aa, or [[a][b]][[a] \to [b]]. This gives us the same result as last time, mapmap::[ab][[a][b]]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.