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?
[x] -> [x]
head :: [x] -> x
and
append :: x -> [x] -> [x]
.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.Chain
m a
is an Array of Numbers.m b
is the same type as m a
: A Chain
of an Array of Numbers.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.