So far we’ve seen that if you have a type that follows the monad pattern, you can always create a “wrapped” value from any value of the “underlying” type. We also showed how five different monadic types enable you to add one to a wrapped integer, and thereby produce a new wrapped integer that preserves the desired “amplification” — nullability, laziness, and so on. Let’s march forth (HA HA HA!) and see if we can generalize the pattern to operations other than adding one to an integer.
Let’s stick with integers for a moment though; higher-order programming can be a bit tricky and so I want to approach it slowly. We represent an operation on integers with a Func<int, int> — that is, a delegate which takes an integer and produces an integer. We can generalize each of our five AddOne methods of last time to instead take a Func<int, int> that represents the desired operation:
static Nullable<int> ApplyFunction(
Nullable<int> nullable,
Func<int, int> function)
{
if (nullable.HasValue)
{
int unwrapped = nullable.Value;
int result = function(unwrapped);
return new Nullable<int>(result);
}
else
return new Nullable<int>();
}
Our AddOne method is now a special case:
static Nullable<int> AddOne(Nullable<int> nullable)
{
return ApplyFunction(nullable, (int x) => x + 1);
}
I’m sure you can see how we could apply this same simple transformation to the other AddOne methods to make all five ApplyFunction methods. Can we make this even more general? Sure; there’s nothing special about integers! We can replace all those integers with Ts:
static Nullable<T> ApplyFunction<T>(
Nullable<T> nullable,
Func<T, T> function)
{
if (nullable.HasValue)
{
T unwrapped = nullable.Value;
T result = function(unwrapped);
return new Nullable<T>(result);
}
else
return new Nullable<T>();
}
And moreover: suppose we have a function from int to double; say we want to divide the int by two and get the result as a double. Clearly if we have an operation on an int that produces a double, then we should be able to make an operation on an “amplified” int that produces an “amplified” double. Really this thing should take two type parameters: the underlying type on the input side and the underlying type on the output side:
static Nullable<R> ApplyFunction<A, R>(
Nullable<A> nullable,
Func<A, R> function)
{
if (nullable.HasValue)
{
A unwrapped = nullable.Value;
R result = function(unwrapped);
return new Nullable<R>(result);
}
else
return new Nullable<R>();
}
And similarly we can make ApplyFunction methods that allow you to do the same thing to our other examples of the monad pattern:
static Lazy<R> ApplyFunction<A, R>(
Lazy<A> lazy,
Func<A, R> function)
{
return new Lazy(()=>
{
A unwrapped = lazy.Value;
R result = function(unwrapped);
return result;
});
}
And so on; the rest are an easy exercise given how verbosely I wrote them out last time.
We know that the first part of the monad pattern is that there’s got to be an easy way to take a value of the underlying type and turn it into a value of the amplified type. And I said earlier that, though it seems plausible that there ought to also be a way to get the values back out on demand, the truth is actually more subtle. What we’ve shown here is that we actually need to get the values back only insofar as is necessary to ensure that any function on the underlying values can be applied to any amplified value.
Essentially what we’ve got here is a way of turning functions from A to R into functions from M<A> to M<R> such that the action of the function is preserved and the “amplification” provided by the monadic type is also preserved. That is pretty darn useful!
Is this then the second requirement of the monad pattern: that you can write a method with the signature
static M<R> ApplyFunction<A, R>( M<A> amplified, Func<A, R> function)
that does the right thing?
No. But we are so close! Next time on FAIC we’ll make a small but vital modification to the signature pattern ApplyFunction to arrive at the actual second requirement of the monad pattern.
Fabulous adventures in coding 
This is really good stuff. I like your pedagogical approach over something more densely technical. Another fellow blogger takes a similar approach, though he often gets into details much more quickly than you have. Check him out, if you don’t already – scientopia.org/blogs/goodmath/
Mark is one of my favorite bloggers, and in general is just a really cool guy.
Regarding your note, well punned, sir.
Part of me is very disappointed that it wasn’t, “Ha! I kill me.”
You need to wait until the 15th for that!
“Small but vital modification”: rename the function “bind”?
On a more serious note, bind should accept a function that already returns an augmented value, so the signature should be something like:
Which is highly useful, and required to implement the monad pattern. However, the ApplyFunction method you posted here, which is basically the same as fmap, is far more useful. The reason a monad needs Bind and not ApplyFunction is because ApplyFunction can be defined in terms of Bind, but not vice versa – Bind is more general while ApplyFunction is more useful.
You have anticipated my denouement, Commander Riker. We’ll cover all that in the next episode.
I believe **you** have anticipated the denouement, sir 🙂
http://stackoverflow.com/a/7828952/3312
You could that coming, but hey, why spoil it? Some people like suspense…in their blog series.
C’mon, people, let Eric finish
I’m sure I had some sort of question in mind when I wrote that, but I started rambling about the difference between Bind and ApplyFunction and completely forgot about it 🙂
I’m enjoying your series on monads. I’d be interested to know:
(1) Are the obvious functions for mapping values to amplified values, or for binding, the *only* ones that make a valid monad for those particular generic types? E.g., I could imagine a much less obvious function for mapping T to Nullable<T>, say (T t) => T is int ? new Nullable<int>((int)t + 1) : new Nullable<T>(t)
God knows why you’d want to do that, but is it an equally valid monad?
(2) Why can’t the other common C# generic types be expressed as monads? Is it that they don’t have an obvious bind method, or for some is there no *possible* way to define a valid bind method?
Should be: t is int
But hopefully you get what I’m trying to say
In a couple more episodes we’ll cover why such an encoding would not be a valid implementation of the monad pattern.
As for other generic types, what types did you have in mind?
IEquatable<T>, for instanceOK, so (1) what “amplification” does it represent? (2) how do you turn an instance of any type T into an instance of
IEquatable<T>? and (3) if you have a function from A to R, how do you turn that into an “equivalent” function fromIEquatable<A>toIEquatable<R>? If you can’t answer those three questions then it’s not an example of the monad pattern.(1) A T that can check whether it’s the same as another T. (I’m not sure if that’s a valid “amplification”, since I’m not totally clear on the rigorous definition of “amplification”, but it doesn’t sound that different than your examples of “a T that can be null”, or “a T that can be computed on demand”.
(2) Well, I’m not sure if this is allowed but couldn’t you just wrap it in a class that implements IEquatable<T>, using the T’s equals method (that it inherits from object, if it doesn’t have its own)?
(3) Hmm… I guess I would either need a way to convert any IEquatable<A> to A (so I could apply the Func<A,R> to it before comparing to R), or I’d need a way to invert the Func<A,R> so I could map the R to an A and compare to my IEquatable<A>
At least if I’m trying to do the bind in a way that preserves some properties of the original function. Originally I had been thinking I could do the amplification in a trivial way like always define the Equals method as return true; (which is still a reflexive/symmetric/transitive equivalence relation), but based on your answer to my (1) above I’m guessing that will be invalid for reasons you have yet to reveal.
Could be wrong here, but I think you are basically describing the Identity monad here, so while it is a monad it doesn’t really buy you much?
The problem with calling IEquatable a monad is that there’s no way to “unpack” an arbitrary IEquatable, and hence there’s no way to define the Bind function (note that IEnumerable works because the interface defines methods for unpacking it). However, you could define a generic implementation of IEquatable that wraps an instance of T, define a bind method for that specific implementation of IEquatable, and call that a monad. The amplification would be that it turns any T into a “T that implements IEquatable”. But, even in that case, its a monad only trivially (similar to, but perhaps not identical to the Identity Monad) and not all that useful.
That makes sense. Thanks!
Incidentally, types for which you can write ApplyFunction (more commonly called “map”):
are called “(covariant) functors” in Haskell, and are much more prevalent than monads. It’s no accident that this is called “covariance” — it’s very closely related to the subtyping sort of covariance. In fact, it’s “the same thing”, just in a different category. Compare:
And you’ll find that, generally, you can write “map” for a particular type more or less exactly when it’s (subtyping) covariant.
Contravariance works too, with the types reversed:
Shouldn’t that be
static M Map(M x, Func f)instead?
Aargh! My tags got mangled.
static M Map (M x, Func f)
Shoudln’t f be a function from A to B, instead of a function returning A from void?
Yes, that’s what I wrote originally. My tags also got mangled, and were mysteriously fixed, but apparently not all the way. fmap takes a value of type M-of-A and a function from A to B, and gives you a value of type M-of-B (and, ideally, is polymorphic over any functor M, so that you can have one generic mapping function for any covariant type).
This comment has nothing to do with monads. Sorry, but I wasn’t sure how to get to you directly.
For a future series, could you go into the immutability techniques for Roslyn’s AST, such that you can update/replace individual nodes (e.g. an statement) without cloning the entire AST structure?
Pingback: Monads, part three | Fabulous adventures in coding
Pingback: Monads, part five | Fabulous adventures in coding
This monad series is darn good!
Thanks.