Monads in C#-7. Turning our parser into a Monad

This is the seventh 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.

Do you remember our parser delegate from part 6? If you haven’t read it yet, I’d recommend reviewing it now before reading the rest of this post.

public delegate Maybe<Tuple<T, string>> Parser<T>(string input);

Remember the pain we had to go through to combine these parsers? Let’s try a different approach by turning our parser into a Monad. Up to now we’ve just looked at turning classes or interfaces with a single type parameter into Monads, but we can do just the same with a delegate.

First let’s write a ToParser method. It’s pretty easy we just return a parser that returns our item without consuming any of the input string:

public static Parser<T> ToParser<T>(this T value)
{
    return s => new Just<Tuple<T, string>>(Tuple.Create(value, s));
}

Next we need a Bind method. This is a little harder to write, but if we ‘follow the types’ it appears relatively painlessly. Let’s think about the signature of bind, remember this is the same for any Monad:

public static Parser<B> Bind<A, B>(this Parser<A> a, Func<A, Parser<B>> func){}

Now we’ll digest the signature step by step. First let’s look at the return type: Parser<B>.  Remember Parser<B> is a function from a string to a Maybe<Tuple<B, string>>, so we need to return a lambda for that function:

public static Parser<B> Bind<A, B>(this Parser<A> a, Func<A, Parser<B>> func)
{
    return s =>
    {
        // ...
    };
}

That lambda needs to return a Maybe<Tuple<B, string>>, we can get one of those by invoking func, getting the returned Parser<B> and invoking that:

public static Parser<B> Bind<A, B>(this Parser<A> a, Func<A, Parser<B>> func)
{
    return s =>
    {
        var bParser = func( ??? );
        return bParser( ??? );
    };
}

We need an A to pass to func and we can get one of those by invoking the a parser, getting it’s return value and grabbing the A from that:

public static Parser<B> Bind<A, B>(this Parser<A> a, Func<A, Parser<B>> func)
{
    return s =>
    {
        var aMaybe = a(s);
        var aResult = aMaybe as Just<Tuple<A, string>>;
        
        // short circuit if parse fails
        if (aResult == null) return new Nothing<Tuple<B, string>>();

        var aValue = aResult.Value.Item1;

        var bParser = func(aValue);
        return bParser( ??? );
    };
}

Notice how we short circuit the parse if the a parser fails. This means that any combination of parsers will return Nothing if any one of them can’t parse its part of the input string.

Lastly we need a string value to feed to our bParser, which we can get from the a parser result:

public static Parser<B> Bind<A, B>(this Parser<A> a, Func<A, Parser<B>> func)
{
    return s =>
    {
        var aMaybe = a(s);
        var aResult = aMaybe as Just<Tuple<A, string>>;
        
        // short circuit if parse fails
        if (aResult == null) return new Nothing<Tuple<B, string>>();

        var aValue = aResult.Value.Item1;
        var sString = aResult.Value.Item2;

        var bParser = func(aValue);
        return bParser(sString);
    };
}

That’s it, we have built a Monadic parser. To use it with Linq syntax we need to write a SelectMany, but that’s a mechanical operation because we already know what it looks like, it’s exactly the same as the Ident<T> SelectMany and the Maybe<T> SelectMany that we’ve already written, except with Parser<T> substituted:

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

Now we can write our little Hello World parser in three lines of code:

var helloWorldParser =
    from hello in "Hello".Find()
    from world in "World".Find()
    select new {Hello = hello, World = world};

var result = helloWorldParser("HelloWorld");

Console.WriteLine(result.AsString(x => x.Hello));
Console.WriteLine(result.AsString(x => x.World));

// outputs 
// Hello
// World

That is a thing of beauty.

Hopefully you can start to see how Monads can let you simply build some very complex systems.

If you want to dig deeper into Monadic parsers, Nicholas Blumhardt has a very nice implementation called Sprache.

Happy Parsing!