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 associative1.
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
The function to combine two endomorphisms,
mappend, is defined as composition
f . g. The
id function is used for
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!"
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
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. :)