10
Aug 2017

# Haskell: demystifying composing compose with compose

Tags |

On Computer Technology

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

```
(.) . (.)
```

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!

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.

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

Disclaimer: Opinions expressed on this blog are solely my own and do not express the views or opinions of my employer(s), past or present.