Thursday, August 23, 2012

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

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

In the last post, we covered over half of the items in Wikipedia's formal 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.

Let's break down the requirement for the Bind function. It

...chains a monadic value of type M a...
That says to me that we need to have an instance method in our monad. Or, we could use an extension method to achieve the same result. I prefer to use an extension method, so that's what we'll do. Let's create an extension method:

public static ??? Bind<T>(this Monad<T> monad, ???)

Not a bad start. Let's skip to the return type. We'll need

...to create a monadic value of type M b...
That doesn't look so hard. We've already used our Monad<T> class in place of M a. But, since we already used T we won't be able to use it again. But, since it's a good idea to use standard C# naming conventions when we're writing C# code (when in Rome...), our generic type should at least start with the letter 'T'. How about TResult, since it is the result of our Bind method?

public static Monad<TResult> Bind<T, TResult>(
    this Monad<T> monad,
    ???)

But what of the second parameter? It looks like it needs we need to be connecting

...with a function of type a ? M b...
Why, if I didn't know better, I'd say that looks an awful like a lambda expression (spoiler alert: it is). And we already know what a and M b mean to us: T and Monad<TResult>. It would be great if we were able to pass in a lambda expression that takes an T and returns a Monad<TResult>. But what is a lambda expression? Just a convenient way of creating a function. Hmmmm, function. I know - why don't we take a Func<T, Monad<TResult>> as our parameter type! We just put the function in functional. So what does our extension method look like now?

public static Monad<TResult> Bind<T, TResult>(
    this Monad<T> monad,
    Func<T, Monad<TResult>> resultSelector)

Finally, we'll need to fill in the body. Our requirements state that we need to take our Monad<T> and transform it into a Monad<TResult> by using a Func<T, TResult>. That function needs a <T> argument passed to it. Haven't we seen an instance of <T> before? Of course - in the Value property of our Monad<T> class. With that, I think we have got enough information to fill out our Bind method:

public static Monad<TResult> Bind<T, TResult>(
    this Monad<T> monad,
    Func<T, Monad<TResult>> resultSelector)
{
    return resultSelector(monad.Value);
}

I think we're really getting somewhere now! How would we use our spiffy new Bind function? I'd think that we would use it something like this:

Monad<int> m1 = 128.ToMonad();
Monad<Type> m2 = m1.Bind(x => x.GetType().ToMonad());
Console.WriteLine(
    "The type of the original monad is: {0}.",
    m2.Value);

We've taken a Monad of type int, and bound it to a Monad of type Type by calling Bind and passing in a lambda expression that takes a T and returns a Monad<Type>. There's one thing I don't like about this usage though: the call to ToMonad(). I'd prefer it if our Bind function had, as its parameter, a Func<T, TResult>. But I also want to meet the requirement for being a monad. Why don't we create an overload of Bind to do just that? I'd like our existing Bind method to remain the source of truth, so we'll have our new one call it.

public static Monad<TResult> Bind<T, TResult>(
    this Monad<T> monad,
    Func<T, TResult> resultSelector)
{
    return monad.Bind(m => resultSelector(m).ToMonad());
}

This is getting a little funky. We're doing a few things here: 1) we're passing a new lambda expression to the other Bind method; 2) in the body of the new lambda expression, we're executing the function that was passed in; and 3) we're turning the result of into a Monad<TResult> by calling our extension method, ToMonad. We're not actually executing the passed-in function, we're passing it into another function that we pass to the other Bind method. Clear as mud, right? So why go through all this trouble? To me, it expresses intent better, and I think this makes it worth it. We can use it like this:

Monad<int> m1 = 128.ToMonad();
Monad<Type> m2 = m1.Bind(x => x.GetType());

Console.WriteLine(
    "The type of the original monad is: {0}.",
    m2.Value);

This is all well and good, but it seems kind of tedious to have to create a new variable each time we call Bind. Didn't the requirement mention something about chaining? As in method chaining? Why don't we try that?

var m =
    128.ToMonad()
    .Bind(x => x.GetType())
    .Bind(x => new string(x.ToString().Reverse().ToArray()));

Console.WriteLine(
    "The backwards string representation of "
    + "the type of the original monad is: {0}.",
    m.Value);

We're taking the number 128 wrapping it in Monad<int>, binding it to a Monad<Type> with a function that takes any value and returns its type, and binding that to a Monad<string> with a function that takes any value and returns its string representation backwards. Pretty cool, huh?

We're headed for the home stretch now. It's time to address the final bullet point:

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).
It seems to me like we're already doing this. We're composing a monad from a series of monadic functions. But perhaps we can make our intent more clear - calling Bind over and over again doesn't exactly look pretty. What if we extracted the calls to Bind into methods that expressed their intent more clearly? How about using some extensions methods? Something like this?

public static Monad<Type> ToType<T>(this Monad<T> monad)
{
    return monad.Bind(m => m.GetType());
}

public static Monad<string> ToReversedString<T>(
    this Monad<T> monad)
{
    return monad.Bind(m =>
        new string(m.ToString().Reverse().ToArray()));
}

Now we can replace our Bind statements:

var m =
    128.ToMonad()
    .ToType()
    .ToReversedString();

Console.WriteLine(
    "The backwards string representation of "
    + "the type of the original monad is: {0}.",
    m.Value);

That about wraps it up for today. Next time, we'll discuss the three monadic laws.(Hopefully we follow them!)

Sunday, July 1, 2012

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.

Friday, June 29, 2012

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.