Refactoring to monadic C#

You may have heard or read that LINQ is more than just queries, that it's actually syntax sugar for monadic code. But unless you previously used monads in another language with better, more explicit support (like Haskell or F#) you might not grok the concept of monads or how exactly monads are useful in real-world code.

No, this is not yet another monad tutorial. Instead, I'll show how a concrete function in a real-world C# project can be refactored to take advantage of a monad. But I'm not going to explain how this monad works or how it's implemented.

First, a warning: there is quite a bit of code in this post. It's simple code, but I recommend really reading it and not just skimping over it to understand what's going on.

The code we'll work with is a simple utility function that parses version ranges in NuGet, used to express dependency versions. For example, the string "2.1" indicates version 2.1. Another example: "[2.0,2.5]" is an interval between versions 2.0 and 2.5, inclusive. You can find the full specification here.

This post is not a criticism of NuGet or its code, or even imperative programming. There's nothing "wrong" here. I was just browsing NuGet's code and thought this would make a good example on how to refactor imperative code to functional, monadic style. It's a decidedly different style, but I'll leave it to you to decide if it's better or not. In my experience, shoving functional programming down programmers' throats doesn't work. People have to see and decide for themselves.

The code we'll refactor can be found here in NuGet's repository. I'll copy it here for convenience:

public static bool TryParseVersionSpec(string value, out IVersionSpec result) {
    if (value == null) {
        throw new ArgumentNullException("value");
    }

    var versionSpec = new VersionSpec();
    value = value.Trim();

    // First, try to parse it as a plain version string 
    Version version;
    if (Version.TryParse(value, out version)) {
        // A plain version is treated as an inclusive minimum range 
        result = new VersionSpec {
            MinVersion = version,
            IsMinInclusive = true
        };

        return true;
    }

    // It's not a plain version, so it must be using the bracket arithmetic range syntax

    result = null;

    // Fail early if the string is too short to be valid 
    if (value.Length < 3) {
        return false;
    }

    // The first character must be [ ot ( 
    switch (value.First()) {
        case '[':
            versionSpec.IsMinInclusive = true;
            break;
        case '(':
            versionSpec.IsMinInclusive = false;
            break;
        default:
            return false;
    }

    // The last character must be ] ot ) 
    switch (value.Last()) {
        case ']':
            versionSpec.IsMaxInclusive = true;
            break;
        case ')':
            versionSpec.IsMaxInclusive = false;
            break;
        default:
            return false;
    }

    // Get rid of the two brackets 
    value = value.Substring(1, value.Length - 2);

    // Split by comma, and make sure we don't get more than two pieces 
    string[] parts = value.Split(',');
    if (parts.Length > 2) {
        return false;
    }

    // If there is only one piece, we use it for both min and max 
    string minVersionString = parts[0];
    string maxVersionString = (parts.Length == 2) ? parts[1] : parts[0];

    // Only parse the min version if it's non-empty 
    if (!String.IsNullOrWhiteSpace(minVersionString)) {
        if (!Version.TryParse(minVersionString, out version)) {
            return false;
        }
        versionSpec.MinVersion = version;
    }

    // Same deal for max 
    if (!String.IsNullOrWhiteSpace(maxVersionString)) {
        if (!Version.TryParse(maxVersionString, out version)) {
            return false;
        }
        versionSpec.MaxVersion = version;
    }

    // Successful parse! 
    result = versionSpec;
    return true;
}

Going functional

Let's start refactoring. The first thing we should note is that by functional standards this is a pretty monolithical function. In functional programming we tend to write very little functions instead, sometimes even trivial, and avoiding state as much as possible, then compose them to achieve the end result.

In this case, we can identify several functions:

• Check input length
• Parse interval start inclusiveness
• Parse interval end inclusiveness
• Check interval syntax
• Parse lower bound version
• Parse upper bound version

In order to make these functions composable, we'll avoid using out parameters. We could do this by making them return a Tuple<bool,T> where the bool represents if the function was successful or not, and T is the type of the actual result. For example, we could wrap Version.TryParse like this:

Tuple<bool, Version> ParseVersion(string value) {
    Version v;
    var ok = Version.TryParse(value, out v);
    if (ok)
        return Tuple.Create(true, v);
    return Tuple.Create(false, v);
}

In fact F# does this automatically for you. But we can do better by using an option type. An option type is similar to the familiar Nullable<T> type: we can ask if it contains a value or not, and if it does have a value we can retrieve it. The difference is that an option type works for any underlying type, not just value types.

It's not hard to implement a basic option type, but F# already has a proper implementation, and if you have Visual Studio 2010 you already have F#. If you don't, get F# here. So we'll just reference FSharp.Core.dll and use F#'s option type. With a couple of extension methods to ease the syntax in C#, ParseVersion can be written as:

FSharpOption<Version> ParseVersion(string value) {
    Version v;
    var ok = Version.TryParse(value, out v);
    if (ok)
        return v.ToOption();
    return FSharpOption<Version>.None;
}

At this point you may ask why not just return null when value is not a valid version. Yes, we could do that in this particular case, but we'll see that sometimes null can be valid value to return, and then we wouldn't be able to tell an invalid value from a valid null value.

Using FSharpOption<T> the signature of the main function:

bool TryParseVersionSpec(string value, out IVersionSpec result)

becomes:

FSharpOption<IVersionSpec> ParseVersionSpec(string value)

Now let's start implementing one by one the functions in the bulleted list above. I'll write them as local Funcs, but you could just as well make them regular methods if you prefer.

var checkLength = L.F((string val) => val.Length < 3 ? FSharpOption<Unit>.None : FSharpOption.SomeUnit);

L.F() is a little function to help C# with type inference of Funcs, as described here, so checkLength is of type Func<string, FSharpOption<Unit>>

Unit is like void. It means "nothing", but unlike void, it's an actual type we can use, so we can write FSharpOption<Unit> (C# won't allow FSharpOption<Void>). FSharpOption<Unit> has only two possible values: None and Some(null) (represented by SomeUnit)

The rest of the functions look like this:

var minInclusive = L.F((string val) => {
    var c = val.First();
    if (c == '[')
        return true.ToOption();
    if (c == '(')
        return false.ToOption();
    return FSharpOption<bool>.None;
});
var maxInclusive = L.F((string val) => {
    var c = val.Last();
    if (c == ']')
        return true.ToOption();
    if (c == ')')
        return false.ToOption();
    return FSharpOption<bool>.None;
});
var checkParts = L.F((string[] parts) => parts.Length > 2 ? FSharpOption<Unit>.None : FSharpOption.SomeUnit);
var minVersion = L.F((string[] parts) => {
    if (string.IsNullOrWhiteSpace(parts[0]))
        return FSharpOption<Version>.Some(null);
    return ParseVersion(parts[0]);
});
var maxVersion = L.F((string[] parts) =>  {
    var p = parts.Length == 2 ? parts[1] : parts[0];
    if (string.IsNullOrWhiteSpace(p))
        return FSharpOption<Version>.Some(null);
    return ParseVersion(p);
});

So far we've only defined a bunch of functions but haven't done anything with the actual input. Here's the actual processing:

var singleVersion = ParseVersion(value);
if (singleVersion.HasValue())
    return ((IVersionSpec)new VersionSpec { IsMinInclusive = true, MinVersion = singleVersion.Value }).ToOption();

if (!checkLength(value).HasValue())
    return FSharpOption<IVersionSpec>.None;
var isMin = minInclusive(value);
if (!isMin.HasValue())
    return FSharpOption<IVersionSpec>.None;
var isMax = maxInclusive(value);
if (!isMax.HasValue())
    return FSharpOption<IVersionSpec>.None;
var svalue = value.Substring(1, value.Length - 2);
var sparts = svalue.Split(',');
var min = minVersion(sparts);
if (!min.HasValue())
    return FSharpOption<IVersionSpec>.None;
var max = maxVersion(sparts);
if (!max.HasValue())
    return FSharpOption<IVersionSpec>.None;
return ((IVersionSpec)new VersionSpec { IsMinInclusive = isMin.Value, MinVersion = min.Value, IsMaxInclusive = isMax.Value, MaxVersion = max.Value }).ToOption();

What have we really achieved so far, compared to the original imperative solution? We encapsulated all parsing and checking into neat little referentially transparent functions. There's no mutability or side-effects here, whereas in the imperative code the VersionSpec instance gets mutated along the entire function. It might not seem like much in this little example, but once you become reference-transparency aware (and you apply this awareness) your code gets easier to understand and compose, just as Wes describes.

Since VersionSpec is no longer mutated, we could also just ditch IVersionSpec (the readonly interface to VersionSpec) and make VersionSpec truly immutable.

Further modifications and monadifications

But we still have some significant cruft left: all that if (!something.HasValue()) return FSharpOption<IVersionSpec>.None isn't very pretty. Here's where the monad comes in, and another reason to use option types. FSharp.Core.dll already defines a monad around FSharpOption (called the Maybe monad). All we have to do is wrap the functions that implement this into the extension methods that C# requires to enable LINQ syntax sugar (or just implement it directly, it's pretty trivial code), and then we can write that last code block as:

var singleVersion =
    from v in ParseVersion(value)
    select (IVersionSpec)new VersionSpec { IsMinInclusive = true, MinVersion = v };

var versionRange = L.F(() => {
    return from x in checkLength(value)
           from isMin in minInclusive(value)
           from isMax in maxInclusive(value)
           let val = value.Substring(1, value.Length - 2)
           let parts = val.Split(',')
           from y in checkParts(parts)
           from min in minVersion(parts)
           from max in maxVersion(parts)
           select (IVersionSpec)new VersionSpec { IsMinInclusive = isMin, MinVersion = min, IsMaxInclusive = isMax, MaxVersion = max };
});

return singleVersion.OrElse(versionRange)();

By now you're probably thinking "I could have done something similar!". Indeed, you could have invented monads, and you probably have, except that maybe you didn't know you were doing monads so you couldn't take full advantage of the power of this abstraction.

If I got you interested in functional programming and monads, my job here is done. I hope this refactoring was detailed enough to compare the functional and imperative ways of thinking, and also to demystify monads. If you want to learn more about monads, use a language with better syntactic support, like Haskell or F#. Monads don't really require any special language support (you can write and use monads in Java, Python, Ruby, Perl, ...), but without syntax sugar they are harder to read and write, at least until you're comfortable with them. In F# this syntax sugar is called computation expressions, in Haskell do notation.

Desugaring the LINQ expression above into extension methods is a good way to understand what the LINQ syntax does under the covers and see how the functions are composed.

By the way, this is not the only way to apply monads to parsing. We could have used monadic parser combinators, which can provide automatic parsing error messages, but it's a whole different approach from the get-go, not so easily refactorable from existing imperative code. If you're interested, there are some implementations of parser combinators in C#, check out Sprache or RxParsers.

All code shown here (plus the parts I didn't show) is available on github.

All code copied from NuGet is copyrighted by the Outercurve Foundation, licensed under the Apache License, Version 2.0