Monads in C#-4. Linq loves Monads!

This is the fourth part of my Monad series. See the introduction for a list of all the posts.

You can find the code for this post on GitHub here.

In part 3 we met our first Monad, Identity<T>. We learnt that for something to become a Monad it had to have a type constructor (Identity<T>), and two methods, ‘Bind’ and ‘ToIdentity’.

// a function 'Bind', that allows us to compose Identity returning functions
public static Identity<B> Bind<A, B>(this Identity<A> a, Func<A, Identity<B>> func)
{
    return func(a.Value);
}

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

I also mentioned that in C# Bind has a different name, SelectMany. It’s one of the extension methods defined for IEnumerable<T>. And as you might have guessed, IEnumerable<T> is in fact a Monad. It’s the Monad poster child for C# in fact :)

So today let’s see how we can implement SelectMany for Identity<T> and free ourselves from the lambda soup we were drowning in in the last post.

Linq takes an interesting approach to Monads, it asks us to write a method that combines Bind and ToXxxx into a single method, SelectMany. SelectMany must have the following signature:

Identity<C> SelectMany<A, B, C>(this Identity<A> a, Func<A, Identity<B>> func, Func<A, B, C> select)

As you can see it looks just like Bind, except it has a third parameter, a function that takes an A and a B and returns a C. It also has a different return type, an Identity<C> instead of an Identity<B>. If your amplified type implements this method, the linq syntax ‘pre-compiler’ (not really, but it’s a good way of thinking about it) can re-write ‘for x in y’ expressions in terms of select many.

Let’s implement SelectMany as an extension method:

public static Identity<C> SelectMany<A, B, C>(this Identity<A> a, Func<A, Identity<B>> func, Func<A, B, C> select)
{
    return ???
}

Now we’ll ‘follow the types’ to work out how to write the implementation. First we know we need to return an Identity<C>. The only place we get a C from is the return value of the select function. We can change a C into an Identity<C> by using ToIdentity:

public static Identity<C> SelectMany<A, B, C>(this Identity<A> a, Func<A, Identity<B>> func, Func<A, B, C> select)
{
    return select( ??? ).ToIdentity();
}

What do we pass into select? Its first parameter is an A, we can get an A from our ‘a’ parameter by invoking its ‘Value’ method. The second parameter is a B. We can get a B from our previously defined Bind method and then invoke ‘Value’ on that as well:

public static Identity<C> SelectMany<A, B, C>(this Identity<A> a, Func<A, Identity<B>> func, Func<A, B, C> select)
{
    return select(a.Value, a.Bind(func).Value).ToIdentity();
}

Let’s expand out Bind because it’s not greatly helping us here:

public static Identity<C> SelectMany<A, B, C>(this Identity<A> a, Func<A, Identity<B>> func, Func<A, B, C> select)
{
    return select(a.Value, func(a.Value).Value).ToIdentity();
}

And viola, we have implemented SelectMany for Identity<T>.

Now remember our lambda soup example from the last post? Here it is again:

var result = 
    "Hello World!".ToIdentity().Bind(                   a => 
    7.ToIdentity().Bind(                                b =>
    (new DateTime(2010, 1, 11)).ToIdentity().Bind(      c =>
    (a + ", " + b.ToString() + ", " + c.ToShortDateString())
    .ToIdentity())));

Console.WriteLine(result.Value);

We can now rewrite it using Linq syntax like this:

var result =
    from a in "Hello World!".ToIdentity()
    from b in 7.ToIdentity()
    from c in (new DateTime(2010, 1, 11)).ToIdentity()
    select a + ", " + b.ToString() + ", " + c.ToShortDateString();

Console.WriteLine(result.Value);

Is that not much nicer? With our new insight into Linq and Monads, we can stop thinking of ‘from x in y’ as a weird attempt to write SQL in C#, but instead see it for what it really is, a kind of Monadic assignment where we assign an unamplified type on the left from an amplified type on the right.

It’s a common misconception that you can only use Linq syntax with IEnumerable<T>, this is incorrect. You can use it for Whatever<T> so long as you implement SelectMany. If you want to use other bits of linq syntax (where, let, join etc) you have to implement the appropriate matching methods, but they can all be constructed from Bind, as we’ll see a little while later.

In the next post we’ll meet our first useful Monad - The Maybe Monad.