What is a monad for someone who doesn't want to learn Haskell in order to understand it?

Question

What is a monad in programming, and can it be explained such that:

1. You don't need any prior knowledge of Haskell to understand.
2. You can go ahead and use or build the concept in more mainstream programming languages such as C++/Java/Scala.

Basically, I've been coming across this term in my online learning. As an example, this Java 8 Stream tutorial mentions monads (http://winterbe.com/posts/2014/07/31/java8-stream-tutorial-examples/). So I would like to understand the fundamental concept in a useful way. (As opposed to a stupid way like "Imagine programming as an orange, then monads would be grapefruit ..." sort of thing.)

However, each monad tutorial seems to require prior knowledge of (or tries to teach you on-the-fly) Haskell or Haskell syntax.

Answer 1

I am going to try and give the simplest possible explanation using Scala syntax and semantics.

A Monad is any type that has the following signature:

trait Monad[A] {
  def flatMap[B](f: A ⇒ Monad[B]): Monad[B]
}

def unit[A](x: A): Monad[A]

and satisfies the following laws:

• Left Identity:

  unit(x).flatMap(f) == f(x)
  

• Right Identity:

  m.flatMap(unit _) == m
  

• Associativity:

  m.flatMap(f).flatMap(g) == m.flatMap(f(_).flatMap(g))
  

And that's it. That is the beauty of monads. Anything that satisfies those constraints is a monad. And there are lots of things that satisfy those constraints: Lists, Sets, Dictionaries, Maps, Options, Database Queries, Continuations, Errors, Side Effects, Interpreters, Compilers, …

The power of monads comes from the combination of just enough structure that you can write lots of operations that operate on monads, and at the same time so little structure that lots of things are monads. The combination of those two properties means that you can write lots of operations once that then apply to lots of different types of objects.

And that's one of the problems with monads: their generality. A monad is a very general abstraction, that makes it not immediately obvious what it is. I mean, what do sets, lists, database queries, side effects, continuations, and compilers have in common?

Answer 2

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