Monads, part five

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 [1. 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. [2. 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.]

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;
  }
}

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. [1. 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.] (Finally!) However, 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.

About these ads

17 thoughts on “Monads, part five

  1. 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`.

    • 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?

  2. 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.

  3. “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).

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

  5. 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));”

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s