Tales from the Evil Empire

Bertrand Le Roy's blog

News


Bertrand Le Roy

BoudinFatal's Gamercard

Tales from the Evil Empire - Blogged

Blogs I read

My other stuff

Archives

How I understood monads, part 1/2: sleepless and self-loathing in Seattle

(c) Bertrand Le Roy For some time now, I had been noticing some interest for monads, mostly in the form of unintelligible (to me) blog posts and comments saying “oh, yeah, that’s a monad” about random stuff as if it were absolutely obvious and if I didn’t know what they were talking about, I was probably an uneducated idiot, ignorant about the simplest and most fundamental concepts of functional programming. Fair enough, I am pretty much exactly that.

Being the kind of guy who can spend eight years in college just to understand a few interesting concepts about the universe, I had to check it out and try to understand monads so that I too can say “oh, yeah, that’s a monad”.

Man, was I hit hard in the face with the limitations of my own abstract thinking abilities. All the articles I could find about the subject seemed to be vaguely understandable at first but very quickly overloaded the very few concept slots I have available in my brain. They also seemed to be consistently using arcane notation that I was entirely unfamiliar with.

It finally all clicked together one Friday afternoon during the team’s beer symposium when Louis was patient enough to break it down for me in a language I could understand (C#). I don’t know if being intoxicated helped. Feel free to read this with or without a drink in hand.

So here it is in a nutshell: a monad allows you to manipulate stuff in interesting ways. Oh, OK, you might say. Yeah. Exactly.

Let’s start with a trivial case:

public static class Trivial {
    public static TResult Execute<T, TResult>(
this T argument,
Func<T, TResult> operation) {
return operation(argument); } }

This is not a monad. I removed most concepts here to start with something very simple. There is only one concept here: the idea of executing an operation on an object. This is of course trivial and it would actually be simpler to just apply that operation directly on the object. But please bear with me, this is our first baby step. Here’s how you use that thing:

"some string"
  .Execute(s => s + " processed by trivial proto-monad.")
  .Execute(s => s + " And it's chainable!");

What we’re doing here is analogous to having an assembly chain in a factory: you can feed it raw material (the string here) and a number of machines that each implement a step in the manufacturing process and you can start building stuff. The Trivial class here represents the empty assembly chain, the conveyor belt if you will, but it doesn’t care what kind of raw material gets in, what gets out or what each machine is doing. It is pure process.

A real monad will need a couple of additional concepts. Let’s say the conveyor belt needs the material to be processed to be contained in standardized boxes, just so that it can safely and efficiently be transported from machine to machine or so that tracking information can be attached to it.

Each machine knows how to treat raw material or partly processed material, but it doesn’t know how to treat the boxes so the conveyor belt will have to extract the material from the box before feeding it into each machine, and it will have to box it back afterwards.

This conveyor belt with boxes is essentially what a monad is. It has one method to box stuff, one to extract stuff from its box and one to feed stuff into a machine.

So let’s reformulate the previous example but this time with the boxes, which will do nothing for the moment except containing stuff.

public class Identity<T> {
    public Identity(T value) {
        Value = value;
    }

    public T Value { get; private set;}
    
    public static Identity<T> Unit(T value) {
        return new Identity<T>(value);
    }

    public static Identity<U> Bind<U>(
Identity<T> argument,
Func<T, Identity<U>> operation) {
return operation(argument.Value); } }

Now this is a true to the definition Monad, including the weird naming of the methods. It is the simplest monad, called the identity monad and of course it does nothing useful. Here’s how you use it:

Identity<string>.Bind(
    Identity<string>.Unit("some string"),
    s => Identity<string>.Unit(
s + " was processed by identity monad.")).Value

That of course is seriously ugly. Note that the operation is responsible for re-boxing its result. That is a part of strict monads that I don’t quite get and I’ll take the liberty to lift that strange constraint in the next examples.

To make this more readable and easier to use, let’s build a few extension methods:

public static class IdentityExtensions {
    public static Identity<T> ToIdentity<T>(this T value) {
        return new Identity<T>(value);
    }

    public static Identity<U> Bind<T, U>(
this Identity<T> argument,
Func<T, U> operation) {
return operation(argument.Value).ToIdentity(); } }

With those, we can rewrite our code as follows:

"some string".ToIdentity()
    .Bind(s => s + " was processed by monad extensions.")
    .Bind(s => s + " And it's chainable...")
    .Value;

This is considerably simpler but still retains the qualities of a monad. But it is still pointless.

Let’s look at a more useful example, the state monad, which is basically a monad where the boxes have a label. It’s useful to perform operations on arbitrary objects that have been enriched with an attached state object.

public class Stateful<TValue, TState> {
    public Stateful(TValue value, TState state) {
        Value = value;
        State = state;
    }

    public TValue Value { get; private set; }

    public TState State { get; set; }
}

public static class StateExtensions {
    public static Stateful<TValue, TState>
ToStateful<TValue, TState>(
this TValue value,
TState state) {
return new Stateful<TValue, TState>(value, state); } public static Stateful<TResult, TState>
Execute<TValue, TState, TResult>(
this Stateful<TValue, TState> argument,
Func<TValue, TResult> operation) {
return operation(argument.Value)
.ToStateful(argument.State); } }

You can get a stateful version of any object by calling the ToStateful extension method, passing the state object in. You can then execute ordinary operations on the values while retaining the state:

var statefulInt = 3.ToStateful("This is the state");
var processedStatefulInt = statefulInt
    .Execute(i => ++i)
    .Execute(i => i * 10)
    .Execute(i => i + 2);
Console.WriteLine("Value: {0}; state: {1}",
processedStatefulInt.Value, processedStatefulInt.State);

This monad differs from the identity by enriching the boxes. There is another way to give value to the monad, which is to enrich the processing. An example of that is the writer monad, which can be typically used to log the operations that are being performed by the monad. Of course, the richest monads enrich both the boxes and the processing.

That’s all for today. I hope with this you won’t have to go through the same process that I did to understand monads and that you haven’t gone into concept overload like I did.

Next time, we’ll examine some examples that you already know but we will shine the monadic light, hopefully illuminating them in a whole new way. Realizing that this pattern is actually in many places but mostly unnoticed is what will enable the truly casual “oh, yes, that’s a monad” comments.
Part 2/2 of this series can be found here:
http://weblogs.asp.net/bleroy/archive/2010/06/29/how-i-understood-monads-part-2-2-have-we-met-before.aspx

Here’s the code for this article:
http://weblogs.asp.net/blogs/bleroy/Samples/Monads.zip

The Wikipedia article on monads:
http://en.wikipedia.org/wiki/Monads_in_functional_programming

This article was invaluable for me in understanding how to express the canonical monads in C# (interesting Linq stuff in there):
http://blogs.msdn.com/b/wesdyer/archive/2008/01/11/the-marvels-of-monads.aspx

Comments

JP said:

Nice article, thank you.  A couple pieces of feedback.

You write ...

"Now this is a true to the definition Monad, including the weird naming of the methods."

I think here it would be good to explain how the methods on the monad map specifically to the metaphor of the conveyor belt and the boxes.

Also, when you write …

“That of course is seriously ugly. Note that the operation is responsible for re-boxing its result.”

How specifically is it doing that?

Thanks again!

# June 16, 2010 7:52 PM

Bertrand Le Roy said:

@JP: Unit is boxing, Value is unboxing and Bind is processing. The Identity class is the conveyor belt.

The operation is re-boxing by wrapping its result in a call to Unit: s => Identity<string>.Unit(s + " was processed by identity monad.")

# June 17, 2010 12:28 AM

Mark Rendle said:

Excellent post; very illuminating to see an explanation in my native language. Thank you.

# June 17, 2010 6:36 AM

DBJ said:

Hi BLR,

Good post. Couple of comments.

1 :: You had to resort to "stunt programming" to be able to implement concepts You are explaining. Which makes the explanation difficult to comprehend. Above examples written in Python or JavaScript would be much simpler but still would represent true usable implementation of the concept.

2 :: I personaly find much easier to explain monads, by using some simple code , for which the "pupil" is convinced it is a monad.  For example. Is the following code a 'monad', and if it is not, why is it not :

       static readonly  System.Globalization.CultureInfo cc_ = System.Globalization.CultureInfo.CurrentCulture;

       public static string format(this string argument, params object[] args)

       {

           return string.Format(cc_, argument, args);

       }

// usage:  "hello {0}".format("world")

Of course, I am glad that CallStream concept made you think "even more" ... I just hope "beer fest" is not the only way to "cool the brain overheating" ;o)

--DBJ

# June 17, 2010 6:37 AM

JD said:

Note that your state example illustrates why it's important that bind take a function from the base type to the monadic type. As written, operations on a state-enhanced value are unable to modify the state.

# June 17, 2010 3:26 PM