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.
Sorry but I already stopped to understand in the Part two. I’m not in that level. 😦
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!
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
“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.
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. 🙂
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.
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.
But languages are a tool not the end. So C# works for me.
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.
ApplyFunction (aka fmap) is still useful, it just is insufficient to be monad (it is a function on functors which are kind of a superclass of monads)
the critical thing is that for a monad with ApplyFunction (aka fmap) you need to be able to flatten M<M<A>> somehow, and indeed there is another formulation of a monad which does it (Eric hinted at this in the footnotes of part 5 ) this way by introducing a flatten function (aka join). with unit/fmap/join the identity proofs are arguably a bit easier to understand but there is some redundancy, the unit/bind formulation is the one that tends to be used in real software
What I’m getting at is that if I’m supplying the function to ApplyFunction, then I can make sure that I never get back M<M<A>> in the first place. Is getting back M<M<A>> unavoidable in some situations?
I believe you are asking if you can create your own optimized version of ApplyFunction, instead of defining ApplyFunction using ApplySpecialFunction and CreateSimplyM. The answer is yes and it is often done. As Eric hinted at in one of his notes, for IEnumerable, SelectMany is the ApplySpecialFunction of IEnumerable. SelectMany could be used to define most of the other Enumerable functions such as Select, which is the ApplyFunction of IEnumerable. But the actual implementation of Select is optimized and does not call SelectMany for the exact reason you give: to avoid wrapping with a CreateSimpleM function.
I’m not asking about optimization. I just want to understand why things are implemented in a certain way. I thought about my question some more, and here’s what’s really bothering me.
The goal of Apply is to convert M<A> to M<R>. Here’s how I look at ApplyFunction and ApplySpecialFunction.
Conversation with
M<R> ApplyFunction<A, R>(M<A> wrapped, Func<A, R> function):
Me: Hey ApplyFunction. Can you convert this M<A> to M<R> for me? Please?
AF: Sure. Just tell me how to convert A to R and I’ll get right on it.
Me: Thanks ApplyFunction!
Conversation with
M<R> ApplySpecialFunction<A, R>(M<A> wrapped, Func<A, M<R>> function):
Me: Hey ApplySpecialFunction. Can you convert this M<A> to M<R> for me? Please?
SF: Sure. Just tell me how to convert A to M<R> and I’ll get right on it.
Me: Wait, you want me to tell you how to convert A to M<R>?
SF: I want you to tell me how to convert A to M<R>.
Me: But if I know how to convert A to M<R>, why would I need your help?
SF: Silly. Because you don’t know how to convert M<A> to A!
Me: Wait, let me get this straight. I’m asking you to convert M<A> to M<R>.
SF: Yes.
Me: And you think that I know how to convert A to M<R>.
SF: That’s right.
Me: But at the same time, you think I don’t know how to convert M<A> to A?
SF: Uh huh.
Me: I know how to convert A to M<R> but I don’t know how to convert M<A> to A???
SF: Uh huh.
Me: ?????
I guess ApplySpecialFunction and I just come from two different worlds. I don’t know.
consider what happens when the func you want to apply has its return value naturally as a monad i.e. R is M
imfrancisd, initially I had the same problem to understand it, 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, since converting from R to M is simple (just call CreateSimple) anyone who knows how to convert from A to R also knows how to convert from A to M and so both cases can be convert using just one convert function (ApplySpecialFunction), to use ApplyFunction in both cases one would need to know how to convert from M to R, but this conversion isn’t possible at all (at least loss less) since M is an augmented value of R and doing the lossy conversion would lose exactly the augmentation wich is the point of the monad pattern, so let’s change a bit your talk to make SF more helpful.
You: Hey ApplySpecialFunction. Can you convert this M to M for me? Please?
SF: Sure. Just tell me how to convert A to M and I’ll get right on it.
You: Wait, you want me to tell you how to convert A to M?
SF: I want you to tell me how to convert A to M.
You: But if I know how to convert A to M, why would I need your help?
SF: Silly. Because it is not possible to convert M to A!
You: Wait, let me get this straight. I’m asking you to convert M to M.
SF: Yes.
You: And you think that I know how to convert A to M.
SF: That’s right.
You: But at the same time, you think I can’t convert M to A?
SF: Uh huh.
You: I know how to convert A to M but I can’t know how to convert M to A???
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
Please add better support for tags…
imfrancisd, initially I had the same problem to understand it, 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> and so both cases can be convert using just one convert function (ApplySpecialFunction), to use ApplyFunction in both cases one would need to know how to convert from M<R> to R, but this conversion isn’t possible at all (at least loss less) since M<R> is an augmented value of R and doing the lossy conversion would lose exactly the augmentation wich is the point of the monad pattern, so let’s change a bit your talk to make SF more helpful.
You: Hey ApplySpecialFunction. Can you convert this M<A> to M<R> for me? Please?
SF: Sure. Just tell me how to convert A to M<R> and I’ll get right on it.
You: Wait, you want me to tell you how to convert A to M<R>?
SF: I want you to tell me how to convert A to M<R>.
You: But if I know how to convert A to M<R>, why would I need your help?
SF: Silly. Because it is not possible to convert M<A> to A!
You: Wait, let me get this straight. I’m asking you to convert M<A> to M<R>.
SF: Yes.
You: And you think that I know how to convert A to M<R>.
SF: That’s right.
You: But at the same time, you think I can’t convert M<A> to A?
SF: Uh huh.
You: I know how to convert A to M<R> but I can’t know how to convert M<A> to A???
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<A>
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. This requires the special yield commands in C# or a lot of coding if you don’t use yield. By using the ApplyFunction and ApplySpecialFunction of IEnumerable (Select and SelectMany) you can write code that never uses the yield command. The special logic to apply a function to IEnumerable and still keep “delayed execution” is hidden from us and we don’t actually need to know how to do it.
imfrancisd, I think what you’re missing is that the goal of ApplyFunction isn’t to just convert an M to M, but to be able to apply *any* function that can be applied to an object of type A to an object of type M and be able to get back the result (note that this function should not have side-effects, only calculate a new value). In some cases, the function I want to apply may return M instead of just an R, which means ApplyFunction would return an M<M>. In most cases, that’s not what I want. Therefore, we define ApplySpecialFunction, which takes the result and flattens it, as a key part of a Monad without loosing any generality because I can easily define ApplyFunction in terms of ApplySpecialFunction. The reverse, defining ApplySpecialFunction in terms of ApplyFunction is not possible, however. You can always create a M from a T, but you can’t, in general, convert an M to a T because the ‘T’ that M wraps may not exist (in the case of Nullable), may not be known yet (in the case of OnDemand), might have multiple values (in the case of IEnumerablt), etc.
Personally, I find the Unit/Bind formulation of a Monad to be more confusing than the Unit/Map/Flatten formulation, as the later seems more orthogonal to me. Basically, to be a monad, three operation must be supported:
Unit: Create an M from a T
Map: Apply any function function T => R to the value(s) held in M, resulting in M.
Flatten: convert M<M> to an equivalent M.
Curse you angle brackets! (okay, I’m going to try again using square brackets in place of the 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 (note that this function should not have side-effects, only calculate a new value). In some cases, the function I want to apply may return M[R] instead of just an R, which means ApplyFunction would return an M[M[R]]. In most cases, that’s not what I want. Therefore, we define ApplySpecialFunction, which takes the result and flattens it, as a key part of a Monad without loosing any generality because I can easily define ApplyFunction in terms of ApplySpecialFunction. The reverse, defining ApplySpecialFunction in terms of ApplyFunction is not possible, however. You can always create a M[T] from a T, but you can’t, in general, convert an M[T] to a T because the ‘T’ that M[T] wraps may not exist (in the case of Nullable), may not be known yet (in the case of OnDemand), might have multiple values (in the case of IEnumerablt), etc.
Personally, I find the Unit/Bind formulation of a Monad to be more confusing than the Unit/Map/Flatten formulation, as the later seems more orthogonal to me. Basically, to be a monad, three operation must be supported:
Unit: Create an M from a T
Map: Apply any function function T => R to the value(s) held in M, resulting in M.
Flatten: convert M to an equivalent M.
Missed converting the last part:
Personally, I find the Unit/Bind formulation of a Monad to be more confusing than the Unit/Map/Flatten formulation, as the later seems more orthogonal to me. Basically, to be a monad, three operation must be supported:
Unit: Create an M[T] from a T
Map: Apply any function function T => R to the value(s) held in M[T], resulting in M[R].
Flatten: convert M[M[T]] to an equivalent M[T].
CreateSimpleM is critical to the Monad pattern, because it is part of the whole purpose of Monads, to be able to “amplify” already existing values or logic. If you don’t have a “constructor” for this new “amplified” logic, then I don’t see how it could be useful. The other part of the purpose of the Monad pattern, as you have indicated, is to be able to ApplyFunction OR ApplySpecialFunction. Monads can apply both types of functions, as long as you have ApplySpecialFunction defined. ApplySpecialFunction is more flexible and so is the second part of the definition of the Monad pattern.
I understand that CreateSimpleM is critical to the Monad pattern. I just wanted to know if passing CreateSimpleM to ApplySpecialFunction was critical to the Monad pattern.
The whole problem thing is that for the monad pattern, you need either of these (with all the good composition properties):
1) CreateSimpleM + ApplySpecialFunction
2)CreateSimpleM + ApplyFunction + Flatten
In case 2), you can recreate ApplySpecialFunction by combining the others, but you need 3 hypothesises. 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.
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.
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.
I like this web blog very much, Its a rattling nice situation to read and obtain info .
Pingback: Monads, part five | Fabulous adventures in coding