Monads in C#-5. Maybe ;)

This is the fifth 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 created our first Monad, Identity<T>. It was worth starting with the simplest possible thing, so that we could focus on the Monad pattern without being distracted by detail. But working with a useless Monad might well have left you scratching your head, still wondering what the point was. So let’s create our first useful Monad, the Maybe Monad.

We’re used to the idea of nullability in C#. Technically null is a value that any reference type variable can have when it’s not pointing to an actual instance of that type. Nulls are problematic, in fact some people thing they are a mistake. They can be both a bug when we’ve forgotten to initialise a variable, and intentional when we use them to represent some state. Nulls are often used as one of the possible return values from a method when, for some reason, an instance can not be returned.

If I have methods that might return null, I should check the return value for null and execute some alternative branch. If we’ve got a whole chain of methods, any of which might return null, our intention can soon be obfuscated by all the null checks. It would be nice if we could factor these out.

So we want to do two things; first, make the fact that our method might return ‘null’ explicit, and second, factor out the null checks. The Maybe Monad lets us do both. C# has a type Nullable<T>, but it can only be used with value types, so it’s not really what we’re after. Here’s a type called ‘Maybe’, that can or cannot have a value, and its two subtypes, Nothing, which has no value, and Just, which has a value:

public interface Maybe<T>{}

public class Nothing<T> : Maybe<T>
{
    public override string ToString()
    {
        return "Nothing";
    }
}

public class Just<T> : Maybe<T>
{
    public T Value { get; private set; }
    public Just(T value)
    {
        Value = value;
    }
    public override string ToString()
    {
        return Value.ToString();
    }
}

The ToString overrides are not required, they’re just to make the output I write later a little easier. You can just as well write Maybe as a single type with a ‘HasValue’ boolean property, but I quite like this style, it feels closer to the Haskell Maybe.

To make Maybe<T> into a Monad we have to write ToMaybe and Bind methods for it. ToMaybe is simple, we just create a new ‘Just’ from our value:

public static Maybe<T> ToMaybe<T>(this T value)
{
    return new Just<T>(value);
}

Bind is more interesting. Remember, Bind is where we put our Monad’s behaviour. We want to factor null checks out of our code, so we need to write Bind so that if the initial value, a, is Nothing, we simply return a Nothing, and only if it has a value do we evaluate the second function:

public static Maybe<B> Bind<A, B>(this Maybe<A> a, Func<A, Maybe<B>> func)
{
    var justa = a as Just<A>;
    return justa == null ? 
        new Nothing<B>() : 
        func(justa.Value);
}

So the Maybe Bind acts a short circuit. In any chain of operations, if any one of them returns Nothing, the evaluation will cease and Nothing will be returned from the entire chain.

Lastly let’s implement SelectMany so that we can use linq syntax to help us out. This time we’ll implement SelectMany in terms of Bind:

public static Maybe<C> SelectMany<A, B, C>(this Maybe<A> a, Func<A, Maybe<B>> func, Func<A, B, C> select)
{
    return  a.Bind(             aval => 
            func(aval).Bind(    bval => 
            select(aval, bval).ToMaybe()));
}

Remember this, we can the same pattern for the SelectMany of any Monad once we have a Bind implementation.

Now let’s do some sums. Here’s a safe division method, its signature explicitly tells us that it might not return an int:

public static Maybe<int> Div(this int numerator, int denominator)
{
    return denominator == 0
               ? (Maybe<int>)new Nothing<int>()
               : new Just<int>(numerator/denominator);
}

Now lets chain some division operations together:

public Maybe<int> DoSomeDivision(int denominator)
{
    return from a in 12.Div(denominator)
           from b in a.Div(2)
           select b;
}

 

Look at that, no null checks anywhere to be seen, we’ve successfully factored them out. Now let’s use our DoSomeDivision method with some other types:

var result = from a in "Hello World!".ToMaybe()
             from b in DoSomeDivision(2)
             from c in (new DateTime(2010, 1, 14)).ToMaybe()
             select a + " " + b.ToString() + " " + c.ToShortDateString();

Console.WriteLine(result);

Still no null checks and we’re mixing ints, strings and DateTimes. If I run this, it will output:

Hello World! 3 14/01/2010

 

Now if we change the denominator to zero like this:

var result = from a in "Hello World!".ToMaybe()
             from b in DoSomeDivision(0)
             from c in (new DateTime(2010, 1, 14)).ToMaybe()
             select a + " " + b.ToString() + " " + c.ToShortDateString();

Console.WriteLine(result);

It outputs:

Nothing

See how the divide by zero Nothing from inside ‘DoSomeDivision’ cascaded up the stack, short circuiting all the other operations on the way? It left us with a Nothing result at the end of the chain. That would have been a pain to write imperatively. Maybe is probably the simplest Monad that is actually useful, but we can already see how it can remove a significant amount of boiler plate.

 

Next we’re going to leap ahead in sophistication and build a parser monad. The insane power we now have will soon become apparent… Mwuhahaha!