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!)