Haskell: demystifying composing compose with compose

Problem Statement

Figure out the type of the following Haskell code, why it has that type, and what it does:

(.) . (.)

Solution

It is trivial to type :t (.) . (.) into ghci to get the following:

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

What is more difficult is to figure out why this, and not something else, is the type of (.) . (.). We shall do exactly that here.

First, we have to realize that (.) . (.) can also be written as:

(.) (.) (.)

which is its prefix equivalent form. Then, we make use of the fact that in Haskell, function application is left associative. So the same code can be written as:

((.) (.)) (.)

Now, we have the job of figuring out the type of:

((.) (.))

If we type that into ghci, we get:

(a1 -> b -> c) -> a1 -> (a -> b) -> a -> c

which may actually look more intimidating than the type of (.) . (.). So why does (.) (.) have the above type?

Recall that the compose operator (.) has type:

(b -> c) -> (a -> b) -> a -> c

Now we try to match the types. In (.) (.), we rename the type variables so that the (.) that serves as the argument has the type

(b1 -> c1) -> (a1 -> b1) -> a1 -> c1

Since this (.) is just 1 argument, we must have that (b -> c) in the compose that’s being called be of type (b1 -> c1) -> (a1 -> b1) -> a1 -> c1. Using the fact that the -> operator is right associative, we must have the following type matches:

b: (b1 -> c1)
c: (a1 -> b1) -> a1 -> c1

So after taking (.) as its first argument, the type of the compose being called is now:

(a -> b) -> a -> c

before substitution. Now we perform the substitution and get:

(a -> (b1 -> c1)) -> a -> (a1 -> b1) -> a1 -> c1

Renaming b1 to b and c1 to c, we get

(a -> (b -> c)) -> a -> (a1 -> b) -> a1 -> c

We can also remove the inner parentheses in (a -> (b -> c)) (because there are only 1 argument functions in Haskell) to get:

(a -> b -> c) -> a -> (a1 -> b) -> a1 -> c

Then we swap the names of a1 and a to get:

(a1 -> b -> c) -> a1 -> (a -> b) -> a -> c

which is the type of (.) (.) that we got from ghci.

Now that we got the type of (.) (.), we have to figure out the type of ((.) (.)) (.), or equivalently, (.) (.) (.). We rename the type variables of the (.) argument so that it has type (b2 -> c2) -> (a2 -> b2) -> a2 -> c2. Doing some pattern matching between this and the type of (.) (.), we get:

a1: (b2 -> c2)
b:  (a2 -> b2)
c:  a2 -> c2

After applying (.) (.) with (.), its type pre-substitution is:

a1 -> (a -> b) -> a -> c

Now we substitute what we got from pattern matching on the types to get:

(b2 -> c2) -> (a -> (a2 -> b2)) -> a -> a2 -> c2

We can get rid of the inner parentheses in the second argument and rename b2 to b, rename c2 to c to get:

(b -> c) -> (a -> a2 -> b) -> a -> a2 -> c

We can rename a to a1 and a2 to a to get

(b -> c) -> (a1 -> a -> b) -> a1 -> a -> c

which is what we want. If we erroneously started out pattern matching the type signature of compose with its 2 arguments which also happen to be compose, we can probably never arrive at the correct type signature. Just look at the type of the second argument of (.) . (.) - it is a1 -> a -> b, a function with 2 arguments! Who would have known!

Context

I was reading about the ST monad when I encountered this answer: https://stackoverflow.com/a/28146074. When I saw the following snippet of code:

swap (x, y) = (y, x)
(.*) = (.) . (.)

filterAccum :: (a -> b -> (Bool, a)) -> a -> [b] -> [b]
filterAccum f a xs = [x | (x, True) <- zip xs $ snd $ mapAccumL (swap .* f) a xs]

I was flabbergasted at the definition (.*) = (.) . (.), and how .* was later used in (swap .* f). It looked so surreal (just like a lot of Haskell code I’m seeing). I was thinking - no way this works. Then I copied and pasted a slightly modified version of this into a file and compiled it, and it worked. Magically.

Next thing I know, I was figuring out the type of (.) . (.) the wrong way, by pattern matching the types of the arguments directly onto the type of the function, which was exactly what I said not to do at the end of the solution. I thought this will make a good, short blog post, so here we are. I believe that once upon a time I have chanced across a blog post explaining this same topic, but obviously my googling skills weren’t up to par.

References

• https://stackoverflow.com/a/28146074; a Stack Overflow answer to the question Why do we need monads?, by user3237465