Thursday, January 13, 2011

Monads in C#-4. Linq loves Monads!

This is the fourth part of my Monad series. See the introduction for a list of all the posts.

You can find the code for this post on GitHub here.

In part 3 we met our first Monad, Identity<T>. We learnt that for something to become a Monad it had to have a type constructor (Identity<T>), and two methods, ‘Bind’ and ‘ToIdentity’.

// a function 'Bind', that allows us to compose Identity returning functions
public static Identity<B> Bind<A, B>(this Identity<A> a, Func<A, Identity<B>> func)
{
return func(a.Value);
}

public static Identity<T> ToIdentity<T>(this T value)
{
return new Identity<T>(value);
}

I also mentioned that in C# Bind has a different name, SelectMany. It’s one of the extension methods defined for IEnumerable<T>. And as you might have guessed, IEnumerable<T> is in fact a Monad. It’s the Monad poster child for C# in fact :)

So today let’s see how we can implement SelectMany for Identity<T> and free ourselves from the lambda soup we were drowning in in the last post.

Linq takes an interesting approach to Monads, it asks us to write a method that combines Bind and ToXxxx into a single method, SelectMany. SelectMany must have the following signature:

Identity<C> SelectMany<A, B, C>(this Identity<A> a, Func<A, Identity<B>> func, Func<A, B, C> select)

As you can see it looks just like Bind, except it has a third parameter, a function that takes an A and a B and returns a C. It also has a different return type, an Identity<C> instead of an Identity<B>. If your amplified type implements this method, the linq syntax ‘pre-compiler’ (not really, but it’s a good way of thinking about it) can re-write ‘for x in y’ expressions in terms of select many.

Let’s implement SelectMany as an extension method:

public static Identity<C> SelectMany<A, B, C>(this Identity<A> a, Func<A, Identity<B>> func, Func<A, B, C> select)
{
return ???
}

Now we’ll ‘follow the types’ to work out how to write the implementation. First we know we need to return an Identity<C>. The only place we get a C from is the return value of the select function. We can change a C into an Identity<C> by using ToIdentity:

public static Identity<C> SelectMany<A, B, C>(this Identity<A> a, Func<A, Identity<B>> func, Func<A, B, C> select)
{
return select( ??? ).ToIdentity();
}

What do we pass into select? Its first parameter is an A, we can get an A from our ‘a’ parameter by invoking its ‘Value’ method. The second parameter is a B. We can get a B from our previously defined Bind method and then invoke ‘Value’ on that as well:

public static Identity<C> SelectMany<A, B, C>(this Identity<A> a, Func<A, Identity<B>> func, Func<A, B, C> select)
{
return select(a.Value, a.Bind(func).Value).ToIdentity();
}

Let’s expand out Bind because it’s not greatly helping us here:

public static Identity<C> SelectMany<A, B, C>(this Identity<A> a, Func<A, Identity<B>> func, Func<A, B, C> select)
{
return select(a.Value, func(a.Value).Value).ToIdentity();
}

And viola, we have implemented SelectMany for Identity<T>.

Now remember our lambda soup example from the last post? Here it is again:

var result = 
"Hello World!".ToIdentity().Bind( a =>
7.ToIdentity().Bind( b =>
(new DateTime(2010, 1, 11)).ToIdentity().Bind( c =>
(a + ", " + b.ToString() + ", " + c.ToShortDateString())
.ToIdentity())));

Console.WriteLine(result.Value);

We can now rewrite it using Linq syntax like this:

var result =
from a in "Hello World!".ToIdentity()
from b in 7.ToIdentity()
from c in (new DateTime(2010, 1, 11)).ToIdentity()
select a + ", " + b.ToString() + ", " + c.ToShortDateString();

Console.WriteLine(result.Value);

Is that not much nicer? With our new insight into Linq and Monads, we can stop thinking of ‘from x in y’ as a weird attempt to write SQL in C#, but instead see it for what it really is, a kind of Monadic assignment where we assign an unamplified type on the left from an amplified type on the right.

It’s a common misconception that you can only use Linq syntax with IEnumerable<T>, this is incorrect. You can use it for Whatever<T> so long as you implement SelectMany. If you want to use other bits of linq syntax (where, let, join etc) you have to implement the appropriate matching methods, but they can all be constructed from Bind, as we’ll see a little while later.

In the next post we’ll meet our first useful Monad - The Maybe Monad.

5 comments:

fschwiet said...

This blog series is shaping up to be something special, good work.

Yoann Esnaud said...

Hi Mike,

I left you a note on twitter yesterday regarding monads and my ineptitude to understand the benefits.

First, these are great posts (and the ones before too).

I can understand the implementation of monads and how they would work. however what I am not seeing is in which situations would you implement your own?

Regards,

Yoann.

Mike Hadlow said...

Hi Yoann,

Thanks for asking the question again here.

I've found Monads a difficult abstraction to think intuitively about, and until you have that intuitive understanding, it's always going to be hard to spot a situation where they are going to be useful. But with that insight, all kinds of situations appear. I've noticed that in the Haskell community, almost everything seems to end up as a Monad, and they often stack Monads to make new ones. So for the example of the community that's been playing with Monads for longest there is ample evidence that they have a wide range of applications.

But anyway, I'm not answering your question. One example would be where you repeat a control structure frequently in your code. The simple Maybe Monad shows how you can work with 'nullable' types, wrapping up all the actual null checking. The Maybe Monad also shows how they can work as a 'short-circuit', allowing you to break out of a series of operations if a certain condition appears. That's an awkward thing to code imperatively. Monads can also be used to pass on state orthogonally to the domain logic of your program, a good example of this would be a Monadic Parser. CPS style code can also be nicely wrapped with a Monad, the F# Async Monad is an excellent example of this. The list goes on.

I'm still at the foothills of understanding these functional abstractions myself, but I've found that looking at existing examples is a very good way of getting some insight. I plan to examine a number of different Monads here, starting with the Maybe Monad in the next couple of days, so hopefully that will help too.

user1 said...

LINQ loves monads, but it's not the only language construct that loves monads - there is also another, which maybe loves them even more:

"There is actually one more way for writing some monadic computations in C# using the recently added query syntax. The syntax is very limited compared to the encoding using iterators, but may be suitable for some computations." [Thomas Petricek, Encoding monadic computations in C# using iterators]

Iterators are older than LINQ, but now we have of course async/await. We can "await anything" already:
public IEnumerable Numbers()
{
return EnumeratorMonad.Build(async Yield =>
{
await Yield(11);
await Yield(22);
await Yield(33);
});
}
(full source code is available on StackOverflow)

But in C#7 arbitrary async return types are going to be possible, which would allow constructs like this:

"Running this C# code:

static void Main()
{
var nullable = DoNullableThings();
Console.WriteLine(nullable.HasValue);
Console.ReadLine();
}

static async NullableTaskLike DoNullableThings()
{
var val1 = await GetValue();
var val2 = await GetNoValue();

var val3 = await GetValue();
var val4 = await GetValue();
var val5 = await GetValue();
var val6 = await GetValue();
var val7 = await GetValue();
return val7;
}

static async NullableTaskLike GetValue()
{
Console.WriteLine("Returning 1");
return 1;
}

static async NullableTaskLike GetNoValue()
{
Console.WriteLine("Returning none");
return await new NullableTaskLike();
}

produces this output:

Returning 1
Returning none
False

(...) Using this, we can leverage the compiler to write code that acts like do-notation in Haskell. This implementation of Nullable is akin to Haskell's Maybe type."

Source: "Quick and dirty monadic Nullable implementation for the C# Tasklike language proposal" on GitHub

DWright said...

Deeply helpful series, thank you. Could you provide any more info on the fact that Linq works with Whatever, not just IEnumerable? Obviously, you are right and it does, as your code helpfully demonstrates!