Last post we looked at composing lists of functions using folds. This let use write functions of type `[a -> a] -> a -> a`

to compose lists of functions (take a list of functions `a -> a`

, and return a single function `a -> a`

).

Another way to do this relies on treating functions of type `a -> a`

, also known as endomorphisms, as a monoid.

## Prologue (or "Why bother?")

Me-from-a-year-ago would have tuned out when someone dropped a monoid-bomb or similar term, assuming it was too complicated. Since then I’ve found lots of maths / category theory terms co-opted by computer science that represent surprisingly straight-forward and useful concepts. No Babel fish required, just a little bit of patience. :)

Even more surprisingly, I’ve found looking at this stuff both interesting and fun!

"[O]ne of the joys of functional programming is the way in which apparently-exotic theory can have a direct and practical application … ."

Too right! So let’s dive right in. Please ask me to clarify anything I’ve done a bad job of explaining (if it’s confusing it means I’m explaining it poorly. It’s not you, it’s me). Or if you know all this stuff already please point out the mistakes I’ve made.

## Monoids in Haskell

A monoid is a type that has an associative binary function, and an identity value such that when we pass it as one of the arguments to that function, we always get the other argument back.

This is much simpler to understand by looking at examples. The Sum monoid for numbers is the function `(+)`

and the value `0`

. This is associative (`1 + (2 + 3) = (1 + 2) + 3`

), and has the required identity property (`x + 0 = x`

). Another example is multiplication, which has function `(*)`

and value `1`

. Division is not a monoid because `10 / (5 / 2) != (10 / 5) / 2`

, so it is not associative^{1}.

In Haskell monoids are represented with the Monoid type class. The binary function is called `mappend`

(it combines, or appends, two values), and the identity value is called `mempty`

. (We need to provide implementations of these two functions when we make a type an instance of the monoid typeclass.)

Using these two properties we can define a function that combines arbitrarily many monoid values. This function is called `mconcat`

in Haskell, and its default implementation looks a bit like this:

This means that for any monoid we can combine multiple values. Handy!

## A monoid for endomorphisms

Roughly speaking, "endomorphism" means a mapping from a type into itself ("endo" for "inside", "morphism" for "transformation"). A function `a -> a`

is a mapping into itself; it takes an `a`

and maps it to another `a`

.

Haskell has a monoid defined for endomorphisms called `Endo`

. This is how `Endo`

is implemented in Haskell:

The function to combine two endomorphisms, `mappend`

, is defined as composition `f . g`

. The `id`

function is used for `mempty`

, as `f . id = f`

.

## Putting it all together

This means that if we wrap our `a -> a`

functions in the `Endo`

type (using `map Endo`

on the list of functions), we can use `mconcat`

to compose them all together.

```
ghci> import Data.Monoid
ghci> let transforms = [(++ "!"), (++ " world"), reverse]
ghci> mconcat (map Endo transforms) `appEndo` "olleh"
"hello world!"
```

The `appEndo`

function applies the resulting, composed endomorphism to the argument `"olleh"`

. We had to wrap our function in the `Endo`

type to treat it as a monoid, so we have to unwrap it using `appEndo`

before we can use it (this wrinkle is specific to Haskell, rather than part of the underlying theory).

We can now rewrite `<<<|`

, our right-to-left composition operator from last post, like this:

We can simplify the `mconcat . map Endo`

expression using `foldMap`

from the `Data.Foldable`

module (this also means we can compose functions in any foldable structure, not just lists):

The main difference between this and the original function, `fs <<<| input = foldr ($) input fs`

, is that the former explicitly declares we are working with endomorphisms, which compose when concatenated as monoids. The latter expresses more of the mechanics of the operation; it is less declarative.

Which is easier to understand will depend on the reader’s knowledge of concepts like monoids, but I like the idea that mathematical concepts can provide a deeper understanding of a program’s intention.

## For extra credit: Left-to-right composition using `Dual`

The implementation above composes right-to-left, as if we had written `(++ "!") . (++ " world") . reverse`

. If we want to instead compose left-to-right, we can use the dual of the endomorphism monoid.

We can do this in Haskell with the `Dual`

monoid, which combines monoid values in the opposite order by flipping the arguments given to `mappend`

. When combined with the `Endo`

monoid, this reverses the order our functions are composed. From the Haskell source:

Which means we can compose any number of functions left-to-right like this:

Our previous example used `foldl'`

to get functions composing in this order:

`fs |>>> input = foldl' (flip ($)) input fs`

Again, this seems to focus more on the mechanics of the operation, rather than relying on the properties of the things we are composing. Unwrapping our function using `appEndo . getDual`

is an unfortunate bit of mess, but `foldMap (Dual . Endo)`

shows that we are folding (reducing) our functions as the dual of endomorphism composition (I am sure I am butchering the terminology here, but from my layman’s perspective we’re composing endomorphisms in the opposite order, so I’m calling that the dual. Please correct me).

In this particular case we may be better off reversing the composition like this:

`(|>>>) = (<<<|) . reverse`

Still, I find it very interesting how we can use mathematical properties to combine functions in different ways. The `Dual`

monoid folds other monoids in the reverse order, and `Endo`

folds functions `a -> a`

using standard right-to-left composition, so `Dual . Endo`

gives us left-to-right composition. I’ve got no idea what to do with this information, but for some reason I find it fascinating. :)

Thanks to Dan for correcting my original example↩