My ASP.NET skills may be a bit rusty, but that’s not stopping me from working on a side project in ASP.NET MVC. While it has made significant strides in the 4.0 release, code like this demonstrates that ASP.NET still has a long way to go to improve testability.

public class AccountController : Controller
{
    ITwitterService _twitter;

    //constructor dependency injection
    public AccountController(ITwitterService twitterService)
    {
        _twitter = twitterService;
    }

    public ActionResult SignInWithTwitter()
    {
        //check for GetRedirectUrl and sets cookie
        Response.SetCookie(new HttpCookie("RedirectUrl",
            FormsAuthentication.GetRedirectUrl(string.Empty, false)));

        //build callback URL
        var callback_url_builder = new UriBuilder()
        {
            Host = Request.ServerVariables["SERVER_NAME"],
            Port = int.Parse(Request.ServerVariables["SERVER_PORT"]),
            Path = Url.Action("SignInWithTwitterCallback"),
        };

        //Helper funciton to invoke Twitter’s oauth/request_token REST endpoint
        var url = _twitter.GetRequestToken(callback_url_builder.ToString());

        //redirect to the URL returned from _twitter.GetRequestToken
        return Redirect(url);
    }

This code has several dependencies that are hard or impossible to test: FormsAuthentication, Request, Response and Url. Testing this code is a real pain in the ass. When I originally wrote this code, I bit the bullet and wrote said the PITA test code. But I couldn’t help thinking there must be a better way.

Clearly, in order to be able to test this code, I need to introduce points of abstraction that can be filled with mock implementations during unit test runs. I already have one such abstraction point – the _twitter field of AccountController is an ITwitterService instance that gets injected on construction. I have a “real” implementation that gets injected in production and a mock implementation that I manually inject in my tests.

In order to test the code above, I’ll need to wrap the calls into the untestable objects in some sort of injectable dependency that can be mocked out for tests.

C# being an OO language, typically we think of Dependency Injection in terms interfaces and classes. However, wrapping the untestables in interfaces and then implementing those interfaces is a lot of additional code. Instead of one injected dependency, the code above would need five injected dependencies. Furthermore, since objects are both the unit of dependency injection as well as the typical way the URL namespace is segmented, I also have to consider the dependencies of any other action methods on AccountController. That gets ugly fast.

Instead of thinking in terms of objects and interfaces, I wondered what DI might look like if we thought about dependencies in terms of delegates and anonymous lambdas? You know, functional programming?  It might look something like this:

Func<string> @GetRedirectUrl;
Action<HttpCookie> @SetCookie;
Func<NameValueCollection> @ServerVariables;
Func<string, string> @ActionUrl;

public ActionResult SignInWithTwitter()
{
    //check for GetRedirectUrl and sets cookie
    @SetCookie(new HttpCookie("RedirectUrl", @GetRedirectUrl()));

    //build callback URL
    var callback_url_builder = new UriBuilder
    {
        Host = @ServerVariables()["SERVER_NAME"],
        Port = int.Parse(@ServerVariables()["SERVER_PORT"]),
        Path = @ActionUrl("SignInWithTwitterCallback"),
    };

    //Call twitter.GetRequestToken
    var url = _twitter.GetRequestToken(callback_url_builder.ToString());

    //redirect to the URL returned from Twitter.GetRequestToken
    return Redirect(url);
}

(Note, I’m using the @ symbol as a prefix for injected delegates, in order to make it easier to pick them out of the code. Looks kinda odd, but it is valid C#.)

This is better in that it’s actually testable without requiring a metric crapload of test code to mock the ASP.NET intrinsics. However, this approach don’t have enough information to inject dependencies based on type alone. For example, the @GetRedirectUrl is a Func<string> (i.e. a function that takes no parameters and returns a string). However, FormsAuth FormsCookieName and DefaultUrl properties would also be represented as Func<string> delegates as well.

Most DI containers have support resolving dependencies by name and type, but that makes declaring dependencies much tougher and more fragile in my opinion. If you’re going to limit yourself to static typing write compiled code, you might as well let the compiler do as much heavy lifting as possible, right?

Also, wrapping each untestable method call in a delegate has made the explosion of dependencies problem even worse. SignInWithTwitter declares four new dependencies, the callback action (not shown) adds seven new delegate dependencies and the sign out action adds one, making a total of thirteen dependencies! (including the original ITwitterService). However, none of these twelve delegate dependencies are shared across action methods. So they aren’t really controller dependencies so much as action dependencies. So what if I went ahead and declared them as action dependencies directly?

public Func<ActionResult> SignInWithTwitter(
    Func<string> @GetRedirectUrl,
    Action<HttpCookie> @SetCookie,
    Func<NameValueCollection> @ServerVariables,
    Func<string, string> @ActionUrl)
{
    return () =>
    {
        //check for GetRedirectUrl and sets cookie
        SetCookie(new HttpCookie("RedirectUrl", GetRedirectUrl()));

        //build callback URL
        var callback_url_builder = new UriBuilder
        {
            Host = ServerVariables()["SERVER_NAME"],
            Port = int.Parse(ServerVariables()["SERVER_PORT"]),
            Path = ActionUrl("LogOnCallback"),
        };

        //Call twitter.GetRequestToken
        var url = _twitter.GetRequestToken(
            callback_url_builder.ToString());

        //redirect to the URL returned from Twitter.GetRequestToken
        return Redirect(url);
    };
}

SignInWithTwitter is now a function that takes four delegates and returns a delegate – we’re really down the functional programming rabbit hole now!

The benefit of this approach is that I can make tradeoffs as I see fit between controller and action dependencies. ITwitterService is still injected via the AccountController constructor since it is used by two of the three Account actions. Dependencies only used by a single action can be scoped to that specific action so that only tests for a given action method have to mock them out. And testing this is a breeze compared to having to mock out intrinsic ASP.NET objects.

[Fact]
public void returns_redirect_result_with_getrequesttoken_url()
{
    //inject controller dependencies
    var twitter = new Mock<Models.ITwitterService>(MockBehavior.Strict);
    twitter.Setup(t => t.GetRequestToken(It.IsAny<string>()))
        .Returns("http://fake.twittertest.local");
    var controller = new AccountController(twitter.Object);

    //inject action dependencies
    Func<string> @getRedirectUrl = () => "/fake/redirect/url";
    Action<HttpCookie> @setCookie = c => { };
    Func<NameValueCollection> @serverVariables =
        () => new NameValueCollection()
        {
            {"SERVER_NAME", "testapp.local"},
            {"SERVER_PORT", "8888"}
        };
    Func<string, string> @actionUrl = url => "/fake/url/action/result";
    var action = controller.SignInWithTwitter(@getRedirectUrl,
        @setCookie, @serverVariables, @actionUrl);

    //Invoke action
    var result = action();

    //Validate
    var redirectResult = Assert.IsType<RedirectResult>(result);
    Assert.Equal("http://fake.twittertest.local", redirectResult.Url);
}

I could make this code even smaller by moving the action dependencies out to be test fixture class fields. Assuming you write multiple tests for each action method, this allows you to reuse the mock action delegates across multiple methods. If I want to do negative testing, I can easily define test-specific delegates that throw exceptions or return unexpected values.

Of course, the down side to this approach is that MVC has no idea what to do with an action method that returns Func<ActionResult>. I could envision support for this pattern in MVC someday, though we’d need a robust solution to the type+name dependency issue I described above. For now, I will simply wrap the delegate injection version (aka the testable version) of the action in a non-testable but MVC compatible version that injects the right delegate dependencies.

public ActionResult SignInWithTwitter()
{
    return SignInWithTwitter(
        () => FormsAuthentication.GetRedirectUrl(string.Empty, false),
        Response.SetCookie,
        () => Request.ServerVariables,
        Url.Action)();
}

Since I’m using the untestable intrinsics, I can’t write any tests for this method. However, it’s nearly declarative because the anonymous delegates I’m injecting are closing over the untestable intrinsics. Personally, I’m willing to make the tradeoff of having an declarative yet untestable wrapper action method in order to get the delegate injected easy-to-test version of SignInWithTwitter that has the real implementation.

Barry Kelly thinks that “programmers would understand monads better if they were described as a design pattern”. I agree 100% and would love to see a monad design pattern written out using p&p’s pattern form. The one thing I would note on this is that certain language constructs can make working with certain design patterns easier. For example, C# obviously has great language level support for the Iterator design pattern. Once you’ve got language level support, it doesn’t really feel like a design pattern anymore, it feels like a language feature. I mean, given that you can write OO code in a language like C, does that mean technically OO is a “design pattern”. I don’t think so.

A commenter named atp warned me not to “fall into the newbie trap of thinking that monads are about sequencing operations. They aren’t. A large number of monads (for example, Reader) are commutative and do not enforce any sort of statement ordering.” Fair enough. For example, you switch the order of some LINQ operators and still end up with the same result. If you switch Where and Select, you should end up with the same output (assuming the where clause isn’t invalidated by the select projection). But from a C#/F# perspective, I don’t really care about monads for enforcing order anyway – the language has that natively. I care much more about the context flow aspect of monads, which it sounds like atp thinks we should be focused on anyway. Works for me.

Finally, Yuri K. pointed out that we aren’t really stuck with the nested lambda expression syntax in C#. In Luke Hoban’s Monadic Parser Combinators using C# 3.0 post, he implements a Where, Select and SelectMany extension method for his Parser delegate type, which allows him to plug into C#’s query comprehension syntax. He’s 100% correct and I considered including this fact in my post. However, the mapping between query comprehension and the Bind and Result functions is a little murky, so I skipped it.

For C# query comprehensions, basically SelectMany does double duty, not only binding the parser and the parser generating function (which Luke called ‘selector’), but also taking the two parse values and calling to a projector function and returning the projection return value in a Result. By implementing SelectMany, you can rewrite the TwoValues parser like this:

static Parser<string> QueryTwoItems()  
{  
    return from v1 in Item()
           from v2 in Item()
           select string.Format("{0}{1}", v1, v2);  
}

which looks pretty much identical to the F# monadic syntax version. Luke also implements Where, which I have in my F# parser library as Satisfy. Where takes a parser and only returns the parser result if the provided boolean predicate returns true. Select is a projection, similar to SelectMany but only used with a single parser. I have a couple of specific projectors in my F# library (Ignore which tosses the parse result and Listify which turns a single result into a single item list) but I haven’t had any need for a generic projector like Select. I’m assuming Luke only implemented Select to make the query comprehension work when you don’t have multiple from statements.

In the last post, I built out a basic parser monad in C#. While the approach worked OK, the syntax is still a little foreign to your typical .NET programmer, what with it’s nested anonymous functions and all. Now, I’m going to translate that code to F# and take a look at the special monadic syntax F# supports that makes using monads as easy any sequential code.

First, let’s translate our Parser delegate, Bind, Result and Item functions over to F#. Just for kicks, let’s also port over the final version of TwoItems too.

type Parser<'input, 'result> = 'input-> ('result * 'input) option

// the Bind function, defined as a custom operator
let (>>=) p f : Parser<'i,'r> =  
    fun input ->
        match p input with
        | Some(value, input) -> (f value) input
        | None -> None

let Result v : Parser<'i,'r> = fun input -> Some(v, input)

let Item : Parser<string, char> =  
    fun input ->
        if string.IsNullOrEmpty(input)  
            then None
            else Some(input.[0], input.Substring(1))

let BestTwoItems =  
    Item >>= (fun v1 ->  
    Item >>= (fun v2 ->  
    Result (sprintf "%c%c" v1 v2)))

First, we start with the declaration of the Parser type. Unlike C#, F# has built in support for tuples, so I didn’t bother to define a Result type (just the Result function). A Parser is declared to be a function that takes in some generic input type and returns an optional tuple pairing the result with the remaining input to be parsed. As I’ve blogged before, F#’s option type is kinda like C#’s Nullable type, so a parser that returns None is considered to have failed to parse the input.

Next up is are the monad functions Bind and Result. The only significant change from the C# version is that I used the custom operator >>= for the Bind function. So instead of calling Item().Bind(some\_function), we can call Item \>\>= some\_function. F# functions aren’t attached to a type like C# extension methods are, so this is the only way to get the more readable infix notation. I’m using >>= as the bind operator because that’s the operator Haskell uses for their monad function. Other than the custom operator name, Bind and Result work identically to their C# counterparts. Note, I explicitly specified the return type of Bind, Result and Item, but I didn’t have to. F# can infer the types of all the parameters from usage just fine. I added the type specifications for the reader, in case you’re not familiar with F#’s syntax.

Likewise, Item is identical to the C# version including using strings as the parse input, except for than the F# syntax. Typically, in a real parsing app you would use an intrinsic list of chars instead of strings, since F#s list is a much more efficient data structure than strings for operations that strip characters off the head of the list (like parsers are wont to do). However, I wanted to make this code as similar to the previous code, so I stuck with strings.

Finally, we have BestTwoItems. Again, syntax aside, it’s exactly like it’s C# cousin though I did use the slightly more compact sprintf function instead of string.Format. Again, while BestTwoItems it works well, it uses the same nested anonymous function syntax from the C# version. Maybe I shouldn’t have called it “BestTwoItems”!

However, in F# it’s possible to define a custom syntax for your monad that let’s you write the function this way:

let VeryBestTwoItems =
    parse {
        let! v1 = Item
        let! v2 = Item
        return sprintf "%c%c" v1 v2 }

With this monadic syntax, we’ve now completely eliminated not only the Parser delegate and the input string, but also the nested anonymous functions needed by the Bind function, making the code appear completely sequential.

The secret to making this work is the parse monad object. It the code above, the word parse almost feels like a language keyword, but it’s not. It’s actually an instance of an parse monad object with a specific signature. F# knows how to take the syntax above and combine it with the parse monad object to produce the right code. Here’s the parse monad:

type ParseMonad() =
    member w.Delay(f) = fun input -> f () input  
    member w.Return(v) = Result v  
    member w.Bind(p, f) = p >>= f

let parse = ParseMonad()

As you can see, there’s an obvious direct correlation of Result and Bind functions we defined last time and the Return and Bind methods in the ParseMonad. The only thing we haven’t seen before is the Delay method. Monads are one of of F#’s many delayed expressions. F# wraps the entire monad in a call to Delay to ensure the monad isn’t executed prematurely.

As per the F# grammar spec, there are several other functions you can define on your monad if you so choose. My “real” parser monad also implements Zero and Combine. Zero returns a parser that unconditionally fails. By defining Zero on my monad object, I can write ifs without elses, the parser monad will implicitly inject Zero clause as your else statement. Combine combines results (I know, a shocker!). I use it as a prioritized choice. In other words, when you Combine two parsers, you only call the second parser if calling the first parsers fails. Prioritized Choice is used very often in PEGs, which is why I chose to define it this way.

F# monadic syntax also support For, Let, While, Using, TryFinally and TryWith. Frankly, I haven’t spent much time thinking about scenarios where you’d use these other syntax elements. The only one that’s obvious to me is Using for deterministic finalization, which you could see using anywhere you access IDispoasble objects. Here’s hoping the F# folks document in detail how to use this powerful syntax.

So that’s it for basic monads in F#. I’ve gotten some great comments (and one less than great comments) as I’ve written this series. In my last post on monads (in this series at least) I’ll repost some of those comments as well as provide some concluding thoughts.

(If you disregarded my advice and read the previous version of this post, please note I rewrote this post significantly so you’ll probably want to read it again.)

In the last post, we looked at how LINQ is a monad and how IEnumerable is a pseudo-functional construct. However, C#’s intrinsic collection support – aka foreach and yield return – really obscure how you might go about building your own monad. So for this post, we’re going to take a look at a parsing monad instead. Just as LINQ broke the big problem of queries into a collection of standard query operators that were composable, we want to take the same approach for parsers.

Note, I’m going to stick with C# for now, and get into F# monads in my next post. Quick shout out to Luke Hoban and Brian McNamara, from whom I stole obtained some of the code below.

Quick refresher: I’ve described a monad as a sequence of computations with a context flow. Since C# has explicit sequencing, we want to focus on the context flow. For LINQ, the context was IEnumerable. For parsers, we could define an similar IParser interface like this:

class Tuple<T1, T2>
{
    public readonly T1 Item1;
    public readonly T2 Item2;
    public Tuple(T1 val1, T2 val2) { Item1 = val1; Item2 = val2; }
}

class Result<T> : Tuple<T, string>
{
    public Result(T val, string rest) : base(val, rest) { }
}

interface IParser<T>
{
    Result<T> Parse(string input);
}

The Parse function takes a string to be parsed as input and returns the parsing result which pairs the semantic value with with the remaining string input to be parsed. I’ve built out a simple generic tuple class because I know I’ll use it again later. I’ve long wished C# would support intrinsic tuples like F# does. For convenience, I’ve also created a strongly typed subclass of Tuple to represent parse results where the second item is a string, to save some typing. Since Result is a class, it can be null which means the the Parser failed to parse the input.

The problem with this approach is that unlike IEnumerable, the C# compiler has no built-in knowledge of this interface. That means there are no easy-to-use keywords like foreach and yield return that can do our heavy lifting of consuming or creating these IParser types for us. Instead, we would have to explicitly declare classes to implement the interface. As we add more and more parsers, that additional overhead of creating types would become more and more unwieldy. Instead, let’s redefine Parser as a delegate.

delegate Result<T> Parser<T>(string input);

The benefit of this approach is that you can create Parser delegates inside functions, using C#’s anonymous delegate syntax, without the overhead of creating a type. For example, here’s a function to create a simple primitive parser that strips the first character off the parse string and returns it as the parse result:

static Parser<char> Item()
{
    return input =>
        {
            return string.IsNullOrEmpty(input)
                ? null
                : new Result<char>(input[0], input.Substring(1));
        };
}

That’s a lot more convenient than building a type just to implement a single method.

Now that we have our Parser type, we need to think about how to compose Parsers so that we can flow context between them. Much as LINQ provides a collection of primitive query operators (Select, Where, OrderBy, etc), you would expect a monadic parser library to provide a collection of primitive parsers (Item, Satisfy, AnyOf, ItemEqual, etc), that you could combine into higher-order parsers along with some language specific lower-order parsers. Here’s an example from the the PEG grammar:

Primary \<- Identifier !LEFTARROW / OPEN Expression CLOSE / Literal / Class / DOT

The Primary parser depends on some high-order language specific parsers (Identifier, Expression, Literal and Class) as well as some language specific low-order tokenizer style parsers (LEFTARROW, OPEN, CLOSE and DOT) and finally some language-independent primitive parsers (the failure predicate ! and the prioritized choice operator /).

So how should we compose these various Parsers? LINQ query operators were fairly easy to compose because they all take in and return the same type (IEnumerable) so you can simply chain them together. Parsers are a little trickier because the inputs and outputs are asymmetric – i.e. they take a string, but return a Result – so simple chaining won’t work.

We could combine the parsers sequentially, taking the parse string returned from first parser and feed it into the second. Then we could combine the two parse values in a Tuple to return them (you see why I created a generic Tuple class?) resulting in a function that looks like this:

static Parser<Tuple<T1,T2>> Join<T1,T2>(this Parser<T1> p1, Parser<T2> p2)  
{  
    return input =>  
        {  
            var ret1 = p1(input);  
            if (ret1 == null)  
                return null;  

            var ret2 = p2(ret1.Item2);  
            if (ret2 == null)  
                return null;  

            return new Result<Tuple<T1,T2>>(  
                new Tuple<T1, T2>(ret1.Item1, ret2.Item1),  
                ret2.Item2);  
        };  
}

Note this is an extension method so we can call Parser1.Join(Parser2) rather than the less fluent Join(Parser1, Parser2). I was going to call this function Combine, but there’s already a static Combine method on the Delegate type that caused a conflict, so I used Join instead.

The Join approach works, but it’s a bit unwieldy to return the parsing values in a tuple. Every set of joined parsers will result in another level of tuple nesting in the Result that’s returned. That gets pretty ugly pretty fast. For example, lets say we want to create a parser that combines two instances of Item. It looks like this:

static Parser<Tuple<char, char>> TwoItems()
{
    return Item().Plus(Item());
}

That’s not so bad. But now look what happens if we combine the TwoItems parser with another instance of Item:

static Parser<Tuple<Tuple<char, char>, char>> ThreeItems()
{
    return TwoItems().Plus(Item());
}

The result is a nested tuple. Yuck. We need a better way. Enter the monadic bind. The code looks like this:

static Parser<U> Bind<T, U>(this Parser<T> p1, Func<T, Parser<U>> fun)
{
    return input =>
        {
            var ret1 = p1(input);
            if (ret1 == null)
                return null;

            var p2 = fun(ret1.Item1);
            if (p2 == null)
                return null;

            return p2(ret1.Item2);
        };
}

Like the Join function above, Bind starts by calling the first parser function, returning null if the parse fails. However, instead of calling to the second parser directly, it calls to the provided function that generates the second parser. This function acts as a closure, packaging up the parse value from the first parser for later processing. Finally, Bind calls to the generated second parser, feeding in the remaining text from the first parser result.

This approach allows you to inject code that combines the parsing values however we like rather than always pairing them up in a tuple. Here’s a version of TwoItems that binds a call to Item with a custom function that calls Item again and returns the two characters as a string rather than a tuple:

static Parser<string> BetterTwoItems()
{
    return Item().Bind<char, string>(
        val =>  
        {
            return input =>
            {
                var result = Item()(input);
                return new Result<string>(
                    string.Format("{0}{1}", val, result.Item1),
                    result.Item2);
            };
        });
}

It’s kinda strange to see a lambda expression that returns a lambda expression in C#, but that’s what this code does. The first lambda expression (val =>) defines the custom function, the second lambda expression (input =>) defines the Parser delegate. Val is the parse value from calling Item() the first time – ret1.Item1 in the Bind function above. Input is the remainder of the parse string – ret1.Item2 from the Bind function.

Unfortunately, while this approach avoids nested tuples for parse values, we’ve had to give up quite a bit of simplicity. The original TwoItems method was a single line of code. BetterTwoItems is significantly more complex. Furthermore, the double lambda expression syntax confuses C#’s type inference, forcing you to explicitly specify the generic types on the Bind method. Luckily there’s a better way to write this. However, let’s start by rewriting the function like this:

static Parser<string> SlightlyBetterTwoItems()
{
    return Item().Bind(
        v1 => Item().Bind<char, string>(
            v2 =>
            {
                return input =>
                {
                    return new Result<string>(
                        string.Format("{0}{1}", v1, v2),
                        input);
                };
            }));
}

SlightlyBetterTwoItems pulls the second call to Item out into a second Bind operation. The point of this refactoring is to make it clear that we can view this function as a call to Item, bound to a second call to Item, bound to custom function to return a Parser that returns the two parse value chars formatted as a string. You’ll notice that by eliminating the the double lambda expression on the first call to Bind, we were able to drop out the explicit generic type specification.

This version is a little clearer, but we can make it clearer yet. It turns out that wrapping up a parse value in a Parser that unconditionally returns the parse value and the parse text input in a Result is a very common operation. So let’s create a primitive function Result to wrap up a parse value in a Parser delegate and build our final version of TwoItems that uses it.

static Parser<T> Result<T>(T val)  
{  
    return input => new Result<T>(val, input);  
}  

static Parser<string> BestTwoItems()
{
    return Item().Bind(
        v1 => Item().Bind(
        v2 => Result(string.Format("{0}{1}", v1, v2))));
}

Now it’s very clear that we have a call to Item, bound to a second call to item, which is in turn bound to a call to Result. We’ve now dropped all use of double lambdas, which means C# can infer the types to each of our Bind calls implicitly. But more importantly, do you see any reference to Parser<T> delegates or input strings in this code? Only in the return type specification. Just as LINQ hides the specifics of flowing IEnumerable or enumerator objects between standard query operators, the parser monad hides the specifics of flowing Parser delegates or input strings between parse operations.

The Parser delegate plus the Bind and Result methods are all there are to our basic parser monad. Seriously, all that worry that monad “is a bit obscure and sounds a little daunting” and it’s really just two functions and a delegate type.

While this code is fairly straight forward, the whole nested lambdas expressions is fairly atypical syntax that some developers might have a hard time understanding. Unfortunately, if we’re writing our parsers in C#, we’re kinda stuck with this syntax. However, F# has a special syntax that lets you write what looks like normal sequential code, while still flowing the Parser context between parse operations exactly like the code above does. We’ll take a look at that syntax in the next post.

If you don’t come from a math or philosophy background (and I don’t) “monad” sounds like a made-up word. Of course, understanding OO’s use of terms like “class” and “object” can be hard to grok at first too. But at least those terms have some grounding in real-world concepts that non-math geeks come across. Because I couldn’t draw an analogy of monads to anything at first, it made grasping the concept of monads very hard for me.

It’s such a unfamiliar word that the F# team doesn’t like it either:

“[W]hen the designers of F# talked with the designers of Haskell about this, they agreed that the word monad is a bit obscure and sounds a little daunting and that using other names might be wise.”
[F# Workflows and Haskell Monads, Expert F#, p232]

The F# team thought about calling them workflows, but settled on computation expression. Frankly, I don’t like these names much better. Workflow is too easily confused with WF and if the term computation expression is way to generic. Isn’t everything in programming a computation expression? I think I’ll just stick with monad.

Of course, if there was a short, pithy way of describing a monad, I’m sure that’s what we’d call them. It’s a kinda complicated idea, so there’s no simple two or three word phrase that accurately describes it. “Sequential computation with context flow” is the best I could come up with. It’s a crappy description, but here’s an elegant example that most .NET programmers are probably already familiar with.

var Orders = new List<Order>()

//code to populate orders omitted

var q = Orders
    .Where(x => x.OrderDate < DateTime.Now)
    .OrderBy(x => x.OrderDate)
    .Select(x => new {ID = x.OrderID, Date = x.OrderDate})

Yes it’s true: LINQ is a monad. The two basic concepts about a monad from my description above is that it’s a) a sequence of operations and b) there’s a context that flows from operation to operation. We see both here in this simple LINQ query. I realize I’m using what looks like a LINQ to SQL query here, but for the sake of argument let’s assume that this is all happening in memory.

The query is a sequence of three operations: Where, OrderBy and Select. LINQ has a set of standard query operators that you can mix and match in whatever order you need to. Part of the monad’s job is to enforce the sequence of actions. For C#, that’s not really a big deal, since it has explicit sequencing already. However, other languages like Haskell use lazy evaluation, meaning there is no explicit order of execution. Many lazy evaluation languages use monads in areas, such as I/O, where order of execution matters.

While C# doesn’t need any help to enforce execution order, monads are very useful in the way they flow context between the operations. In the case of LINQ, all the standard query operators take an IEnumerable<T> as their first parameter and return an IEnumerable<T>. Since they have the same inputs and outputs, they can be plugged together in whatever order is required. Yet, you don’t see any reference to GetEnumerator or the enumerator objects they return in the LINQ code above. All that code is hidden inside the LINQ query operators so the LINQ developer doesn’t have to look at it.

If you squint hard enough, IEnumerable kinda looks like a functional construct. It exposes a single method (GetEnumerator) and can be passed around much the same way functional languages like F# pass around first-order functions. Furthermore, the result of calling GetEnumerator is an IEnumerator object that likewise exposes one main function (MoveNext). In other words, you can think of IEnumerable sort of like a function that returns a function that you call to iterate the collection.

So to sum up, a monad is a sequence of operations in a specific order that automatically flows context from one operation to the next. In the LINQ example, C# has built-in constructs – IEnumerable<T>, foreach and yield return – that makes the monad seem less foreign (which is why I used it as my first example!) However, as we’ll see, the concepts of sequence and context flow in a monad still hold even if we’re not using built in features of C# to implement them.