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.