## Yan Han's blog

On Computer Technology

 Tags

## 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

``````swap (x, y) = (y, x)
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.