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

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:

mconcat :: Monoid a => [a] -> a
mconcat = foldr mappend mempty

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 monoid of endomorphisms under composition.
newtype Endo a = Endo { appEndo :: a -> a }

instance Monoid (Endo a) where
        mempty = Endo id
        Endo f `mappend` Endo g = Endo (f . g)

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:

(<<<|) :: [a -> a] -> a -> a
(<<<|) = appEndo . mconcat . map Endo

{-  ghci> transforms <<<| "olleh"
    "hello world!"
-}

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):

(<<<|) :: Foldable t => t (a -> a) -> a -> a
(<<<|) = appEndo . foldMap Endo

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:

newtype Dual a = Dual { getDual :: a } deriving (Eq, Ord, Read, Show, Bounded)
instance Monoid a => Monoid (Dual a) where
        mempty = Dual mempty
        Dual x `mappend` Dual y = Dual (y `mappend` x)

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

(|>>>) :: Foldable t => t (a -> a) -> a -> a
(|>>>) = appEndo . getDual . foldMap (Dual . Endo)

{-
    ghci> [reverse, (++ " world"), (++ "!")] |>>> "olleh"
    "hello world!"
-}

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. :)