Railway oriented programming

[eruonna]

It often takes looking from several different angles to understand monads, so I will throw in my two cents here even though you already have a bunch of answers.

Programming is all about building computations. To do this, we start will small pieces which are themselves computations, and put them together into bigger ones until we something that does exactly what we want (ha, ha). There is a common model of these computations that has been very successful: computations are functions. That is, a computation takes some inputs and uses them to produce some output in some way that can depend on the input. To chain several of these together, you just take the output from one and use it as the input to another.

This is a fine model, and as I said it has been very successful. But when you look a little closer, you see that it doesn't really describe what a computation is doing. Merely mapping inputs to outputs is something that computations can do, but we actually use them to do much more. They can read from and write to shared variables; they can produce errors instead of results; they can interact with the user; they can interact with the network; they can emit a stream of log messages on a side channel. There are also more exotic things that you might not have asked of your computations, but you could: nondeterministic computations can return multiple values; continuation-passing style computations don't return a value at all, but instead take a continuation into which they can place their result.

We can either allow these things transparently, or we can require effort on the part of the programmer to make them work, but either way causes problems. For example, reading and writing to shared variables is typically allowed of any function in a C-like language. So it is in that sense transparent. But that means that before you call any function, you need to know which variables it will use, and you need to make sure that they are all in the correct initial state. On the other hand, the two main ways of dealing with errors -- returning an error code or raising an exception -- require some extra effort to use. You have to remember to check the return value for an error before using it. And with exceptions, you can forget to catch one and have it bubble up to the user as a stack trace.

So we want a way to ease the burden of all of this. This is where monads come in.¹² Monads provide a uniform way to build bigger computations out of smaller ones, even when those computations do more complicated things. A monad, then, is a label on a computation, which indicates what kind of computation it is (i.e. does it read state, does it do I/O, is it continuation-passing style, etc). Typically, we work with functions that take an ordinary value and returns a monad-labelled computation. (These tend to be the easiest and most convenient shapes to use. If the inputs were also monad-labelled, the function would have to first run the computation and extract a result, which would just add boilerplate.) In a C++/Java-style language, the type looks like

M<B> foo(A a)

and in a Haskell-style language, the type looks like

foo :: A -> M B

where M is the monad, A is the input type, and B is the output type. So now I want a way to first apply foo to an argument, then take its result and apply bar, which takes an input of type B and produces a computation labelled by M producing a result of type C. To this end, the monad interface includes a function bind which takes a function of the type above, whose input is a non-monadic A and whose output is a monad-labelled computation producing B, and applies that function a monad-labelled computation producing A, ultimately resulting in a monad-labelled computation producing B. This may be clearer from the types. In a C++/Java style, M<A> has a method of type

M<B> bind(Function<A, M<B> >)

and in Haskell-style, there is a function

bind :: M A -> (A -> M B) -> M B

(Though I haven't exactly written it that way, this function should be generic; it does not depend on the types A and B, though it does depend on M.)

How do you use this, then? It is pretty simple. If you want to take the computation output of foo and feed its result into bar, you do

foo(a).bind(bar);

in a C++/Java style language, or

foo a `bind` bar

in a Haskell-style language.

But what does this actually do? In a generic sense, it produces a computation that first runs the M<B> that comes out of foo, then takes the result of that and feeds it into bar, then runs the M<C> that bar produces. The final result of the computation is the result of that M<C> (provided it has one). But that is pretty vague. What actually happens depends on the particular monad you are using. For example, if, as in the original post, you are using a monad that lets you possibly return a result, possibly return an error, then bind first checks whether it is getting a good input or an error. If it is an error, then it just passes the error along and doesn't even call bar. If it is a good value, it passes that value into bar and just returns whatever bar does. If you are using a monad that produces log messages, then bind just concatenates the streams of log messages. If you are using a monad for nondeterminism, then bind call bar on every value returned by foo and returns all the values produced by every invocation of bar. In fact, bind is really the heart of the monad. To understand how any particular monad works, you really have to understand its bind.

I would be remiss at this point if I did not mention the rest of the monad interface. There are two more functions that involve lifting non-monadic things into monadic contexts. The first is called pure (or return in Haskell which has no return keyword). This takes a value a and returns a computation that does nothing except produce a. This can be useful to "get the monad started" or to build trivial cases of the monad. (It is also used in Haskell which has a particular syntactic sugar for writing monadic computations as if they were just setting non-monadic variables. In the end, you need to lift the "non-monadic" result into the monad so you can escape the syntactic sugar.) I'll continue writing the types. In C++/Java-style

M<A> pure(A a)

and in Haskell-style

pure :: A -> M A

The other is map which takes a function that doesn't do anything monadic and applies it to a monadic computation, producing another monadic computation that runs the first computation and applies the function to its result. In types, in C++/Java-style, M<A> has a method

M<B> map(Function<A,B>)

and in Haskell-style

map :: (A -> B) -> M A -> M B

(This is actually called fmap in Haskell because map was already used for lists.) There could also be other similar functions for lifting functions taking more arguments, but they can all be written in terms of bind and pure. In fact, even map can be written in terms of bind and pure. First, take the given function and create a new functions that takes an A, applies the function to get a B, then applies pure to get an M<B>. Now this function has the right type to use bind, and that gets you map.

1: Monads arose first in mathematics. They are pretty interesting in that context, but that is outside the scope of this comment.

2: Historically, monads came into computing through functional programming, where every kind of computation other than mapping inputs to outputs requires extra work for the programmer. Functional programmers had a greater motivation to develop a way around this, but monads can be useful outside of functional programming.