I have moved!

I've moved my blog
CLICK HERE

Thursday, 11 December 2008

The Maybe Monad in C#

The Maybe Monad is extremely simple. It represents a value that might be there, but might not, and also provides a neat way of working with such values.

This Haskell-related page makes it pretty clear:

The Maybe monad embodies the strategy of combining a chain of computations that may each return Nothing by ending the chain early if any step produces Nothing as output. It is useful when a computation entails a sequence of steps that depend on one another, and in which some steps may fail to return a value.

Change Nothing to null and we're talking in C#. Furthermore, it advises:

If you ever find yourself writing code like this:

case ... of
  Nothing -> Nothing
  Just x  -> case ... of
               Nothing -> Nothing
               Just y  -> ...

you should consider using the monadic properties of Maybe to improve the code.

Again, translating into C#, we're talking about code like this:

public static Role GetRole(string urlString)
{
    string[] url = SplitUrl(urlString);
 
    RecordCompany company = Music.GetCompany("4ad.com");
    if (company != null)
    {
        Band band = company.GetBand("Pixies");
        if (band != null)
        {
            Member member = band.GetMember("David");
            if (member != null)
                return member.Role;
        }
    }
 
    return null;
}

As we navigate our way through a graph of objects, we repeatedly have to check whether the road is blocked by a null. When a situation like this occurs inside our nice tidy Linq expression, it makes it look really ugly.

But how can we improve on this in C#?

Firstly, we should be clear that a reference variable (such as company in the above code) is ideally suited for representing the Maybe monad. Any class type can be "stored" in a reference, otherwise that reference has the special value null. So don't be misled by the example on this page; it's correct (it's a great article) but it might make you think that we need to define a special new class to make a monad. In this case, as long as we're referring to class types (rather than unboxed value types), we don't need to.

What we're observing is that reference types already have one of the operations required by a monad: a Unit function. By simply assigning a new object to a reference variable, you are storing that object in a location that might have been null before you assigned to it, and may become null again later on. So assignment to the reference variable is the Unit function for our monad; it's built into the language.

That's all very well, but what are we actually trying to achieve? Going by the Haskell description, it's as if we'd like to be able to casually write a chunk of code like this:

RecordCompany company = Music.GetCompany("4ad.com");
Band band = company.GetBand("Pixies");
Member member = band.GetMember("David");
return member.Role;

If any of those operations returned null, then the return value of the whole thing would be null. But of course we don't always want C# to apply that rule, and how would the compiler figure out when to stop treating a chain of operations in this special way?

What we're missing from our monad is a Bind function:

public static TOut IfNotNull<TIn, TOut>(
    this TIn v, Func<TIn, TOut> f) where TIn : class 
                                   where TOut: class
{
    if (v == null)
        return null;
 
    return f(v);
}

The type parameters in this generic function constrain us to dealing with class types, so what we have here is an extension method that applies to any reference variable (weird distinction: it makes more sense to think of extension methods applying to the reference variable than to the object stored in the variable, because it's perfectly okay to call an extension method on a null reference variable).

This extension method takes a function that "transitions" from one object to another. They don't have to be the same type. To see the point of all this, let's see how our ugly code looks if we rewrite it:

return Music.GetCompany("4ad.com")
            .IfNotNull(company => company.GetBand("Pixies"))
            .IfNotNull(band => band.GetMember("David"))
            .IfNotNull(member => member.Role);

Now it's all just one expression! Cool!

(If you're wondering why is this important, there are lots of reasons, but here's one to start you off. The original version of the code was a sequence of statements, so it couldn't be represented by an expression tree, whereas the new version can be.)

So why is IfNotNull a good Bind function? It's not immediately obvious that it is, because a Bind function talks to its caller in terms of values wrapped in the monad, but deals in "naked" values with the function passed to it. But IfNotNull uses ordinary reference variables in both situations.

This is because there is a feature missing from C#. It ought to be possible to somehow tag a reference variable to say that it is definitely not null.

Response to comment from Marcel:

The : (colon) operator sounds good, but I'd argue that it's a little inflexible. It's a member access operator, like an alternative to the . (dot) so it works for the example I've given here. But what if the way I'd like to transition to the next object in the chain is by passing the current object as a parameter to some function? For example, look up the next object in a Dictionary with TryGetValue, using the current object as a key. With IfNotNull, the non-null object is given a named reference so I can do whatever I want with it.

As for verbosity, what I'd really like here is the ability to write what might be called extension operators, something Microsoft has considered but unfortunately isn't planning to implement anytime soon. These are like a cross between extension methods and operator overloads. This SO question pretty much covers the idea.

If that was possible, we could change IfNotNull to a binary operator such as | (pipe), allowing us to pipe values between lambdas like this:

return Music.GetCompany("4ad.com")
        | company => company.GetBand("Pixies")
        | band => band.GetMember("David")
        | member => member.Role;

I think that would be just about perfect.

6 comments:

Marcel said...

Interesting idea with IfNotNull... it might be helpful in some cases, but it's still too verbose compared with the ":" operator in Chrome (aka Delphi), which is a dot operator that returns null if the left part is null.

Also, you have a mistake here:

if (member != null)
return null;

return member.Role;

Daniel Earwicker said...

Thanks, I'll fix that mistake. I guess that proves my point - it's worth capturing a common repeating pattern because otherwise you can get it wrong sometimes. So it's good that I screwed up!

abby, the hacker chick blog said...

Neat idea, thanks for pointing me to this.

I'd still prefer that we just update our code to never return nulls. But, of course, when you're dealing with existing apps with thousands of lines of code that isn't always realistic so this is a nice alternative that doesn't require creating extra classes.

Now... if only Java would get add extension methods!

Rafael said...

What about the "??" operator?

Daniel Earwicker said...

The ?? operator only evaluates its right side if the left side is null. That's kind of the opposite of what is needed here. We want to evaluate the right side only if the left side is NOT null. And for safety, we want to bind the left side's value to a name only if it is not null, so guaranteeing that the name is bound to a non-null value.

ImaginaryDevelopment said...

There's a project with working functionality for deep nulls http://maybe.codeplex.com