To take it to C++ (prior to metaclasses, which will eventually give a way to express this properly), the best description of a monad is this:
A parameterised class (like the STL container types), i.e. a class of the form
template <typename a> class M;
which supports at least the following functions:
“Trivial injection”
template <typename a, typename b> M<a> pure (a x);
Mathematicians call this η, Haskell has traditionally called it return, other languages often unit.
Functor† mapping
template <typename a, typename b> M<b> fmap (std::function<b(a)> f, M<a> m);
A flattening operation
template <typename a, typename b> M<a> join (M< M<a> > mm);
Which mathematicians call μ. Many programming languages (including Haskell) don't implemented this by itself but combined with fmap, as such it is then called flatMap or >>=. But join is the simplest form.
such that the monad laws are fulfilled.
Example for an array type:
template <typename a> struct array { std::vector<a> contents; }; template <typename a> array<a> pure(a x) { return array<a>{{std::vector<a>({x})}}; // array with only a single element. } template <typename a, typename b> array<b> fmap(std::function<b(a)> f, array<a> m) { std::vector<b> resultv; for(auto& x: m) { resultv.push_back(f(x)); } return array<b>{{resultv}}; // array with the elements transformed by the given function } template <typename a> array<a> join(array< array<a> > mm) { std::vector<a> resultv; for(auto& row: mm.contents) { for(auto& x: row.contents) { resultv.push_back(x); } } return array<a>{{resultv}}; // array with all the rows concatenated. }
So, what's the use of this? Well, fmap is pretty useful on its own right, when you quickly want to map a lambda over all the elements of an array (allowing for changing type), without having to fiddle with any iterators (unlike std::transform). But fmap doesn't really require a monad.
What monads really shine at is generically sequencing actions. That won't become very clear with that array example, so let me introduce another monad:
template <typename a> struct writer { std::string logbook; a result; }; template <typename a, typename b> writer<a> pure (a x) { return writer<a>{{"", x}}; // nothing to log yet } template <typename a, typename b> writer<b> fmap (std::function<b(a)> f, writer<a> m){ return writer<b>{{m.logbook, f(m.result)}}; // simply keep the log as-is } template <typename a, typename b> writer<a> join (writer< writer<a> > mm) { return writer<a>{{mm.logbook + mm.result.logbook, m.result.result}}; // Concatenate the two logs, and keep the inner value }
writer more resembles the most [in]famous Haskell monad, IO. The writer type allows you to compose arbitrary log-writing functions together, and without ever having to worry about it, gather all the logbook information.
You may wonder at this point: what is there to log? None of the operations above actually produce any logbook entries! Indeed they don't – in fact the monad laws would be violated if they did! Monads are not about particular actions, pre-built values. Rather, they just give you an extremely generic framework for “glueing together” such actions.
A simple example of such a glueing-compositor is replicateM, which takes a single monadic action and executes it n times in sequence, gathering all the results. Unfortunately, this can't be properly typed in C++ in full generality, but here's a specialized version that only works for the writer monad. First, let's quickly implement that combined fmap-join I mentioned earlier, because it's much more handy than join in practice:
template<typename a, typename b> writer<b> flatMap(std::function<writer<b>(a)> f, writer<a> xs) { return join(fmap(f,xs)); } template <typename a> writer<array<a>> replicateM (int n, writer<a> m) { if (n>0) { writer<array<a>> resultv = fmap(pure, m); for (int i=1; i<n; ++i) { resultv = flatMap( [&](array<a> xs){ return fmap( [&](a x){ return xs.push_back(x);} , m );} , resultv); } } else { return pure(std::vector<a>()); } }
Notice that none of the code above actually uses anything specific to writer, so I could copy&paste it and use it for any other monad. (Or, use a language with higher-kinded polymorphism and just write it once and for all.)
What replicateM does in case of writer is frankly quite dumb – it just repeats the same log message n times, and replicates the result value n times as well. However, that's just the simplest example: monads can also have much more functionality, for example, in the IO monad, each invocation might yield a different result (e.g. because it reads from standard input). A generic monad interface allows you to abstract over all kinds of different side-effects, but still keeps clear track of what side-effects can possibly happen in a given context.
†Unfortunately, the C++ community misuses the word “functor” simply to describe function objects. Although this is a related concept, a functor is actually more than that.
