Sunday, January 16, 2011

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!

17 comments:

Anonymous said...

Thanks for explaining Monads and im looking forward to more great content.

Redbeard said...

In your Div definition, is there a reason you cast the Nothing to a Maybe? I would have thought this would be automatic (since a Nothing is a Maybe).

I just want to make sure I'm not missing something important :)

Michael L Perry said...

For completeness sake, you could also implement Select:

public static Maybe<B> Select<A, B>(this Maybe<A> a, Func<A, Maybe<B>> select)
{
return a.Bind(aval => select(aval));
}


This would simplify the syntax in some scenarios. For example:

from c in GetCustomer(1) from n in c.Name.ToMaybe() select n

becomes:

from c in GetCustomer(1) select c.Name.ToMaybe()

Michael L Perry said...

What's your opinion on naming. Should the names "Bind" and "ToMaybe" be changed to better fit the specific usage? While playing with your code, I called them "IfNotNull" and "Maybe", which seemed to read better.

And finally, would you consider it bad practice to put a null check in ToMaybe, as in:
return obj == null ? (Maybe<T>)new Nothing<T>() : new Just<T>(obj);

Mike Hadlow said...

@Redbeard, The cast to Maybe is simply to keep the compiler happy (or at least intellisense). Both branches of the conditional operator (?:) have to return the same type and VS wan't able in infer that the type should be Maybe without at least one cast.

@Michael, Is that the signature for Select? It's exactly the same as Bind, so you could just rename Bind. I'm not sure I like the fact that you have to call ToMaybe again in the select clause, the nice thing about linq syntax is that it executes all the Monad extension methods for you.

But yes, it would make an interesting exercise to implement more of the linq extension methods. As for what to call them, I like Bind, because it's explicitly saying, 'this is a Monad', but really it's a personal choice.

Should ToMaybe return Nothing if the argument is null? Hmm, I'd much rather explicitly create a new Nothing, rather than call mynullval.ToMaybe(). Are you considering a scenario where you are transitioning from dealing with null values into a section of code where you are using Maybe?

Michael L Perry said...

This is a better implementation of Select that does not require the extra ToMaybe():

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

This no longer matches the Bind signature, but I'm not sure that you necessarily want it to.

Now you can call it like this:

Maybe<string> name = from c in GetCustomer(1) select c.Name;

Very clean.

And, yes, my question about detecting null in ToMaybe is to bridge the gap between null-aware code and Maybe-aware code. So if GetCustomer wasn't enlightened, it could still be called like this:

Maybe<string> name = from c in GetCustomer(1).ToMaybe() select c.Name;

Still, there's something smelly about a null appearing on the left-hand side of a dot.

nabils said...

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

In the statement above I am just selecting b which means var is of type Maybe. How would I get to the int value inside that maybe container cleanly. Would I need to cast to Just and then access the value?

Mike Hadlow said...

Hi nabils,

Yes, you need to cast result to Just first:

var just = result as Just<T>
if(just != null)
{
var actualResult = just.Value;
}

Because you are left with a result that might not have a value, you have to check for that first. If you don't like the cast, you could easily implement Maybe as a single class.

Anonymous said...

Don't you have to use "if" statement in your implementation of ToMaybe to check if value is null and return Nothing then?
Tx.
/Boris

Omar Abou Mrad said...

You say: "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"

and in the code that follows, you check justa against null.

I'm having a hard time understanding this since if i try:

String foo = null;
var result = foo.ToMaybe().Bind(...)

it will not shortcircuit since ToMaybe() creates a new Just with Value null.

Am i missing something?

Mike Hadlow said...

Hi Omar, 'justa' in the Bind function is of type Maybe<A>, the 'as' operator is effectively a 'try cast' operator, if it can cast the Maybe<A> to Just<A> then justa has a value, if it can't cast it, justa will be null. So I'm not checking if a is null, but if it can be cast as Just<A>.

I hope this makes sense.

Your code should start new Nothing<string>().Bind(...)

John Dhom said...

Good info, nice post.

I wanted implicit conversion to Maybe (mostly method returns) for convenience. Can't do that with the 'interface' implementation.

What do you think of changing maybe to an abstract base class and defining the implicit conversion there? Appears to be working for me ;)

Mike Hadlow said...

Hi John, There are many different ways of implementing Maybe in C#. I've seen several that just have a single Maybe class that decides if it's Just or Nothing based on internal state. I don't see why you shouldn't use an ABC.

John Dhom said...

Hi Mike,

Thanks. Based on your post (and Dyer's) I've also added comprehension syntax to the lokad maybe monad.

Good stuff.

/jhd

Steffen Daniel Jensen said...
This comment has been removed by the author.
Steffen Daniel Jensen said...

Particularly Maybe can be implemented nicely using a struct.

Consider the base case of the _isSome field if using the implicit public empty constructor.

public struct Maybe where T : class
{
private readonly T _value;
private readonly bool _isSome;

private Maybe(T value)
{
_isSome = value != null;
_value = value;
}

public static Maybe None()
{
return new Maybe();
}

public static Maybe Some(T val)
{
return new Maybe(val);
}

public bool TryGet(out T t)
{
if (_isSome)
{
t = _value;
return true;
}
t = null;
return false;
}
}

Sid Burn said...

That would have been a pain to write imperatively.

Well the painfull imperatively code will look something like this:

try {
var a = "Hello World!";
var b = DoSomeDivision(0);
var c = new DateTime(2010, 1, 14);
var result = a + " " + b.ToString() + " " + c.ToShortDateString();
Console.WriteLine(result);
}
catch {
Console.WriteLine("Nothing!");
}

public static int DoSomeDivision(int denominator) {
return 12 / denominator;
}