We are closing in on the actual requirements of the “monad pattern”. So far we’ve seen that for a monadic type `M<T>`

, there must be a simple way to “wrap up” any value of `T`

into an `M<T>`

. And last time we saw that any function that takes an `A`

and returns an `R`

can be applied to an `M<A>`

to produce an `M<R>`

such that both the action of the function and the “amplification” of the monad are preserved, which is pretty cool. It looks like we’re done; what more could you possibly want?

Well, let me throw a spanner into the works here and we’ll see what grinds to a halt. I said that you can take *any* one-parameter function that has *any non-void return type whatsoever*, and apply that function to a monad to produce an `M<R>`

for the return type. Any return type whatsoever, eh? OK then. Suppose we have this function of one parameter:

(Again, for expository purposes I am writing the code far less concisely than I normally would, and of course we are ignoring the fact that `double`

already has a “null” value, `NaN`

.)

static Nullable<double> SafeLog(int x) { if (x > 0) return new Nullable<double>(Math.Log(x)); else return new Nullable<double>(); }

Seems like a pretty reasonable function of one parameter. This means that we should be able to apply that function to a `Nullable<int>`

and get back out…

oh dear.

… a `Nullable<Nullable<double>>`

. We said that our `ApplyFunction<A, R>`

helper takes in an `Nullable<A>`

and a `Func<A, R>`

and gives you back a `Nullable<R>`

, and in this case, `R`

is `Nullable<double>`

.

Now, remember a while back I said that for expository purposes I was going to ignore the inconvenient fact that it is illegal to make a `Nullable<Nullable<double>>`

; the CLR requires that the type argument must be a non-nullable value type. My point is that even if this were *legal*, which it is not, it would still seem somehow *wrong*.

Similarly, if we had a function that takes an `int`

and returns a `Lazy<double>`

, it seems wrong that applying that function to a `Lazy<int>`

would produce a `Lazy<Lazy<double>>`

. If we had a function that takes an `int`

and returns a `Task<double>`

, it seems wrong that applying that function to a `Task<int>`

would produce a `Task<Task<double>>`

. And so on. In all these cases it seems like the `ApplyFunction`

helper ought to be able to remove the extra indirection. Let’s make a new version of `ApplyFunction`

to explore this idea.

static Nullable<R> ApplySpecialFunction<A, R>( Nullable<A> nullable, Func<A, Nullable<R>> function) { if (nullable.HasValue) { A unwrapped = nullable.Value; Nullable<R> result = function(unwrapped); return result; } else return new Nullable<R>(); }

Hey, that was easy! Now we can apply `SafeLog`

to a nullable int and get back out a nullable `double`

, not a nullable nullable `double`

. But we already know that `Nullable<T>`

is one of the simplest monads; let’s try to write the special function application helper for `OnDemand<T>`

by modifying our earlier version:

static OnDemand<R> ApplySpecialFunction<A, R>( OnDemand<A> onDemand, Func<A, OnDemand<R>> function) { return () => { A unwrapped = onDemand(); OnDemand<R> result = function(unwrapped); return result(); }; }

Again, piece of cake. We still have the property that all computations are performed on demand, and we don’t end up with an `OnDemand<OnDemand<R>>`

. The special function application helpers for `Lazy<T>`

and `Task<T>`

are similarly straightforward:

static Lazy<R> ApplySpecialFunction<A, R>( Lazy<A> lazy, Func<A, Lazy<R>> function) { return new Lazy(() => { A unwrapped = lazy.Value; Lazy<R> result = function(unwrapped); return result.Value; }; } static async Task<R> ApplySpecialFunction<A, R>( Task<A> task, Func<A, Task<R>> function) { A unwrapped = await task; Task<R> result = function(unwrapped); return await result; }

You see the pattern? A monadic type always knows how to “flatten” what should be an `M<M<R>>`

into an `M<R>`

! To avoid having to make a `Nullable<Nullable<R>>`

you check to see if the outer one has a value. If it does, use it. If not, make a null `Nullable<R>`

and use that. To avoiding having to make a `Task<Task<R>>`

you await the outer task and then await the inner task. And so on.

We forgot one. How can we turn what should be a sequence of sequences, `IEnumerable<IEnumerable<R>>`

, into a sequence, `IEnumerable<R>`

? Easy enough; we just concatenate all the sub-sequences into one big sequence.

static IEnumerable<R> ApplySpecialFunction<A, R>( IEnumerable<A> sequence, Func<A, IEnumerable<R>> function) { foreach(A unwrapped in sequence) { IEnumerable<R> result = function(unwrapped); foreach(R r in result) yield return r; } }

If you are following along carefully you will probably have noticed that `ApplySpecialFunction`

for the sequence monad is better known as one of the `SelectMany`

extension methods. We’ll come back to that interesting and entirely non-coincidental fact later in this series.

OK, summing up, so far it looks like we have sussed out the following rules:

Rule one of the monad pattern is that there is always a way to “wrap up” a value of type `T`

into an instance of `M<T>`

. We represented this earlier in this series by requiring that there be a helper method:

static M<T> CreateSimpleM<T>(T value)

Rule two of the monad pattern is that if you have a function from `A`

to `R`

, then you can apply that function to an instance of `M<A>`

and obtain an instance of `M<R>`

. We represented this by requiring that there be a helper method:

static M<R> ApplyFunction<A, R>( M<A> wrapped, Func<A, R> function)

Rule three of the monad pattern is that if you have a function from `A`

to `M<R>`

then you can apply that function to an instance of `M<A>`

and obtain an instance of `M<R>`

. We represented this by requiring that there be a helper method:

static M<R> ApplySpecialFunction<A, R>( M<A> wrapped, Func<A, M<R>> function)

Are these actually the rules of the monad pattern? There seems to be a small problem here: these three rules contain a redundancy. Rule two need not be stated as a rule; it is implied by rules one and three! It is easy to see how. Suppose we had `CreateSimpleM`

and `ApplySpecialFunction`

written already for a monadic type `M<T>`

. We can implement `ApplyFunction`

trivially:

static M<R> ApplyFunction<A, R>( M<A> wrapped, Func<A, R> function) { return ApplySpecialFunction<A, R>( wrapped, (A unwrapped) => CreateSimpleM<R>(function(unwrapped))); }

Apparently `ApplyFunction`

and `ApplySpecialFunction`

are mis-named; the first is actually a special case of the second!

Thus we can eliminate rule two, because it is implied by rules one and three. So our new rules of the monad pattern are:

Rule one: there’s a helper method

static M<T> CreateSimpleM<T>(T value)

Rule two: there’s a helper method

static M<R> ApplySpecialFunction<A, R>( M<A> wrapped, Func<A, M<R>> function)

that preserves the “amplification” provided by the monadic type and preserves the meaning of the applied function. Moreover, the usual way that the `ApplySpecialFunction`

works is: extract the underlying set of values from the wrapped object, apply the function to the set of underlying values to produce a set of wrapped results, and then somehow combine the set of wrapped results into a single wrapped result. **The precise details of how the “extraction” and “combination” steps work determines what “amplification” the monad implements.**

Are these actually the rules of the monad pattern??? Basically, yes. Finally!

Aside: There is a second equivalent way to characterize the rules of a monad: that our original `ApplyFunction`

operation exists and that there is a way to collapse an `M<M<R>>`

into an `M<R>`

. Though it should be fairly obvious how such a thing would work given my explanation so far, this is not the usual way to characterize the requirements of the monad pattern and so I’m going to say no more about it in this series.

There are actually a few additional invariants that the `ApplySpecialFunction`

must ensure in order to be a correct implementation of the monad pattern.

**Next time on FAIC** we’ll digress with a Fun For Friday Classic FAIC Rerun. **Next week** we’ll continue our investigation of the monad pattern in order to deduce the remaining rules.

Great series of articles on monads. I finally get them now.

However, on remark: you sometimes call the function `MakeSimpleM` and at other times `CreateSimpleM`.

Whoops, I thought I fixed all of those. Thanks for the note.

I’m a bit tired, but shouldn’t it be:

(A unwrapped) => CreateSimpleM(function(unwrapped))

… instead of CreateSimpleM, because the function should go from A to M?

Oh, that didn’t get formatted very well 🙂 Trying again:

(A unwrapped) => CreateSimpleM<R>(function(unwrapped))

…instead of:

CreateSimpleM<A>

This tripped me up as well. It seems like the second argument in the derived ApplyFunction method body is supposed to be (A unwrapped) => CreateSimepleM(function(unwrapped)), given that the parameter is of the type Func<A, M>.

If this is not the case, can someone (Eric?) clarify this further?

Thanks for doing this series. More object-oriented programmers need to know about this concept. I have a little Functional Programming experience, and still most of the explanations on the Internet were of little use to me. It wasn’t until I saw a video from one of the guys who designed the Reactive Extensions for .NET that I started to “get” it. Once I had that “AHA!” moment, I realized how powerful this idea is.

> video from one of the guys who designed the Reactive Extensions for .NET

Which video is this? Link, please.

“The CLR type system is insufficiently rich to express the monad pattern in general; for that you need a “higher” type system, like that of Haskell. You’ll have to build each specific monad yourself. However, it looks like you are well on your way.” (http://stackoverflow.com/a/8979056)

Are you going to discuss exactly what c# is “missing” compared to e.g. Haskell?

You don’t really need a Higher kinded type to implement individual monads, however it prevents Transformers I believe (unless you want to write a transformer for two specific monads, but then there isn’t a point).

Pingback: The Morning Brew - Chris Alcock » The Morning Brew #1311

Nullable<Nullable<Int>> is wrong?! That’s sad. Imagine I have a big data store (Map<int, Nullable<int>>), or Map<string, FancyClass>), and I want to write a cache system which would be a Map<Key,Nullable<Data>> as well. But how on Earth do I distinguish a NULL which is “NULL in the cache because you didn’t poll data from the store” and a NULL which is “NULL in the cache because data in the store is NULL”?

For store which is Map<Key, Nullable<Data>> I’d need to use Map<Key, Nullable<Nullable<Data>> for caching: if there is a null, then I should cache; if there is an actual value inside Nullable, then that’s the value in the store, which *may* happen to be null.

No, of course, there are situations where “join :: m m a -> m a” makes perfect sense, sure. But to claim that “m m a” values don’t make much sense on their own? That’s exactly the usual way to define a monad: triple of

1) an endofunctor M: C -> C , where C is a category of the language’s types (its objects are types, and its arrows are one-argument functions without side effects);

2) a natural transformation eta: 1 -> M , where we will use name “unit” to call its components on objects, unit_X = eta(X) : X -> M(X). When eta works on arrows, it’s called… let it be “funit”, funit_{X,Y} : Ar(X,Y) -> Ar(M(X), M(Y)), though in Haskell it’s called “fmap”.

3) a natural transformation mu: M o M -> M , where we will use name “join” to call its components on objects, join_X = mu(X) : M(M(X)) -> M(X).

If you write it in more C#-friendly way, you get polymorphic, pardon, generic methods

M<X> unit(X obj);

Func<X, M<Y>> funit(Func<X, Y> arrow);

M<X> join(M<M<X>> obj);

And

M<Y> bind(M<X> obj, Func(X, Y) arrow);

is defined in their terms:

M<Y> bind(M<X> obj, Func(X, M<Y>) arrow) {

Func<X, M<M<Y>> liftArrow = funit(arrow);

M<M<Y>> result = liftArrow(obj);

return join(result);

}

Actually, you don’t even need “return”.

Gee, I miss LaTeX 😦

Wait, you DO need the unit/return, because liftArrow has type Func<M<X>, M<M<Y>> , so result is “result = liftArrow(unit(obj));”

shouldn’t

static OnDemand ApplySpecialFunction

return result, but not result() ?

no, it should not.

For the IEnumerable version, why do you need to enumerate the result and yield each element rather than simply returning result?

C# does not support yielding more than one value at a time. F# has yield! (pronounced “yield bang” as I’ve heard it) which would simplify the code if it was available in C#.

Pretending C# had a new keyword yieldAll that did the same thing, then we could do this:

static IEnumerable ApplySpecialFunction(

IEnumerable sequence,

Func<A, IEnumerable> function)

{

foreach(A unwrapped in sequence)

{

IEnumerable result = function(unwrapped);

yieldAll return result;

}

}

Wouldn’t that be nice?!?

C-Omega, a research version of C# in which many of the C# 3 features were first prototyped, has “yield foreach” as you describe. Unfortunately it turns out that in order to do it efficiently in the case of deeply recursive iterators, C-Omega ended up building a state machine that did not have the exactly correct semantics for handling exceptions. I do not know the details; I never pressed Erik Meijer to explain them all to me. I would love to have it in C# but it seems unlikely that it will be added any time soon.

Pingback: Monads, part four | Fabulous adventures in coding