Last time on FAIC we managed to finally state the rules of the monad pattern; of course, we’ve known for some time that the key parts of the pattern are the constructor helper, which we’ve been calling CreateSimpleM<T> and the function application helper, which we’ve been calling ApplySpecialFunction<A, R>. Needless to say, these are not the standard names for these functions. [1. If they were, then I’d have been able to learn what monads were a whole lot faster. Hopefully this helped you too.]
The traditional name for the constructor function is “unit”, which I suppose makes some sense. In Haskell, a purely functional programming language that makes heavy use of monads, the unit function is called return, for reasons which are a bit tricky to explain without a background in Haskell.[2. Newcomers to Haskell are occasionally confused by the fact that return is a function, not a keyword of the language.] In C# there is no particular standard. Of the five monadic types we’ve been using as examples, there are five different ways to construct a monad instance from a simple value:
Nullable<int> nullable = new Nullable<int>(123); Task<int> task = Task.FromResult<int>(123); Lazy<int> lazy = new Lazy<int>(() => 123); OnDemand<int> onDemand = () => 123; IEnumerable<int> sequence = Enumerable.Repeat<int>(123, 1);
And frankly, that last one is a bit dodgy. I wish there was a static method on Enumerable specifically for making a one-element sequence.
The traditional name for the “function application” helper is “bind”. In Haskell the bind function is actually an infix[3. An infix operator is an operator that goes between its operands.] operator; in Haskell to apply a function f to an instance of a monad m, you’d say m >>= f. In C# the bind function is usually not provided explicitly and therefore usually does not have a name.[4. An extremely important exception to this rule is that the bind operation on the sequence monad is the Enumerable.SelectMany method. I’ll talk more on that subject in a later episode.]
“Unit” makes some sense but what on earth could “bind” mean? And what’s with that crazy Haskell syntax?
You might have noticed that the asynchronous, lazy, on-demand and sequence monads all have an interesting common property: when you apply a function to any of these monads, what you get back is an object that will perform that function in the future. Essentially, the bind function takes an immutable workflow and its subsequent step, and returns you the resulting new workflow. So m >>= f means “bind operation f onto the end of workflow m and give me the resulting new workflow”. The Haskell syntax is actually quite appropriate; you get the sense that the workflow is feeding its result into the next function.
Let’s be clear on this: the bind operation takes a workflow and a function and gives you back a new workflow that feeds the result of the original workflow into the new function when the new workflow is executed. The bind operator does not execute the workflow; it makes a new workflow out of an old one.[5. Just as in C#, making a new query out of an old query does not execute either query. This is no coincidence! One of the designers of this feature of C# 3 was also one of the designers of Haskell, Erik Meijer. LINQ queries are actually a fancy syntax for monad binding. Like I said, we’ll talk about that more in a future episode.]
How those workflows are actually executed depends on the semantics of the monad, of course. A portion of the workflow of the sequence monad is activated whenever MoveNext is called, and it executes until the next value in the sequence can be computed. The workflow of the lazy monad is activated the first time the Value property is fetched; after that, it uses the cached value. The workflow of the on-demand monad is activated by invoking the delegate. And the workflow of the asynchronous monad is activated… well, whenever the task is scheduled to execute!
That is the whole point of those particular monads: they represent a bunch of work that is to be done and the order in which to do it. By contrast, the far simpler nullable monad[6. Which, incidentally, is traditionally called the “maybe monad” in other languages because maybe there is a value, maybe there isn’t.] doesn’t represent a workflow to be performed in the future. Rather, it represents the association of extra state — a single Boolean — with a value. Computations performed on it are done so “eagerly” rather than being deferred until the future.
Next time on FAIC: I’m the special guest on the StackExchange podcast, so we’ll digress briefly. When we continue the series we’ll come up with a few ad hoc examples of “state” monads to explore this concept further.
Fabulous adventures in coding 
> I wish there was a static method on Enumerable specifically for making a one-element sequence
How about this?
http://rxx.codeplex.com/SourceControl/changeset/view/71357#1118161
IEnumerable<int> x = Scalar.Return(1);
Even easier: new int[] { 123 }
The problem with that one is that it makes a mutable sequence.
I have that as a extension function
static IEnumerable<T> ListOf1<T>(this T item) { return new T[1]{item}; } int x = 123.ListOf1();Not really a “List” but “EnumerableOf1” is too many syllables.
That’s also mutable, even though it requires a cast:
var e = (int[]) 123.ListOf1();
e[0] = 456;
Scalar is immutable – it returns true for ICollection.IsReadOnly. And as a bonus, it implements IObservable.
As Dave Sexton notes, that is mutable. It also has the downside that it is an extension method of everything. I’d prefer something like:
static IEnumerable<T> Singleton<T>(T item) { yield return item; }Eric, I’m a regular reader of this blog and I’d like to thank you for all this content. For more monads, workflow and binding craziness, I think your readers might want to check out http://fsharpforfunandprofit.com/series/computation-expressions.html. I don’t know if you’ve read it yourself, but this series also includes a very nice use of monads as “wrapper types”.
“A portion of the workflow of the sequence monad is activated whenever MoveNext is called, and it executes until the next value in the sequence can be computed.” … or until the sequence can be determined to have no more values. (The boolean returned by MoveNext identifies which of these outcomes has been reached.)
I think the error/exception Monad is another interesting example that really demonstrates the usefulness of Monads. Since .NET has exceptions built-in, their kinda moot, but if .NET didn’t already have that, you could almost implement them as a Monad, though not quite as elegantly as native exceptions.
I could imagine something similar to the Either monad being useful to separate validated and unvalidated input i.e. as a way to prove your code cannot have an sql injection or similar
I hope that before the end of your series, we will end up with ways to use the LINQ syntax to manipulate tasks, nullables and so on…
I apologize if my post is out of line given the context… But for the life of me I don’t understand the benefits we get from this extraordinary complexity. So far the series required some serious brain twisting. This is part 8 – there are more parts to follow with more brain twisting.
To me it looks like these Monads belong to academia – an interesting concept which is very hard to grasp. In practice, hard to grasp concepts increase the change for error – because half the time the programmer will not know what s/he is doing.
How do Monads help a computer programmer become more productive? How do they help a software company ship software sooner? In practice not in theory.
(I usually read all of Eric’s posts, but I tuned out during the Monad series – except to post here.)
Have you ever used Linq? Linq uses monads to help computer programmers become more productive, and to help them have fewer bugs in their programs.
You don’t need to understand monads to use it. But Erik Meijer had to understand monads to have invented it! Perhaps monads are really only required if you design libraries or APIs, but I personally almost believe every software project should have libraries and APIs with a very thin layer of actual business rules built on top of those – and understanding monads can help you define those libraries.
I haven’t used Linq, but one of my concerns about it which would seem to apply to monads in general is that they can have special-case behaviors which are many orders of magnitude better than their general-case behaviors, but I don’t see any general way to predict which situation will apply. I can imagine that for small data sets it’s nice to be able to write a query without regard for how it will actually be performed, but with a larger data set, I can’t see how one could hope to get good results without understanding the implementation details that things like Linq abstract away. It’s one thing to say “premature optimization is the root of all evil”, but if there are two subtly-different ways of writing a query, one of which will consistently take milliseconds to process and one of which could take hours, making certain to pick the former would not strike me as “premature optimization”.
I’ve used LINQ quite a bit, and I can’t say I’ve ever had this problem. In the implementations of LINQ provided by Microsoft, Linq2Sql and the Entity Framework, the data model adheres to the underlying table structures failrly closely, so the translation of the C# syntax to an SQL query is fairly straightforward. Even with more flexible ORM API that support LINQ, like NHibernate, it’s not difficult to guess how the query will come out, and you can always enable flags that will report to you the queries at runtime (or use an SQL trace to capture them). Like I said, I’ve used it quite a bit, including with large data sets, and it’s rare that I’ve had to worry about what exactly what the underlying query looks like.
It sounds as though you’re not really using Linq as an abstraction, since you are cognizant of the underlying table structures and are using such knowledge to ensure your queries match up with the things Linq can do efficiently. My concern is that I see no general way of knowing when operations can be chained to arbitrary depth without excessively increasing complexity. Suppose for example that AddOne(F) yields a function that returns F(x)+1 and SubtractOne(F) yields a function that returns F(x)-1, each pass through some unbounded loop replaces a function G with either AddOne(G) or SubtractOne(G), and the number of adds and subtracts will never differ by more than a constant. It’s unclear whether the complexity of the resulting function will bounded or unbounded; worse, it would seem entirely plausible that a seemingly-insignificant change to the program somewhere might easily turn bounded behavior into unbounded behavior. If one understands the underlying mechanisms, one may know what patterns will yield bounded versus unbounded behavior, but that having to know the underlying mechanisms reduces the value of abstraction.
I know a bit more than most on how LINQ works, perhaps. But, like I’ve said, I’ve rarely ever had to worry about it. I’d also bear in mind that LINQ isn’t so much a “Data Abstraction Layer”. The objects you get back from LINQ are little more than a strongly-typed representations of a data-row in a table. LINQ just makes it easier to read and write data to/from the database in a manner that provides intellisense and compile time type checking. Editing LINQ queries is little more likely to have unexpected impacts on performance than editing the SQL queries as strings. The mapping between LINQ operations and SQL operations are fairly one-to-one, (i.e., Where() corresponse to SQL Where, JOIN() corresponds to Join), so one’s intuition about the performance implications of SQL expressions apply just as well to LINQ operations for the most part.
Your scenario about AddOne/SubtractOne confuses me. Can you give a concrete example about how these would be used in LINQ? It seems that perhaps you think these user-written operations would somehow be translated into SQL by LINQ, but they would not. They would appear as opaque functions to the query writter. So, for instance, if the function was used inside a Where clause, it would force that part of the where clause to be evaluated locally instead of on the database server.
I never did understand why that function is called Bind, and I don’t quite understand your explanation for it either. It should be called AndThen, which has two important advantages:
(1) It’s clear what it does in at least most circumstances.
(2) It reminds me of And Then ( http://youtu.be/K7luMp6lb9M )
A clear disadvantage of AndThen is the syntax, which is particularly difficult since:
(1) AndThen must always be followed by a function
(2) A function / monad that contains AndThen in its workflow must always be followed by AndThen
This usually results in something like:
m AndThen f AndThen nop AndThen nop AndThen no_really_nop AndThen aaargh_NOP!!!
About the one-element sequence: Besides Enumerable.Singleton, I also miss Enumerable.Add(param T[]) or even just Add(T t). Singleton could thus be implemented as Enumerable.Empty().Add(t). I guess Concat could be abused for this.
Hm, brackets didn’t make it to the comment…
About the one-element sequence: Besides Enumerable.Singleton, I also miss Enumerable.Add<T>(param T[]) or even just Add<T>(T t). Singleton could thus be implemented as Enumerable.Empty<T>().Add(t). I guess Concat could be abused for this.
I don’t see what you mean by (2), or what the point of “AndThen nop” was in your example – could you elaborate?
> Singleton could thus be implemented as Enumerable.Empty().Add(t)
That reminds me of “immutable” (a.k.a., “persistent”) collections:
http://blogs.msdn.com/b/bclteam/archive/2013/03/06/update-to-immutable-collections.aspx
Honestly, I always thought that the term “bind” referred to this:
http://en.wikipedia.org/wiki/Name_binding
As in, the operator binds the extracted value to the first parameter of the supplied function.
But now it seems too specific. Eric’s explanation makes more sense to me.
Too bad the word singleton from mathematics has been hijacked by the pattern people. That world have been a beauty here.
Okay, this part: “Let’s be clear on this: the bind operation takes a workflow and a function and gives you back a new workflow that feeds the result of the original workflow into the new function when the new workflow is executed. The bind operator does not execute the workflow; it makes a new workflow out of an old one.” is, in my opinion, is one of the most important thing one should understand about monads if he plans to use them.
In some sense, monads make up an interpreted language inside your program—which is usually type-checked at the compile time!