A Sharpened View of Monads

As I waded through the functional paradise that is Haskell, there was always one concept that refused to let itself be understood. Hell, the mere mentioning of the word is enough to make my friends look away (well… that usually happens when I start talking about programming). Its name: Monads.

The reason why I was having so much difficulty was because of a couple of misconceptions, which are debunked as such:

  1. Monads are not a type of some sort – they are a sort of functional design pattern.
  2. Monads are not used solely for the purpose of IO operations.

Once I understood those points, things became a lot easier. However, the epiphany came upon realizing that the IO monad actually cannot be implemented in Haskell. As far as I know, it’s implemented by the compiler.

C# is perfectly capable of implementing most monads (including the IO monad, excluding those that involve higher order types). If used properly, it can lead to some really interesting (and readable) code. It also happens to be quite good for explaining the IO monad, which I’ll get to later on. First comes the Maybe monad.

Basic Monads (Maybe)

Monads require three things: a type, a unit function, and a binding function. I’ll be explaining these concepts through example.

The maybe monad provides a method of handling functions that may return a value. The type could easily be expressed as such:

public struct Maybe
{
	public static readonly Maybe Nothing = default(Maybe);

	private bool hasValue;
	private T value;

	public bool HasValue { get { return hasValue; } }
	public T Value
	{
		get
		{
			if (!hasValue)
				throw new InvalidOperationException();
			return value;
		}
	}

	public Maybe(T value)
	{
		this.hasValue = true;
		this.value = value;
	}
}

What use is there for this type? Take integer parsing for example. Instead of using those infernal out parameters from int.TryParse (or even worse: catching an exception from int.Parse), we could write a helper function like this:

public Maybe Parse(string value)
{
	int output;
	return int.TryParse(value, out output) ? new Maybe(output) : Maybe.Nothing;
}

That’s our type. Now the unit function. The unit function is a function that simply takes a single input and wraps it in the monadic type. In fact, we already have our unit function – the constructor (the one that takes one argument).

Lastly, there’s the binding function. This is where it gets a little tricky. This function takes a monadic type and a transformer function.

public static Maybe<span style="text-decoration: underline;"> Bind(Maybe value, Func> selector)
{
 return value.HasValue ? selector(value.Value) : Maybe<span style="text-decoration: underline;">.Nothing;
}


What use is this thing? Well, take this piece of code for example:

// Read two integers from the user and add them.
var a = Parse(Console.ReadLine());

if (a.HasValue)
{
	var b = Parse(Console.ReadLine());

	if (b.HasValue)
	{
		Console.WriteLine(a.Value + b. Value);
	}
	else
	{
		Console.WriteLine("Invalid Input.");
	}
}
else
{
	Console.WriteLine("Invalid Input.");
}

Kind of tedious isn’t it? Wouldn’t it be nice if we could wrap up all those if statements into one reusable function? Turns out we already did.

Take a good look at the bind function. What happens if Maybe<T>.Nothing is passed as the first argument? The function returns Maybe<U>.Nothing, and selector never even gets called. Now take a look at the above code. What happens if the user doesn’t type in a valid number (therefore failing the first conditional)? It goes straight to the else statement, and the second number is never asked for. Sound familiar?

That is the real purpose of the Maybe monad – to wrap up these repetitive if-else blocks into something a little nicer. Let’s rewrite this chunk using Bind now:

var result = Bind(Parse(Console.ReadLine()), a => Bind(Parse(Console.ReadLine()), b => new Maybe(a + b)));

Console.WriteLine(result.HasValue ? result.Value.ToString() : "Invalid Input.”);

The code’s much more compact now, although I’ll admit that it’s not very readable. If you turn Bind into an extension method, refactor Parse(Console.ReadLine()), break lines and indent a little, you can rework it into this:

var result = ReadInteger().Bind(
	a => ReadInteger().Bind(
	b => new Maybe(a + b)));

Console.WriteLine(result.HasValue ? result.Value.ToString() : "Invalid Input.”);

This is much better. The main point though is the use of bind. If either of the calls to ReadInteger() returns Nothing, then the Bind function will return nothing, effectively short circuiting the whole operation.

There’s one more step that could be taken to make this more readable, but I’ll get to that later.

IO

From the Maybe monad shown above, one could get the impression that monads necessarily have to hold the actual value they’re wrapping. This is not true – just take a look at the IO monad.

The IO monad is a bit of a hack – like I said, it can’t be defined in pure Haskell. How can you define imperative and stateful functions in Haskell!? You can’t!

The IO monad doesn’t hold an actual value – it holds a function that returns a value. That’s how it manages to maintain purity in Haskell – the usage of the IO monad means the composition of functions, and the functions themselves don’t change. Of course, the operations in the functions are stateful, but it’s completely isolated.

We’ll define our IO monad type simply as such:

public delegate T IO();

Stupid-simple, right? The unit function is just as simple:

public static IO Create(T value)
{
	return () => value;
}

Lastly, binding:

public static IO<span style="text-decoration: underline;"> Bind(this IO value, Func> selector)
{
 return () => selector(value());
}


The important thing to note is the total laziness of this function. It returns a lambda expression, so value isn’t evaluated at the time this function is called.

In C#, I’ll admit that the IO monad is pretty damn useless, but it makes for a good model for explaining how it works in Haskell.

Prettying Things Up

There is one monad that C# already has built in: the list monad, a.k.a. IEnumerable.

So what’s the unit function? Easy – make an array with one element (new[] { value }). What about the bind function? At this point I would like to point you towards the definition of the SelectMany extension method:

public static IEnumerable<span style="text-decoration: underline;"> SelectMany(this IEnumerable source, Func> selector) { … }


Fancy that eh? You can probably see where I’m heading now. What is SelectMany used for? Why, query expressions of course! In fact, query expressions don’t actually care if you use them for anything other than lists. As long as they have Select/SelectMany, they won’t complain one bit! Query expressions are, in fact, perfectly suited for prettying up monadic syntax.

Let’s go back to our Maybe monad. First up is the Select function. It’s a transformation function. It’s actually quite similar to bind. Remember that snipped where we added two integers? Select automatically wraps the output in the monadic type, so we don’t have to.

public static Maybe<span style="text-decoration: underline;"> Select(this Maybe value, Func selector)
{
 return value.Bind(n => new Maybe<span style="text-decoration: underline;">(selector(n)));
}


Now for SelectMany. You may think that all you have to do is rename the function, but query expressions actually use a slightly different version of the function.

public static Maybe SelectMany(
	this Maybe value,
	Func> itemSelector,
	Func resultSelector)
{
	return value.Bind(a => itemSelector(a).Select(b => resultSelector(a, b)));
}

Now the monad is fully prepped for use in query expressions. Rewriting our function from way back when…

var result =
	from a in ReadInteger()
	from b in ReadInteger()
	select a + b;

Console.WriteLine(result.HasValue ? result.Value.ToString() : “Invalid Input.”);

I should note that there’s a sort of ‘pattern’ I used for defining Select and SelectMany. That code can actually be used with other monads with very little modification.

As a final challenge, try to implement the where operator so that you can short circuit the entire computation (and return nothing) if a condition is not met, ex:

public static Maybe MaybeDivide(Maybe a, Maybe b)
{
	return
		from x in a
		from y in b
		where y != 0
		select x / y;
}

And that brings this ridiculously long post to a close. Next time, I’ll go into some of the more complex monads (continuations and state).

Until then,
YellPika

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s