Sealgram

A Detour

Monads are commonly used in functional programming. They come from a recent mathematical framework named "Category Theory" that is one of the deepest models from computer science, and led to the creation of an entire new set of programming languages.

Monads appear from the union of several concepts that do not appear at the most used languages, and that makes they very challenging for beginners. But they aren't complex by themselves, just very different from what people are used to. Hence the popularity of their tutorials.

In a short explanation, monads are high order types (types that apply to types) that have two operations:

• An operation that encapsulates a value of pure type - in Haskell, called "return" or "pure".
• An operation that sequences functions that operate within the monad - normally called "bind", in Haskell, the operator ">>=".

There are some sanity rules for encapsulation and sequencing, and that's it, those are monads.

Not very fulfilling, I'd say, but that is modern Math. It doesn't have any intrinsic meaning. It is an abstract tool that can be used to guide thinking and communication, it acquires meaning only upon use. Programmers shouldn't think this is odd, we spend our days making machines manipulate abstract bit patterns on memory, that only acquire any meaning on I/O - programs are Math after all.

But don't panic, it gets more tractable when more concrete.

A Kind of Repetition

Consider this C code. Let's pretend we have a settings file to read, and want to populate a struct or get an error on invalid or missing settings (ignore memory leaks):

struct {
       bool success;
       void * val;
       void * err;
} Ret;
//Several lines later
Ret *readSettings(){
       Settings *s = malloc(sizeof settings);
       //Here comes the problem:
       e = readX1(s);
       if(e){
           Ret *r = malloc(sizeof Ret);
           r->success = 0;
           r->err = e;
           return r;
       }
       e = readX2(s);
       if(e)
       if(e){
           Ret *r = malloc(sizeof Ret);
           r->success = 0;
           r->err = e;
           return r;
       }
       //Many more lines, with a lot of other settings
       r = mallor(sizeof ret);
       r.success = 1;
       r.val = s;
       return r;
}

That's a very common pattern, and a real problem for Java-like languages. It leads to lots of boilerplate, that will contain typos, and need editing as the code evolves, but adds very little meaning. C has some tools to cope with it. Dark tools, it must be said, but they do solve the problem. One of them is preprocessor macros:

#define test(x, y) e=(y); if(e){Ret *r = malloc(sizeof Ret); \
       r->success = 0; r->err = e; return r;}

  Ret *readSettings(){
       Settings *s = malloc(sizeof settings);
       Ret *r;
       //Problem solved
       test(s->x1, readX1(s));
       test(s->x2, readX2(s));
       //And the many other tests
       r = mallor(sizeof ret);
       r.success = 1;
       r.val = s;
       return r;
  }

Macros are known to be dangerous. Since they act on the textual representation of the program, they are very hard to write correctly, and since they execute before the compiler, they lead to opaque error messages and unintuitive execution sequence. Something similar can be done in code: [2]

Ret *join(Settings s, int n, Error *(*f[])(Settings *)){
       Error * e = NULL;
       for(int i = 0; i < n; i++){
           if(e)
               return e;
           e *(f[i])(s);
       }
}

Ret *readSettings(){
       Settings *s = malloc(sizeof settings);
       Ret *r;
       //Problem solved again
       e = join(s, 2 /* number of reads */,
       {readX1, readX2 /* many other reads */});
       if(e){
           r->success = 0;
           r->err = e;
           return r;
       }
       r->success = 1;
       r->val = s
       return r
}

What is a very specific way to solve the problem. With templates, on C++, it would be possible to extend this example to more function types, and pass return values around. But as one adds flexibility, it quickly becomes more verbose than the original, and harder to both create and use.

Anyway, the first example goes on the line of a kind of metaprogramming very idiomatic in Lisp. Let's call it "static metaprogramming" - in contrast to what would be "dynamic metaprogramming", more common in Python. The second example instead, goes in the direction of programs that take programs as parameters. Let's call it "high order programming". This second one is idiomatic in Haskell.

Enter monads.

Monads for a Cleaner Code

Monads are a standard way of representing code sequencing. Since it's standard, languages that use them have plenty of tools directed at them. On the Haskell case, even specialized syntax - the "do syntax", that starts with the "do" reserved word, and applies the bind operator (>>=) automatically to every line.

In Haskell, the binding at the example is encoded by the Either monad, available at the standard library. The code would look like:

do
    x1 <- readX1
    x2 <- readX2
    -- Many other reads
    pure $ Settings x1 x2 -- and the other xs

Yes, automatic memory management helps, but this isn't the only gain there. All the returns are implicit by the return type of the reads.

Notice that while metaprogramming acts upon a single "program" type, high order programming can take and generate a big diversity of types. It's no coincidence Haskell brings both strict types and high order programming - if you want the compiler checking your code, you can not rely on metaprogramming.

But as usual as the Either pattern is, it is just not troublesome enough to justify developing an entire theory. No, a big point of monads is that they are generic. There are plenty of useful bindings for all the kinds of contexts.

Take this configuration file example - instead of just stopping on an error, it can also automatically pass the file data as a parameter to the functions, and collect the searched key names to check if no strange key is present on the file after processing. This monad is not available on any public library that I know of, but it's there at the Walrus codebase.

Another example, and also common, are the monadic parsers. Those monads bind a series of tests over input data, abstracting all the upkeeping of feeding data to the tests, joining results, and forking or backtracking through optional paths.

To keep it short, monadic parsers become as simple as regular expressions, but with a more verbose yet less cryptic syntax, without the one-liner constraint, and with all the normal language features available, like arithmetic, conditionals, loops, functions, type checking, etc. The following is an entire parser for HTTP headers, that finds the Host header and returns its value, on the Attoparsec Text Parser monad: [3]

httpHost =
       (do
            -- A blank line finishes HTTP headers
            endOfLine
            fail "Host header not found"
       ) <|> (do
            -- This is the Host header
            skipSpace
            stringCI "Host:"
            skipSpace
            takeTill isSpace
       ) <|> (do
            -- This is another header - skip and continue
            takeLine
            httpHost
       )
       where
            takeLine = do
               takeTill isEndOfLine
               endOfLine

Seasoned Haskell developers would use less lines and more operators, but that's the overall idea. I hope even somebody that has never written a line of Haskell can appreciate how clear this is, and the complete lack of accidental complexity. It is all encoded at the monad's bind operator, so it does not pollute domain specific code.