The Nomadic Monad or: How I Learned to Stop Worrying and Love the Burrito (Part 2)

This is the second in a series of posts about monads (part 1, part 3). I happen to be a .NET developer, so I use C# in my examples, but the concept should apply to any language that has first-class functions. Code for the series is at github.

We left off with the definition of a monad. Let's review:

• Formally, a monad consists of a type constructor M and two operations, bind and return.
• The operations must fulfill several properties to allow the correct composition of monadic functions (i.e. functions that use values from the monad as their arguments or return value).
• In most contexts, a value of type M a can be thought of as an action that returns a value of type a.
• The return operation takes a value from a plain type a and puts it into a monadic container of type M a.
• The bind operation chains a monadic value of type M a with a function of type a → M b to create a monadic value of type M b, effectively creating an action that chooses the next action based on the results of previous actions.

Let's begin by addressing the first bullet point.

Formally, a monad consists of a type constructor M and two operations, bind and return.

As I understand it, a type constructor in .NET is analogous to a generic type. And with that little bit of information, we can start writing code. Let's start our project by creating a generic type, Monad<T>.

public class Monad<T>
{
    
}

github commit

With that, we've satisfied the first half of the first bullet point. We still need to define bind and return, but, since the fourth and fifth bullet points expand on each function, let's declare the first bullet point complete (that was easy!).

Let's move on to the third bullet point (I know I'm skipping around here):

In most contexts, a value of type M a can be thought of as an action that returns a value of type a.

I may be taking some liberties with the formal definition, but this screams "PROPERTY!" to me. So let's add a read-only property, Value, of type T, backed by a readonly field of the same type. And let's provide a single constructor whose parameter is of type T. We want to force people to do the right thing - always provide the monad with a value, and never (ever!) change the its value. Our monad follows the spirit of functional programming - it is immutable.

public class Monad<T>
{
    private readonly T _value;

    public Monad(T value)
    {
        _value = value;
    }

    public T Value
    {
        get { return _value; }
    }
}

github commit

As you might expect, usage of our class is very simple, as it does nearly nothing.

var m = new Monad<int>(128);
Console.WriteLine("The value of m is {0}.", m.Value);

github commit

As boring as the code is - the declaration of class Monad<T> and its usage - we have actually done something quite interesting here. If you think about it, just by having a generic type and a constructor, it fulfills the fourth bullet point:

The return operation takes a value from a plain type a and puts it into a monadic container of type M a.

We took a value, 128, and wrapped it in our class, Monad<int>. Again, we've taken some liberties with the formal definition. Instead of a actual return function, we have a constructor. I don't think it's too much of a stretch.

As little as our class does, I'm not exactly happy with it. More specifically, I'm not happy with its usage. If we already have an value that we want to wrap in our monad, why should we have to explicitly provide the generic type argument in the constructor? Why can't C# just figure it out? In short, that's just how constructors work in C#. And you'll just have to get used to it. But we can do better. We can provide a nice, easy-to-use workaround: an extension method.

public static Monad<T> ToMonad<T>(this T value)
{
    return new Monad<T>(value);
}

github commit

It makes creating an instance of our class much easier on the eyes:

var m = 128.ToMonad();
Console.WriteLine("The value of m is {0}.", m.Value);

github commit

That about wraps it up for this post. We have satisfied over half (2 2/3 by my count) of the five conditions for a monad. We have a generic class. It can wrap any value of any type. And it exposes its value as a read-only property. But we don't have a monad yet. So what's left? The bind method, and the ability to chain monadic functions. Stay tuned, things are about to get interesting.

The Nomadic Monad or: How I Learned to Stop Worrying and Love the Burrito (Part 1)

This is the first in a series of posts about monads (part 2, part 3). I happen to be a .NET developer, so I'll use C# in my examples, but the concept should apply to any language that has first-class functions.

So why should I care about monads? Aren't they only found in those weird academic languages (like Haskell) that nobody actually uses in production code? Actually, no. If you're a .NET developer like me, you've already been using monads. For almost 5 years.

I first became aware of the existence of the concept of monads after attending Kevin Hazard's CodeMash 2011 talk, What the Math Geeks Don't Want You to Know about F#. Somewhere amid the concepts of pattern matching, closures, and discriminated unions, he mentioned monads. What he said was something the line of, "...then there are monads - I'm not going to get into them because this is an intro-level talk." This caught my attention, and, since I had never heard of monads, I wrote a single word - monad - in my notebook. And forgot about it as soon as I got home. Several months later, somebody mentioned monads in a tweet. I thought to myself, "Hmmm, haven't I heard that word before?" Then I forgot about it again. Several months after that, I came across it again on Twitter. This time, I got fed up with myself - there was a concept out there that I was completely ignorant of. It was time to educate myself. Thus, my quest began.

So what is a monad? And what do they have to do with burritos? First, and least importantly, burritos. If you spend any non-trivial amount of time googling monads, you will undoubtedly come across someone comparing them to burritos. Go ahead, google "monad" "burrito" - I get 847,000 results. Interesting, but not really relevant to what a monad is. For that, let's go the source of all knowledge, Wikipedia. I've taken the liberty of bulletizing its definition of a monad:

• Formally, a monad consists of a type constructor M and two operations, bind and return.
• The operations must fulfill several properties to allow the correct composition of monadic functions (i.e. functions that use values from the monad as their arguments or return value).
• In most contexts, a value of type M a can be thought of as an action that returns a value of type a.
• The return operation takes a value from a plain type a and puts it into a monadic container of type M a.
• The bind operation chains a monadic value of type M a with a function of type a → M b to create a monadic value of type M b, effectively creating an action that chooses the next action based on the results of previous actions.

Wait, what?! This doesn't exactly make sense at first. But have no fear, it will all come together. Beginning with the next post, I'll begin dissecting each bullet point. Trust me - it'll all make sense by the end.

Generic Producer Consumer Class in C#

Over the years, I implemented the Producer/Consumer pattern numerous times. Today, I had a need to implement it. Again. In the spirit of DRY, I decided to write it once and for all.

I began thinking about the requirements of a Producer/Consumer object. It had to be generic, so that it would be type safe. Users of the object needed to be able to specify the action that would be executed upon consumption. And I wanted an Enqueue method, which would be the entry point for producers. Here's my starting point:

public class ProducerConsumer<T>
{
    public ProducerConsumer(Action<T> consumerAction) { /* snip */ }

    public void Enqueue(T item) { /* snip */ }
}

Producers will use the Enqueue method. But I only want to allow one producer to enqueue at a time, so I'm going to need to introduce an object that I'll use to lock with. I'm also going to need a Queue to hold items.

public class ProducerConsumer<T>
{
    private readonly Queue<T> queue = new Queue<T>();

    private readonly object queueLocker = new object();

    /* snip */

    public void Enqueue(T item)
    {
        lock (this.queueLocker)
        {
            this.queue.Enqueue(item);
        }
    }
}

I'm going to have to think about how to consume the items. I'll want to do this on a separate thread, so I'll set this up in the constructor. The thread's method should be an infinite loop - it will dequeue items and hand them to the consumer action. I'll also need to ensure that only one thread is adding to or removing from the queue at a time - I'll do this by locking our queueLocker when I dequeue.

public class ProducerConsumer<T>
{
    /* snip */

    private readonly Action<T> consumerAction;

    public ProducerConsumer(Action<T> consumerAction)
    {
        this.consumerAction = consumerAction;
        new Thread(this.ConsumeItems) { IsBackground = true }.Start();
    }

    /* snip */

    private void ConsumeItems()
    {
        while (true)
        {
            T nextItem;

            lock (this.queueLocker)
            {
                nextItem = this.queue.Dequeue();
            }

            this.consumerAction(nextItem);
        }
    }
}

We have a problem here. What if there are no items in the queue? I'll need to check that before dequeuing. And if there are no items in the queue, I'll need to block until there are some items. So the Enqueue method will need to signal when an item is enqueued. I'll use an AutoResetEvent for this.

public class ProducerConsumer<T>
{
    private readonly AutoResetEvent queueWaitHandle = new AutoResetEvent(false);

    /* snip */

    public void Enqueue(T item)
    {
        lock (this.queueLocker)
        {
            this.queue.Enqueue(item);

            // After enqueuing the item, signal the consumer thread.
            this.queueWaitHandle.Set();
        }
    }

    private void ConsumeItems()
    {
        while (true)
        {
            T nextItem = default(T);

            // Later on, we'll need to know whether there was an item in the queue.
            bool doesItemExist;

            lock (this.queueLocker)
            {
                doesItemExist = this.queue.Count > 0;
                if (doesItemExist)
                {
                    nextItem = this.queue.Dequeue();
                }
            }

            if (doesItemExist)
            {
                // If there was an item in the queue, process it...
                this.consumerAction(nextItem);
            }
            else
            {
                // ...otherwise, wait for the an item to be queued up.
                this.queueWaitHandle.WaitOne();
            }
        }
    }
}

That's everything! Now, to put it together:

public class ProducerConsumer<T>
{
    private readonly Queue<T> queue = new Queue<T>();

    private readonly object queueLocker = new object();

    private readonly AutoResetEvent queueWaitHandle = new AutoResetEvent(false);

    private readonly Action<T> consumerAction;

    public ProducerConsumer(Action<T> consumerAction)
    {
        if (consumerAction == null)
        {
            throw new ArgumentNullException("consumerAction");
        }

        this.consumerAction = consumerAction;
        new Thread(this.ConsumeItems) { IsBackground = true }.Start();
    }

    public void Enqueue(T item)
    {
        lock (this.queueLocker)
        {
            this.queue.Enqueue(item);

            // After enqueuing the item, signal the consumer thread.
            this.queueWaitHandle.Set();
        }
    }

    private void ConsumeItems()
    {
        while (true)
        {
            T nextItem = default(T);

            // Later on, we'll need to know whether there was an item in the queue.
            bool doesItemExist;

            lock (this.queueLocker)
            {
                doesItemExist = this.queue.Count > 0;
                if (doesItemExist)
                {
                    nextItem = this.queue.Dequeue();
                }
            }

            if (doesItemExist)
            {
                // If there was an item in the queue, process it...
                this.consumerAction(nextItem);
            }
            else
            {
                // ...otherwise, wait for the an item to be queued up.
                this.queueWaitHandle.WaitOne();
            }
        }
    }
}

To use it, instantiate a ProducerConsumer, passing in the action you want to be performed when an item is consumed. Then, just start enqueuing items.

void Main()
{
    var producerConsumer = new ProducerConsumer<int>(i => Console.WriteLine(i));
    
    Random random = new Random();
    
    var t1 = new Thread(() =>
    {
        for (int i = 0; i < 100; i++)
        {
            producerConsumer.Enqueue(i);
            Thread.Sleep(random.Next(0, 5));
        }
    });
    
    var t2 = new Thread(() =>
    {
        for (int i = 0; i > -100; i--)
        {
            producerConsumer.Enqueue(i);
            Thread.Sleep(random.Next(0, 5));
        }
    });
    
    t1.Start();
    t2.Start();
    
    t1.Join();
    t2.Join();
    
    Thread.Sleep(50);
}

What I've got here is a very basic implementation. The download allows the user to start and stop the consumer thread, along with options concerning what to do when it is stopped. It also gives the user the ability to clear the queue.

Visual Studio Code Kata Project Template

I just attended CodeMash, and I was really impressed by the pre-compiler all-day session "Software Craftsmanship" by Steve Smith (@ardalis) and Brendan Enrick (@brendoneus). During the session, we did several coding katas. The process for each kata was the same: start by writing a single test, then, as simply as possible, make the test pass. For example, don't do any logic, just return the expected result for the test. Then write another test, and, again, as simply as possible, make it (and the other one) pass. Continue until all use cases have corresponding tests, and all tests pass. This was probably my favorite session at CodeMash: I've known what TDD was in an abstract way, but until now, I didn't "get" it. Kudos to Steve and Branden.

However, there was one thing that slightly annoyed me during this session: when we started a new kata, I first had to create a new project/solution in Visual Studio (a class library), then delete Class1.cs, then add a reference to NUnit, then add a new class (the one that performs the kata), then add another class (the test class), and finally, decorate the test class with [TestFixture]. After all of this, I was ready to start.

I am far too lazy to go through all of these steps for each kata. So I created a Visual Studio project template to handle these routine, boring steps for me.

This was my first attempt at creating a VS project templat, so there was some fumbling around. I googled around and found these two MSDN articles: How to: Create Project Templates and Template Parameters. These two articles got me most of the way there.

After creating a tedious kata project as described above, I used Visual Studio's Export Template (File > Export Template...). After extracting the resulting .zip file, I hand modified the two .cs files, the .vstemplate, and the .csproj file so that the name of the project would be used for the kata and kata test classes. I then re-zipped the files and copied the .zip to the Visual Studio templates directory (located at C:\Users\<UserName>\Documents\Visual Studio 2010\Templates\ProjectTemplates for VS 2010 on Windows 7).

That's it! Now, when I get the urge to do a code kata, I can get started in seconds instead of minutes.

Kata Template.zip

EDIT: I've made the template version-agnostic for NUnit (it had been looking for a specific version of NUnit). This change should make usable for any version of NUnit. However, this will probably cause problems for those who have multiple versions of NUnit installed. In that case, unzip the template and edit KataProject.csproj. Change the NUnit reference to point to the version that you need. Rezip the files and put it in the ProjectTemplates directory and you should be good to go.

XML Serializable Immutable Objects and Lists

In my current project, I'm using a client/server architecture, where, among other things, the client tells the server what its configuration should be. Because multiple clients can change the server's configuration, I found it necessary to maintain the history of all configurations that have been applied to the server. I modeled the workflow after Subversion, where clients have the ability to update and commit (but no branching or merging). In order to keep things simple, I decided to store the history as a flat file - an XML serialization of the classes that represent the history. This file looks something like this:

<History>
  <Version>
    <VersionInfo Number="1" Timestamp="2010-02-11 13:38:04" />
    <Commit>
      <User>MyComputerName\MyUsername</User>
      <Name>Brian</Name>
      <Notes>Initial commit.</Notes>
    </Commit>
    <Configuration>
      <Something>Initial Value</Something>
    </Configuration>
  </Version>
  <Version>
    <VersionInfo Number="2" Timestamp="2010-02-11 14:16:52" />
    <Commit>
      <User>MyComputerName\MyUsername</User>
      <Name>Brian</Name>
      <Notes>Changed something.</Notes>
    </Commit>
    <Configuration>
      <Something>Changed Value</Something>
    </Configuration>
  </Version>
</History>

The original version of these classes look as you would expect (versions were stored in a generic list). The client would serialize a Commit object and a changed Configuration object and send them to the server. The server would create a Version object, give it a VersionInfo object with a Number and a Timestamp, add it to the History, then save it to disk. The client would then update its history.

This would have been fine and dandy if it weren't for my paranoia. I feared that some future developer would modify the history after it was committed. This completely violates the idea of a history. So I set about devising a way to prevent that. What I needed were mostly-immutable objects - objects, whose properties could be set only once.

What I came up with was a pair of generic classes: Immutable<T> and ImmutableList<T>.

public class Immutable<T>
{
    private bool isSet;
    private T value;
 
    public T Value
    {
        get
        {
            return this.value;
        }
        set
        {
            if (isSet)
            {
                throw new InvalidOperationException();
            }
 
            this.value = value;
            isSet = true;
        }
    }
}
 
public class ImmutableList<T> : IList<T>
{
    private readonly List<T> list = new List<T>();
 
    public void Add(T item)
    {
        this.list.Add(item);
    }
 
    public void Clear()
    {
        throw new InvalidOperationException();
    }
 
    public bool Remove(T item)
    {
        throw new InvalidOperationException();
    }
 
    public void Insert(int index, T item)
    {
        this.list.Insert(index, item);
    }
 
    public void RemoveAt(int index)
    {
        throw new InvalidOperationException();
    }
 
    public T this[int index]
    {
        get
        {
            return this.list[index];
        }
        set
        {
            throw new InvalidOperationException();
        }
    }
 
    <snip>
}

Immutable<T> only lets you set its value once, and ImmutableList<T> only lets you add or insert items - never clearing, removing, or replacing. If you attempt to violate these rules, a big, nasty InvalidOperationException is thrown.

public class History
{
    private readonly Immutable<ImmutableList<Version>> versions = new Immutable<ImmutableList<Version>>();
 
    public ImmutableList<Version> Versions
    {
        get
        {
            return versions.Value;
        }
        set
        {
            versions.Value = value;
        }
    }
}

As you can see, History can only have its Versions property set once, which is all you need when XML deserializing. You'll also only be able to add to a Version - never remove or replace.

public class Version
{
    private readonly Immutable<VersionInfo> versionInfo = new Immutable<VersionInfo>();
 
    private readonly Immutable<Commit> commit = new Immutable<Commit>();
 
    private readonly Immutable<Config> configuration = new Immutable<Config>();
 
    public VersionInfo VersionInfo
    {
        get
        {
            return this.versionInfo.Value;
        }
        set
        {
            this.versionInfo.Value = value;
        }
    }
 
    public Commit Commit
    {
        get
        {
            return this.commit.Value;
        }
        set
        {
            this.commit.Value = value;
        }
    }
 
    public Configuration Configuration
    {
        get
        {
            return this.configuration.Value;
        }
        set
        {
            this.configuration.Value = value;
        }
    }
}

One downside to this is I can't use my beloved automatic properties for dumb data object like these. But, I suppose they're not quite as dumb now, are they?