# Chain, chain, chain

Consider this problem, from a question on stack overflow. Given a list `x::xs`, how can one write a function `f` that will output `x::xs::x`? In other words, write a function that takes the head of the list and appends it to the end of the list?

The description above almost writes the function for us. Here are the component parts:

• Take the head of the list: We have a function for that: `head`. Note the type of `head`:

`head :: [x] -> x`

That signature simply says that when you give `head` a list, it will return the first element of that list.

• Append it to the end of the list: We have a function for that as well: `append`. The type of `append` is:

`append :: x -> [x] -> [x]`

When you give `append` an element and a list, it gives you back a new list with the element at the end.

What will our function `f` look like?

• It will be of the type `[x] -> [x]`
• It will be composed of the parts above, viz. `head :: [x] -> x` and `append :: x -> [x] -> [x]`.
• Somehow we have to get the output of `head` fed into `append` to get us a new function `[x] -> [x]`.

Before I pull a rabbit out of this hat, a few words about `chain`:

``````chain :: Chain m => (a -> m b) -> m a -> m b
``````

Let’s break this signature down into bite-sized pieces and digest them one-by-one.

• `Chain m`: There is some thing `m` that is a `Chain`.
• `=>`: This tells us that whenever we see an `m` in the rest of the singature, we know it is a `Chain` thing.
• `(a -> m b)`: The first argument to `chain` is a function from some type `a` to a `Chain` that “contains” a value of type `b`.
• `m a`: The second argument to `chain` is a `Chain` wrapping a value of type `a`.
• `m b`: This is our return type. `chain` will return a `Chain` wrapping a value `b`.

Here is an example of `chain`. It is often called `flatMap`:

In this example,

• `(a -> m b)` is the function `dup`, `a` is `Number`, and the `Chain` `m b` is an Array of Numbers.
• The `Chain` `m a` is an Array of Numbers.
• The returned value `m b` is the same type as `m a`: A `Chain` of an Array of Numbers.
• Note that in this example, both type variables `a` and `b` refer to the same type: an Array of Numbers. Likewise, `m a` and `m b` both refer to a `Chain` of an Array of Numbers. This need not always be the case, but it is also not a problem when it is the case.

It should be pretty clear how `chain` works in the context of Array of Something. In this case, though, we want to output a Function `f`. Is Function a `Chain`?

Recall the signature:

Replace `Chain m => m` with `Function x`:

You can look at a function from `x` to `a` as a wrapper around its return value `a`. It is analogous to an Array wrapping its elements.

Now use `x -> y` as sugar for `Function x y`:

Adding an extra pair parenthesis to make this clearer:

That looks like it should work! Let’s compare this `chain` signature with the components we are going to use to build `f`:

• `f :: [x] -> [x]`
• `head :: [x] -> x`
• `append :: x -> [x] -> [x]`

`append` is of type `a -> m b`; `head` is of type `m a`. Recall that what we are trying to produce is a function `f` of type `m b`. Now our types line up perfectly: But wait – there’s more! Does this mean that you can do this with any function that satisfies those signatures? That’s exactly what it means. For example, you could `chain` `toLower` and `concat` over a String:

… or `chain` `assoc(keyname)` and `keys` over an Object:

… and so on.

You may be surprised to learn that was a demonstration of how `Function` is a Monad. Proving that – by defining `join` and `return` for Function and showing that it satisfies associativity, left identity, and right identity is left as an exercise for the reader.

29 December 2016