Parsing Monads Part 2
I learned something new recently, and it’s something that has me so excited I had to blog about it. Actually, I learned two things. I learned about a really cool functional way of writing parsers, and in the process finally learned what a monad is. It’s going to take a lot to fully blog about this, so this is going to be a series of blog posts.
- Parsing Monads Part 1
- Parsing Monads Part 2
- Parsing Monads Part 3
- more to come… stay tuned
Last time I introduced you to monads and showed you how to define them in C# with the simple identity and maybe monadic types. This time I’m going to start creating a parsing monad that will allow you to use functional composition in order to build very sophisticated text parsers. Let’s get started.
We’ll start by defining our monadic type. If we think about what it is we need to do, parse some value from some given input text, we can fairly easily come up with this for our monadic type.
public delegate T Parser<T>(string input);
This isn’t a bad start, however if you think about it a bit deeper you’ll realize that in order to compose these parsers we need them to not only return some value, but also return something to indicate the text remaining to parse. So, rather than returning T we’ll return a ParseResult<T> type that includes both the result value but also the remaining input. While we’re at it I’m also going to change the input type from string to an IInput interface. Not only will this allow us to accept input from different sources (such as a Stream) by supplying different implementations of the interface, it will also allow us to include other state information about the input stream. For now we’ll provide only a single StringInput implementation and minimal state information, but in the future the decision to use this interface will be important. So, with these changes we’ll modify our Parser monad.
public delegate ParseResult<T> Parser<T>(IInput input);
For now I’m going to gloss over IInput and ParseResult<T> in order to just focus on the monadic parser. You can see the implementation of these types in the code at the end of this post.
So, to complete our Kleisli triple for the parsing monad we need Unit and Bind operations.
public static Parser<T> Unit<T>(T value)
{
return input => new ParseResult<T>(value, input);
}
public static Parser<U> Bind<T, U>(Parser<T> parser, Func<T, Parser<U>> binder)
{
return input =>
{
var result = parser(input);
return result == null ?
null :
binder(result.Value)(result.RemainingInput);
};
}
Unit was really simple. It just returns a ParseResult<T> with the specified value and the initial input (i.e. it returns a value without consuming any input). Bind is fairly simple as well. For now we’re going to return null from any Parser<T> that fails to parse. So we first call the initial parser. If it returns null, we also return null, otherwise we use the Func<T, Parser<U>> to obtain the next parser and call it with the remaining input.
Right now this may seem way too simple, but this is actually all that’s needed to implement all the other compositional operations for our parsing needs. We really only need one more building block to get started parsing text. Unit returns a value without actually consuming or parsing any of the input. We need some way to actually consume and parse something. For this we’ll define an Item operation that will create a Parser<T> that will consume a single character from the input.
public static Parser<char> Item()
{
return input => input.IsAtEnd ?
null :
new ParseResult<char>(input.Current, input.Consume());
}
I said we only needed one more thing, but to simplify some of the code to come we’re also going to define a Zero operation. Zero will return us a Parser<T> that always fails.
public static Parser<T> Zero<T>()
{
return input => null;
}
There we have it. A parsing monad. To illustrate its use we’ll create a very simple parser that simply parses the text “ab” (an ‘a’ followed by a ‘b’). This is a very trivial and meaningless parser, but it does illustrate how we can user our parser monad to compose larger parsers.
var a = Item().Bind(c => c == 'a' ? Unit(c) : Zero<char>());
var b = Item().Bind(c => c == 'b' ? Unit(c) : Zero<char>());
var parser = a.Bind(ar => b.Bind(br => Unit(string.Format("{0},{1}", ar, br))));
Display(parser, "ab");
This will parse “ab” and display “a,b” to the console as a result. Here’s the complete code listing.
using System;
namespace Parsing
{
static class Program
{
public interface IInput
{
bool IsAtEnd { get; }
char Current { get; }
IInput Consume();
}
public class StringInput : IInput
{
private readonly string source;
private readonly int pos;
public StringInput(string source)
: this(source, 0)
{
}
private StringInput(string source, int pos)
{
this.source = source;
this.pos = pos;
}
public bool IsAtEnd
{
get { return this.pos == this.source.Length; }
}
public char Current
{
get { return this.source[this.pos]; }
}
public IInput Consume()
{
return new StringInput(this.source, this.pos + 1);
}
}
public class ParseResult<T>
{
private readonly T value;
private readonly IInput remainingInput;
public ParseResult(T value, IInput remainingInput)
{
this.value = value;
this.remainingInput = remainingInput;
}
public T Value
{
get { return this.value; }
}
public IInput RemainingInput
{
get { return this.remainingInput; }
}
public override string ToString()
{
return this.Value.ToString();
}
}
public delegate ParseResult<T> Parser<T>(IInput input);
public static Parser<T> Unit<T>(T value)
{
return input => new ParseResult<T>(value, input);
}
public static Parser<U> Bind<T, U>(
Parser<T> parser,
Func<T, Parser<U>> binder)
{
return input =>
{
var result = parser(input);
return result == null ?
null :
binder(result.Value)(result.RemainingInput);
};
}
public static Parser<T> Zero<T>()
{
return input => null;
}
public static Parser<char> Item()
{
return input => input.IsAtEnd ?
null :
new ParseResult<char>(input.Current, input.Consume());
}
static void Main(string[] args)
{
var a = Item().Bind(c => c == 'a' ? Unit(c) : Zero<char>());
var b = Item().Bind(c => c == 'b' ? Unit(c) : Zero<char>());
var parser = a.Bind(ar =>
b.Bind(br => Unit(string.Format("{0},{1}", ar, br))));
Display(parser, "ab");
Display(parser, "a");
Console.WriteLine();
Console.WriteLine("Press any key");
Console.ReadKey();
}
static void Display<T>(Parser<T> parser, string input)
{
var result = parser(new StringInput(input));
if (result != null)
{
Console.WriteLine(result);
}
else
{
Console.WriteLine("failure");
}
}
}
}
9 Comments
cheap jordan retro shoes said
If youre interested in good mens bags, then look no further than Louis Vuitton.
air jordan 28 said
A Louis Vuitton mens bag is often a good point to have.
baidu censor said
Other countries censor content and not just rogue regimes such as the Iranian mullocracy. Poor people! http://www.baidu.com
http://www.vaga-bondo.com said
People want to look as beautiful as our superstars do. Appetite suppressants are considered the best
pure green coffee extract, but that hasn't stopped the marketers from developing a multimillion-dollar market. Lose Weight NaturallyGreen tea contains EGCG epigallocatechin gallate - two antioxidant compounds that are a far cry from this.
www.detroitcreativecorridorcenter.com said
Conversely, there are certain factors that you need for weight control
a good idea to avoid buying pure green coffee bean extract 800 mg from dollar stores or discount stores.
designer-warehouse.co.za said
If you are someone who has been diagnosed with the disease and know pure green coffee bean extract reviews how difficult it is to lose it without special treatment.
tohno-sharyo.jp said
It is good to seek the advice of your dietician or doctor before you consume
green green coffee bean extract for weight loss. Without getting too
scientific, EGCG is an antioxidant such as Vitamin C. Along with
the magnolia, both Cortislim and Relacore
contain some vitamin C and E! Second is the amount of fat
intake, which means it can help you to boost your energy.
Dissolve it and add to the beauty of your body with too much food.
My.uitp.org said
Natural Xin Yi Dai and Lasmi green coffee bean extract side
effects due to concerns of serious liver injury. Ideally one should take diet pills after
proper research and feedback reviews as this will be detrimental
to your health.
referendum said
Greetings, I'm Rodger and I've recently started to get into what you're talking about. I am not sure where you’re obtaining your details, but great job nonetheless. I really need to commit some time learning and understanding more. Thanks for this: this is just what I was looking for for my goal.