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:

What will our function f look like?

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.

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

    const dup = x => [x, x];
    chain(dup, [1, 2, 3]); //=> [1, 1, 2, 2, 3, 3]
    

In this example,

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:

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

Replace Chain m => m with Function x:

    chain :: (a -> Function x b) -> Function x a -> Function x b
    

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:

    chain :: (a -> x -> b) -> (x -> a) -> (x -> b)
    

Adding an extra pair parenthesis to make this clearer:

    chain ::      (a -> (x -> b)) -> (x -> a) -> (x -> b)
                         ^^^^^^       ^^^^^^      ^^^^^^
    // analogous to:       m b          m a         m b
    // analogous to:       [b]          [a]         [b]
    

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

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:

    const f = chain(append, head); //=> f :: [x] -> [x]`
    f([1, 2, 3]); //=> [1, 2, 3, 1]
    

ta-da

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:

    chain(concat, toLower)("ABCD"); //=> "abcdABCD"
    

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

    chain(R.assoc('keylist'), keys)({a: 1, b: 2, c: 3}); //=> {a: 1, b: 2, c: 3, keylist: ['a', 'b', 'c']}
    

… 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.

Buzz de Cafe 29 December 2016