Tales from the Evil Empire

Bertrand Le Roy's blog

News


Bertrand Le Roy

BoudinFatal's Gamercard

Tales from the Evil Empire - Blogged

Blogs I read

My other stuff

Archives

How I understood monads, part 2/2: have we met before?

(c) Bertrand Le Roy The first post in this series can be found here:
http://weblogs.asp.net/bleroy/archive/2010/06/16/how-i-understood-monads-part-1-2-sleepless-and-self-loathing-in-seattle.aspx

Last time, I tried to explain how beer and Lou helped me finally understand monads. I gave a couple of trivial examples. Hopefully now that you have this new functional hammer, everything will start looking like a nail.

So let’s have a look at a few screws this time.

Like last time, I’ll be pretty liberal with the definition of a monad as long as the spirit of monads seems to be preserved. Feel free to nitpick in the comments ;)

Oh yeah, jQuery is a monad

In jQuery, you first create a wrapped set of HTML elements and then execute operations on it, the result of which is a new wrapped set:

$(".foo")
    .filter(":odd")
    .map(function () {
        return this.id;
    });

Seems familiar? That because it is: the wrapped set is a monad. Pretty much.

The unit function of the monad, which is responsible for boxing an object into the monadic type is the $ function: $(elt) is building the wrapped set for the elt element.

The binding operation is more implicit than it’s been in previous C# examples and consists in just executing one of the built-in set operations or one of the plug-ins: the operation is specified by simply calling it. So for the monad to really take arbitrary operations there is a registration phase here (the registration of the plug-in) but what the operations themselves are doing is in the spirit of monads: they act on the underlying DOM or JavaScript types and return a new wrapped set.

Unboxing the wrapped elements is done by calling the get function.

Oh yeah, FluentPath is a couple of monads

Ah, here’s one I wrote before I even understood what a monad is (assuming that I do now). FluentPath is wrapping System.IO’s string paths and arrays of string paths into Path and PathCollection boxes. Once this is done, you can execute one of the built-in operations, the result of which is also a wrapped path or path collection. You can also execute custom operations:

var dirs = Path.Get("video")
    .GetFiles("*.avi", true)
    .Copy(p => p.Parent.Combine("backup").Combine(p.FileName))
    .ChangeExtension(p => p.Extension + ".bak")
    .Map(p => p.Up(2));

This is pretty close to jQuery (for a reason, FluentPath was inspired by jQuery).

Path.Get is wrapping the path, the operations are method calls, with or without Lambda parameters.

An example of an arbitrary or custom operation on the set can be seen in the example above: the Map call is taking each element of the path collection and going two levels up on it. The result is a new wrapped set of paths.

Unboxing is done by calling ToString on a path.

Oh yeah, Linq providers are monads

Just look at this:

var l = new[] {"foo", "bar", "baz"}
    .Select(s => "... " + s)
    .Select(s => s + " bleroy was here.");

Looks familiar? Again, it should be. We could just as well write this same example this way:

var l = from s in
            from s in new[] {"foo", "bar", "baz"}
            select "... " + s
        select s + " bleroy was here.";

See? The IEnumerable<T> interface is the box and the selects are binding the operations.

What’s interesting here is that we have a way to specify operations on an enumeration of things that is independent from the kind of thing we’re working on: an array like above, or a SQL Server table, an XML document or whatever has a Linq provider.

It’s also independent of how the operations get executed: a Linq provider abstracts away how the expression of the operation gets translated into actual operations that the underlying type can understand.

This second abstraction is where the real magic in Linq resides: when you write a where clause in Linq, the actual implementation of that clause may be SQL or a C# operation or who knows what, but how you write the expression itself doesn’t change.

And while we’re talking about expressions…

Oh yeah, Expression<T> is a monad

An expression in .NET is a representation of a function:

Expression<Func<string, string>> expr = 
    s => s + " appended some stuff.";

In this example, we are taking a Lambda and wrapping it into an expression object. The beauty of it is that this object can then be manipulated at runtime to build new expressions, which can then be unwrapped into functions and executed.

By now you should have seen where I’m going with this: boxing a Lambda is done by wrapping it into an Expression and unboxing is done by calling Compile() on the expression.

The Bind operation is less obvious and would not fit in this post but it can be done by implementing an expression tree visitor.

Oh yeah, Parallel.ForEach is a monad

The new parallel extensions in .NET 4 are quite interesting as they offer parallel computation under a familiar model.

For example, you can do this:

Parallel.ForEach(
    Directory.GetFiles("*.jpg"),
    path => {
        var bitmap = new Bitmap(path);
        bitmap.RotateFlip(RotateFlipType.RotateNoneFlipXY);
        bitmap.Save(path + ".flipped");
    });

This code will execute a rotation operation on each JPEG image in the current directory, in parallel as much as possible, which is ideal for long-running and independent operations such as image manipulation.

What really happens is that the enumeration of files returned by Directory.GetFiles is getting wrapped into a ParallelEnumerable, and then the operation is getting executed on each of the elements of the enumeration in parallel.

The boxing operation is thus represented here by the AsParallel method (which is implicitly called by Parallel.ForEach). The binding operation of the monad is Parallel.ForEach.

What we are seeing here is a monad whose only goal is to provide a different execution model for an existing operation. The value of the monad pattern is quite clear in this example: a familiar programming model is being quite naturally extended.

Oh yeah, C#4’s dynamic is a monad

Thanks to the new dynamic keyword in C#4, it is now possible to ask the C# compiler to relax compile-time type checking and instead resolve the members of some objects at runtime.

Here’s a somewhat trivial example:

dynamic foo = new {
    bar = "baz"
};
Console.WriteLine(foo.bar);

This example is rather pointless but what’s important is that what can be wrapped into a dynamic object comes in many shapes: .NET objects can be accessed this way (through reflection), but you can also wrap COM objects or pretty much anything provided that somebody wrote the code to resolve the underlying type system at runtime.

Boxing is done by assigning the object from the underlying type system to a dynamic variable like above. You can then perform any C# operations on the wrapped object and access the members of the underlying type system exactly as if it were a native .NET object.

The monad binding is implicit here. What really happens is that the operations are being delegated at runtime to the underlying type system by the dynamic object provider.

Monads everywhere

With functional programming becoming more mainstream and insidiously getting into more “classical” languages such as C# or JavaScript, it’s probably not such a big surprise that its patterns would find their way into our everyday APIs. Once you know the monad pattern, all sorts of things that you weren’t noticing before suddenly seem to jump into focus, like one of those optical illusions that at first you don’t see, and that once you see cannot be unseen.

Did you spot monads in familiar places? Let me know in comments.

Next time, I’ll look at expressing monads with CallStream, and after that I’ll make a post to answer some of the comments I got on this post and the previous one, such as “why should I care?”

Comments

DBJ said:

I can't wait for the next post ;)

# June 29, 2010 11:44 AM

Justin James said:

Parallel.ForEach() != PLINQ

PLINQ is "Parallel LINQ". Parallel.ForEach() has nothing to do with LINQ. What they have in common is that they were both part of the "Parallel Extensions" package that eventually evolved into the new parallelism stuff in .NET 4.

J.Ja

# June 29, 2010 3:21 PM

Bertrand Le Roy said:

@Justin: I stand corrected.

# June 29, 2010 3:28 PM

Chris Eargle said:

Oh yea, an object is a monad: monadic.codeplex.com.

I think we have to be a little more formal with the definition of a monad or the pattern loses its meaning.

# July 1, 2010 10:55 AM

Mauricio Scheffer said:

What's bind and unit in Parallel.ForEach() and dynamic? I don't think these are monads...

# May 15, 2011 6:24 PM

Bertrand Le Roy said:

@Mauricio: as explained above, unit for Parallel.ForEach is implicit and is the call to the AsParallel method; bind is ForEach itself. The pattern is very implicit here (its different elements float below the visible surface) but it's definitely there in spirit and implementation: put an object into a box that the monad understands, then hand that over to processing machines.

For dynamic, unit is the dynamic declaration, and bind is implicitly provided by the compiler itself once that is done. Unboxing happens when you cast back into a CLR object (if you choose to do that). Here you have arbitrary operations that can be expressed in a universal manner and applied to objects of various natures, provided they have been boxed with dynamic.

Those two are very much monads. Or I have not understood monads at all, which is entirely possible...

# May 17, 2011 5:56 PM

Bertrand Le Roy said:

Interesting quote from Eric Lippert: "LINQ was designed to bake the "monad" pattern into C#" blogs.msdn.com/.../following-the-pattern.aspx

# June 30, 2011 3:38 PM