Monads in C#-6. Introducing a simple parser
This is the sixth 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.
So far we’ve learnt how to create a simple Monad, the Maybe Monad, and seen how it can help us eliminate boiler plate code by wrapping the mechanics of handling nullability in the Bind function. But as I said before, there’s no real limit to the complexity we can encapsulate in Bind and still treat our Monad as if it were a simple type. To illustrate this, I’m going to leap ahead in complexity and use the canonical Monad example, a Parser Monad. In this post I’ll introduce a simple concept of a Parser and in later posts I’ll show how we can turn it into a Monad.
I’ve ripped this example straight from Graham Hutton’s excellent Haskell textbook, Programming in Haskell.
OK, so let’s think about what a parser does. It takes some input, usually some text, and produces some desired output from it. So a CSV parser would take a text file and output rows and columns of data, preferably typed as numbers, strings and dates. In abstract terms we can think of a parser as a function that takes a string and returns some type T:
Func<string, T>It’s always easier if we can break large tasks into smaller ones, so it would be good if we could build our parser from lots of mini-parsers. Each mini-parser might only consume some characters of the string, so we really want a function that consumes a string and returns a T and and the unparsed remainder of the input string:
Func<string, Tuple<T,string>>
I’m using the new Tuple type from .NET4 here, but you could just as well NameValuePair or your own custom type.
Our parser might not get a string it understands, so we should be able to account for failure. We’ll do the simplest thing possible for now and reuse our Maybe type:
Func<string, Maybe<Tuple<T,string>>>
Now let’s create a simple parser that just consumes a particular sequence of characters, ‘Hello’:
public static Maybe<Tuple<string, string>> FindHello(string input)
{
return input.StartsWith("Hello")
? new Just<Tuple<string, string>>(Tuple.Create("Hello", input.Skip("Hello".Length).AsString()))
: (Maybe<Tuple<string, string>>)new Nothing<Tuple<string, string>>();
}
var result = Parsers.FindHello("Hello World");
var justResult = result as Just<Tuple<string,string>>;
Console.Out.WriteLine("justResult.Value.Item1 = {0}", justResult.Value.Item1);
// justResult.Value.Item1 = Hello
Console.Out.WriteLine("justResult.Value.Item2 = {0}", justResult.Value.Item2);
//justResult.Value.Item2 = World
var result2 = Parsers.FindHello("Goodbye World");
Console.Out.WriteLine("result2 = {0}", result2);
// result2 = Nothing
public delegate Maybe<Tuple<T, string>> Parser<T>(string input);
public static Parser<string> Find(this string stringToFind)
{
return s => s.StartsWith(stringToFind)
? new Just<Tuple<string, string>>(Tuple.Create(stringToFind,s.Skip(stringToFind.Length).AsString()))
: (Maybe<Tuple<string, string>>)new Nothing<Tuple<string, string>>();
}
This is a higher order function, it returns a function, our parser. Don’t loose sight of the fact that Parser<T> represents a delegate.
var helloParser = "Hello".Find();
var worldParser = "World".Find();
Let’s write a convenience extension method to turn parse results into strings:
public static string AsString<T>(this Maybe<Tuple<T,string>> parseResult, Func<T, string> unwrap)
{
var justParseResult = parseResult as Just<Tuple<T, string>>;
return (justParseResult != null)
? unwrap(justParseResult.Value.Item1)
: "Nothing";
}
Now we can use our helloParser and worldParser to parse strings:
var result = helloParser("Hello World").AsString(s => s);
Console.Out.WriteLine("result = {0}", result);
// result = Hello
var result2 = worldParser("World Hello").AsString(s => s);
Console.Out.WriteLine("result2 = {0}", result2);
// result2 = World
How could we join them together to make a parser for ‘HelloWorld’ (we won’t worry about whitespace just yet). Here’s a brute force attempt:
Parser<Tuple<string,string>> helloWorldParser = s =>
{
var helloResult = helloParser(s) as Just<Tuple<string, string>>;
if (helloResult == null) return new Nothing<Tuple<Tuple<string, string>, string>>();
var worldResult = worldParser(helloResult.Value.Item2) as Just<Tuple<string, string>>;
if (worldResult == null) return new Nothing<Tuple<Tuple<string, string>, string>>();
return new Just<Tuple<Tuple<string, string>, string>>(Tuple.Create(
Tuple.Create(helloResult.Value.Item1, worldResult.Value.Item1), worldResult.Value.Item2));
};
var result3 = helloWorldParser("HelloWorld").AsString(s => s.Item1 + " " + s.Item2);
Console.Out.WriteLine("result3 = {0}", result3);
// result3 = Hello World
Phew! that was hard work. Imagine if we were combining parsers for anything a little more complex, like our CSV parser for example. We’d have a nasty headache pretty quickly. But don’t worry, we’ll see in the next post that we can turn our parser into a Monad and combine them with sublime simplicity. Stay tuned combinator fans!
0 comments