Function composition in Haskell example

Question

Assume b is a list of Strings and consider,

map (map (\a -> ((head a), (length a))) . group . sort) (transpose b)

I know what each individual function above does, but I'm having trouble seeing how the result is assembled. How would I go about figuring out the order in which the functions on this line run, with which parameters?

Specifically, I seem to understand that (map (\a -> ((head a), (length a))) . group . sort) is the the first parameter to the outer map and (transpose b) is the second parameter to the outer map.

But which are the parameters for the inner map? The inner map appears to just have one parameter: (\a -> ((head a), (length a))) . group . sort). Where is the second parameter (the list to which to apply, element-wise, the function in the first parameter)?

Answer 1

What you have noticed is called currying and it's one of many great (or maybe not) aspects of Haskell functions. This is your code:

map (map (\a -> ((head a), (length a))) . group . sort) (transpose b)

Let's check the type of the first map:

map (\a -> ((head a), (length a))) :: [[a]] -> [(a, Int)]

We do so by typing this

:t map (\a -> ((head a), (length a)))

into ghci.

So know we know it's a function. It takes an element of type [[a]] and returns [(a, Int)]. Give the type of the map function is

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

This is perfectly fine. We have given map it's first argument, now, all that it need it's a proper list. What just happened with map is called currying.

Now let's see, we have our map "connected" to sort and group through the (.) function.

(.) :: (b -> c) -> (a -> b) -> a -> c

Now let's change a little your piece of code so we can see better what's going on with the composition function.

map (\a -> ((head a), (length a))) . (group . sort)

I just separated group and sort with some parenthesis. But now we clearly see which elements act as arguments of the outer (.).

We have the map in question, and another function, which results from the other composition. Again we have the currying in action, when we leave out the last argument:

map (\a -> ((head a), (length a))) . (group . sort)
:: Ord a => [a] -> [(a, Int)]

Finally the outer map takes the function from above and a list (transpose b).

Answer 2

It is given implicitly. If you write:

map (\a -> ((head a), (length a))) . group . sort

this is actually short for:

\b -> (map (\a -> ((head a), (length a))) . group . sort) b

which is equivalent to:

\b -> map (\a -> ((head a), (length a))) $ group $ sort b

or:

\b -> map (\a -> ((head a), (length a))) (group (sort b))

The (.) :: (b -> c) -> (a -> b) -> a -> c operator, thus composes two functions together in some sort of pipeline:

(.) f g x = f (g x)

Since we here write three functions separated by dots:

   map (\a -> ((head a), (length a))) . group . sort
-- \_________________ ______________/   \_ _/   \_ /
--                   v                    v       v
--                   f                    g       h

we have defined some sort of pipeline where an element is first processed through h, then the result is processed through g, and finally the result of that is processed through f.

Answer 3

The dot is itself a function, defined like this:

(f . g) x = f (g x)

Let's use this equation in the first argument to the outer map:

map (\a -> (head a, length a)) . group . sort
= { definition of (.), with map (\a -> ...) as f and group . sort as g }
\x -> map (\a -> (head a, length a)) ((group . sort) x)

So, map (\a -> ...) . group . sort is a function which, when applied to argument x, supplies (group . sort) x as an argument to map (\a -> ...).