Monads, part six

Posted on by

Last time in this series we finally worked out the actual rules for the monad pattern. The pattern in C# is that a monad is a generic type M<T> that “amplifies” the power of a type T. There is always a way to construct an M<T> from a value of T, which we characterized as the existence of a helper method:

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

And if you have a function that takes any type A and produces an M<R> then there is a way to apply that function to an instance of M<A> in a way that still produces an M<R>. We characterized this as the existence of a helper method:

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

Is that it? Not quite. In order to actually be a valid implementation of the monad pattern, these two helper methods need to have a few additional restrictions placed on them, to ensure that they are well-behaved. Specifically: the construction helper function can be thought of as “wrapping up” a value, and the application helper function knows how to “unwrap” a value; it seems reasonable that we require that wrapping and unwrapping operations preserve the value.

With that in mind, we notice that ApplySpecialFunction takes as its second argument a function from A to M<R>, for any A and any R. But CreateSimpleM is a function from T to M<T>, and is therefore a possible argument to ApplySpecialFunction! Suppose we have: [1. I’m no longer going to write out the bodies of these methods in such a verbose style.]

static Nullable<T> CreateSimpleNullable<T>(T t)
{
  return new Nullable<T>(t);
}
static Nullable<R> ApplySpecialFunction<A, R>(
  Nullable<A> nullable,
  Func<A, Nullable<R>> function)
{
  return nullable.HasValue ?
    function(nullable.Value) : 
    new Nullable<R>();
}

And then we notice that CreateSimpleNullable has the correct signature to be passed as the second argument to ApplySpecialFunction:

Nullable<int> original = Whatever();
Nullable<int> result = ApplySpecialFunction(original, CreateSimpleNullable);

Work your way through what happens here. If original is null then we get null back out. If original has a value, say, 12, then we unwrap it, pass it to MakeSimpleNullable, and get a wrapped 12 back out! The rule is:

Applying the “make a simple wrapper around this value” function to a monad value must produce the same monad value.

And in this case we actually have value identity. Now, I note that we are not requiring referential identity here, should the monadic type happen to be a reference type. Let’s consider our OnDemand<T> monad:

static OnDemand<T> CreateSimpleOnDemand<T>(T t)
{
  return () => t;
}
static OnDemand<R> ApplySpecialFunction<A, R>(
  OnDemand<A> onDemand,
  Func<A, OnDemand<R>> function)
{
  return ()=>function(onDemand())();
}

If we have

OnDemand<int> original = () => DateTime.Now.Seconds;
OnDemand<int> result = ApplySpecialFunction(original, CreateSimpleOnDemand);

Then original and result are certainly not reference equal. But both original and result do the same thing: when you call them, they tell you what the current second is. The latter unfortunately jumps through several unnecessary hoops in order to do so, but it gets there in the end.

In some implementations of the monad pattern it might be cheap and easy to ensure that the two instances be referentially identical, and obviously that would be great. But all that is actually required is that the original and resulting instances be semantically identical when the simple construction function is applied to an existing monad.

The next restriction is that the “simple wrapper around a value” actually act like a simple wrapper around a value. But how can that be precisely characterized? Easily enough with the two helper methods we have. Let’s look at an example. Recall that we had a SafeLog method:

static Nullable<double> SafeLog(int value) { ... }

Now suppose we had:

int original = 123;
Nullable<double> result1 = SafeLog(original);
Nullable<int> nullable = CreateSimpleNullable(original);
Nullable<double> result2 = ApplySpecialFunction(nullable, SafeLog);

You would expect that result1 and result2 would be the same nullable double, right? If Nullable<int> is just a simple wrapper around an int then applying a function to it should be just the same as applying the function to the original integer value. We can generalize this rule and say that the result of applying a special function to an value, and to the same value “wrapped up in a monad”, must be the same. [2. Again, we do not require referential identity, only that the results be “logically” the same.]

OK, so let’s once again sum up. The rules of the monad pattern are that a monadic type M<T> provides operations that are logically equivalent to methods:

static M<T> CreateSimpleM<T>(T t) { ... }
static M<R> ApplySpecialFunction<A, R>(
  M<A> monad, Func<A, M<R>> function) {...}

subject to the restrictions that:

ApplySpecialFunction(someMonadValue, CreateSimpleM)

results in a value logically identical to someMonadValue, and that

ApplySpecialFunction(CreateSimpleM(someValue), someFunction)

results in a value logically identical to

someFunction(someValue)

Are we done yet? Please?

Sigh. No. We are still missing one rule of the monad pattern but I promise, this is the last one. Next time on FAIC we’ll discuss the nature of programming, and, for that matter, all problem solving, and then see how the monad pattern fits into that. Along the way we’ll deduce the last rule.

27 thoughts on “Monads, part six”

  2. Can’t wait to hear about the nature of programming. I’ve been programming for over a decade, so it’s about time I learned something about that!

    Reply ↓

  3. I like this series but I have to say I recognize this only because I know “monads” already.
    All the ugly type-annotation and Func<A> things in C# just mess up and clutter things to much.

    So if any of your readers really want to understand what is going on I recommend to visit some references/tutorials on monads using F# or even Haskell – even if you don’t know those languagues you will have a much easier time understanding monads this way.
    You can find much on this (even in non-Haskell) here: http://www.haskell.org/haskellwiki/Monad

    Also don’t forget to watch “don’t fear the monad” (http://channel9.msdn.com/shows/Going+Deep/Brian-Beckman-Dont-fear-the-Monads/)- still one of the best introductions there is IMHO

    Reply ↓

    • “even if you don’t know those languagues you will have a much easier time understanding monads this way” I don’t know about that. I got as far as the definition of a monad in that first link and realized I have no idea how to read Haskell syntax.

      Reply ↓

      • As Carsten says, the beauty of Haskell is that it has no “clutter”; it is an extremely concise language. Of course, that means that it looks like Greek to the uninitiated. Redundancy often increases comprehensibility, and Haskell has very little redundancy. Erik Meijer once told me that Haskell doesn’t have syntactic sugar, it has syntactic sodium. 🙂

        Reply ↓

    • I don’t agree. I didn’t know anything about monads before reading these articles and I find them quite clear.
      Maybe it’s because I’m very familiar with the C# syntax, so it does not confuse me.
      Maybe it’s because of my background in mathematics.

      Whatever, I find the concept of monads fascinating.

      Reply ↓

    • Thanks Carsten.
      Now that Eric’s series has renewed my interest in monads (huge thanks!!!!), I’m eager to see them applied in other, more accommodating languages. I did a FP course a long time ago that used HUGS (Haskell Using Gofer Syntax), but didn’t find out about monads then.

      Reply ↓

  4. Is the ability to Apply CreateSimpleM critical to implementing monads? If so, why?

    The reason I ask is that being able to apply CreateSimpleM is the only big distinction I can see between ApplySpecialFunction and ApplyFunction and I feel like I’m missing something.

    The only other difference I see between ApplySpecialFunction and ApplyFunction is how Apply is used. With ApplySpecialFunction, I must supply a function that returns a value in a special kind of wrapper. With ApplyFunction, I should supply a function that returns a value that is not in a special kind of wrapper. Coming from a scripting background where I have to enforce all sorts of rules by myself, that difference between ApplySpecialFunction and ApplyFunction doesn’t really matter. I feel like I’m missing something here.

    Reply ↓

  5. It definitely is critical, because that is the point of a Monad and the ApplyFunction and ApplySpecialFunction. You want to be able to create logic to manipulate the “amplified” value the same way you can manipulate the non-amplified value. Any function you can apply to A, you also want to be able to apply to M<A>. That is the purpose of ApplyFunction and ApplySpecialFunction: to pass in M<A> and a function that manipulates A into an R (or M), and get back an M that represent the same logical R that you would get if you just went from A to R. Go look at the AddOne examples that Eric gave in the early posts: you can add one to Int or M and get the same logical result.

    Reply ↓

  6. Wow. Thank you for replying to my comment.

    “consider what happens when the func you want to apply has its return value naturally as a monad i.e. R is M”
    – jk

    Then I get back M<M<R>>. I know it doesn’t seem like it from my comments, but I do understand this. It’s just that the idea of a function that’s supposed to deal with M, asking the user of that function to deal with M, just to avoid the potential of getting back M<M<R>>, was uncomfortable to me. To me, it’s like using a sort function that not only asks me to write a comparison function, but also requires that the comparison function calls a move(item) function. At least, that’s where the discomfort was coming from.

    “..there are two possible cases, when one have the function to convert from A to R and one have the function to convert from A to M<R>, since converting from R to M<R> is simple (just call CreateSimple) anyone who knows how to convert from A to R also knows how to convert from A to M<R>…”
    – EduardoS

    Yes, CreateSimpleM does make things easier on the user of the function, but I still think it’s weird to require the user of the function to call CreateSimpleM.

    “SF: Exactly, if all you know is to convert A to R then please, convert A to R and then call CreateSimple on the result to convert it to M”
    – EduardoS

    me: But SF, it’s your function. What’s stopping you from calling it yourself? Can you change your structure so that you can call CreateSimpleM yourself?

    “There is a difference between getting out the value or values out of a monad and applying a function to a monad and keeping the special “amplification” of the monad. For example, we know how to get values out of IEnumerable by using foreach, but it is a different thing to apply a function to the IEnumerable and keep the “delayed execution” property of IEnumerable.”
    – Dan Baker

    Yes, I understand this. Right now though, I’m just trying to see why certain types were chosen, how they interact with each other, why these restrictions and not those, etc., instead of trying to make a strong connection between the very abstract concept of Monads with the very concrete IEnumerable.

    “Curse you angle brackets!

    imfrancisd, I think what you’re missing is that the goal of ApplyFunction isn’t to just convert an M[A] to M[R], but to be able to apply *any* function that can be applied to an object of type A to an object of type M[A] and be able to get back the result…”
    – Kevin Yancey

    Yes, I was missing that. I’m also missing “why these *any* function and not those, or those…”

    “Mathematician and computer scientist love to have a minimum number of hypothesises, so they go for the first definition. If you find 2) easier to understand, just run with it. It is just as valid as 1). It’s just a little longer.”
    – Jean-Noël Gourdol

    I understand that eventually, some parts of the implementation just comes do to someone just making a choice and there’s really nothing more to it than that. I just want to have an idea of which parts of the implementation are driven by the programming language, the mathematical definitions, personal preferences, etc.

    Reply ↓

  8. Pingback: Monads, part five | Fabulous adventures in coding

Leave a Reply

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

Gravatar
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 )

Cancel

Connecting to %s