Last time in this series I discussed the standard terminology used for the monad pattern: that the simple construction method is traditionally called “unit”, and the function application method is traditionally called “bind”. I also pointed out that the two sub-patterns you see most frequently in implementations of the monad pattern are first, association of some state with a value, and second, construction of workflows that describe the sequencing of units of work to be performed in the future. Today we’ll look at that first kind of monad in some more detail.
We’ve been talking extensively about the nullable monad; it essentially associates a single Boolean value with the underlying value. If the Boolean value is true then the value behaves normally; if not, then the “nullness” of the value propagates through the system. [1. We’ve seen in the past that C# is a bit more clever than that for some special cases such as nullable Booleans; we’ll ignore that fact for the purposes of this discussion.] I won’t labour that example more. Rather, let’s look at two variations on the nullable monad:
struct Tainted<T>
{
public T Value { get; private set; }
public bool IsTainted { get; private set; }
private Tainted(T value, bool isTainted) : this()
{
this.Value = value;
this.IsTainted = isTainted;
}
public static Tainted<T> MakeTainted(T value)
{
return new Tainted<T>(value, true);
}
public static Tainted<T> MakeClean(T value)
{
return new Tainted<T>(value, false);
}
public static Tainted<R> Bind<A, R>(
Tainted<A> tainted, Func<A, Tainted<R>> function)
{
Tainted<R> result = function(tainted.Value);
if (tainted.IsTainted && !result.IsTainted)
return new Tainted<R>(result.Value, true);
else
return result;
}
}
(Note that I’ve started calling the bind function “Bind” rather than “ApplySpecialFunction”.)
The semantics of this monad should be pretty clear. We associated a “taint” with a value, and any function that takes as its argument a “dirty” value results in an automatically dirty value. Or, put another way, the only way for a function applied to an instance of this monad can result in a clean result is if the original value was clean and the function produced a clean value. You could use this monad to “amplify” a string so that you could determine if it had been checked for cross-site scripting attacks; strings are presumed dirty until proven clean, and any operation on a dirty string produces another dirty string.
This example was very simple; you might imagine that the “security” state stored here could be far more complex. Rather than a simple Boolean taint, the taint might be an identifier determining which client originated the data. Anything is possible.
Here’s a second variation on the nullable monad:
struct NoThrow<T>
{
private T value;
public T Value
{
get
{
if (this.Exception != null)
throw this.Exception;
else
return this.value;
}
}
public Exception Exception { get; private set; }
private NoThrow(T value, Exception exception) : this()
{
this.value = value;
this.Exception = exception;
}
public NoThrow(T value) : this(value, null) {}
public static NoThrow<R> Bind<A, R>(
NoThrow<A> noThrow, Func<A, NoThrow<R>> function)
{
if (noThrow.Exception != null)
return new NoThrow<R>(default(R), noThrow.Exception);
try
{
return function(noThrow.Value);
}
catch(Exception ex)
{
return new NoThrow<R>(default(R), ex);
}
}
}
Again, the semantics should be pretty clear; this is a buffed-up version of the nullable monad, where a value is “null” if any operation that produced it threw an exception. This monad will be very familiar to anyone who has used the asynchronous monad Task<T> because of course it does much the same thing: if the asynchronous task throws an exception then the exception is stored in the task, and re-thrown when the value of the task is fetched.[1. This technique can be dangerous, in that it can delay the production of an exception until long after the exception handlers designed to deal with it are no longer on the stack. Worse, it can delay the production of an exception indefinitely, leading to programs that should have crashed continuing to corrupt user data. Use with extreme caution.]
You can associate any kind of state whatsoever with a value using a monad. For example, for debugging purposes we might want to accumulate a log describing how it flowed through the program:
struct Logged<T>
{
public T Value { get; private set; }
public string Log { get; private set; }
public Logged(T value, string log) : this()
{
this.value = value;
this.log = log;
}
public Logged(T value) : this(value, null) {}
public Logged<T> AddLog(string newLog)
{
return new Logged(this.value, this.log + newLog);
}
public static Logged<R> Bind<A, R>(
Logged<A> logged, Func<A, Logged<R>> function)
{
Logged result = function(logged.Value);
return new Logged(result.Value, logged.Log + result.Log);
}
}
These are just some of the simpler “associate data with a value” monads that are possible, but I suspect that you get the idea. Next time on FAIC we’ll take a closer look at query expression syntax; it turns out to have a strong connection with monadic binding.
Fabulous adventures in coding 
Small typo, Eric: this.IsTainted should be tainted.IsTainted. Great article 🙂
MakeTainted and MakeClean should use value, not T as argument to the ctor.
public static Tainted MakeTainted(T value)
{
return new Tainted(value, true);
}
public static Tainted MakeClean(T value)
{
return new Tainted(value, false);
}
A typo and what I think is an error, in the NoThrow monad:
newValue = function(noThrow.Value));
1) The type: second parentheses at the end;
2) The error: isn’t “newValue” a “R” while “function” return “NoThrow<R>”?
Great article ! Finally it starts to make some more sense.
There are some type parameters missing in the Logger example too.
Do you ever compile these examples? I mean… with the ‘real’ compiler 😀
Cool, was it, like imfancisd, the Logged example the thing that made it click, or something else?
Ah, that’s what I was missing. Logged<T> was the example I was looking for.
With Logged<T>, I can see why I would want to use Bind (aka ApplySpecialFunction) instead of FMap (aka ApplyFunction). If I add FMap to Logged<T>
public static Logged<R> FMap<A, R>(
Logged<A> logged, Func<A, R> function)
{
R result = function(logged.Value);
return new Logged<R>(result, logged.Log);
}
and I have this in Main()
var i = new Logged<int>(0, “Initial Value; “);
with Bind, adding 5.5 to i would look like this
var d1 = Logged<int>.Bind(i, n => new Logged<double>(n + 5.5, “Add 5.5; “));
and with FMap, adding 5.5 to i would look like this
var d2 = Logged<int>.FMap(i, n => n + 5.5);
d2 = d2.AddLog(“Add 5.5; “);
With that example, I can see some reasons why Bind’s signature makes sense.
1) With Bind, I get a complete Logged object. With FMap I get a Logged object that has an updated value but not an updated log. Having that incomplete object floating around is uncomfortable.
2) Because of the immutable style of programming, FMap creates a temporary Logged object that I end up discarding right away. Bind doesn’t have that problem.
3) If I try to use FMap like Bind (pass a function that returns a Logged object), then I would still have to “flatten” the return value of FMap, which is like getting an object that I end up discarding right away.
4) If I try to rewrite FMap’s body so that FMap doesn’t wrap a Logged object in another Logged object (in order to avoid having to “flatten” the result), then
4a) it would no longer be FMap (at least I don’t think it will be for Haskell programmers)
4b) even if I don’t care about Haskell programmers, because of how generics work in C#, I may have to use reflection or change FMap’s signature in some weird way. I’m not sure about this, but I don’t see an easy way of keeping FMap’s signature, and at the same time change its body so that it doesn’t return Logged<Logged<T>>.
I don’t know if my reasoning above is 100% correct, but for me, the Logged<T> example makes a better case for Bind than just “flattening” alone. At least now, the choice between using Bind or using FMap and Flatten doesn’t seem like I’m just flipping a coin. That’s what I was missing. 🙂
Small Typo: The Value getter in NoThrow should return value instead of Value. The way it is now it’s an infinite loop.
Bind in these examples could rather be an instance method instead of static method:
public Logged Bind(Func<T, Logged> function)
{
Logged result = function(this.Value);
return new Logged(result.Value, this.Log + result.Log);
}
Is that so?
or an extension method as in LINQ
Correct. Whether it is a static method, extension method or instance method (or in the case of Haskell, an infix operator) is just a detail of the language.
Am I missing something, or should your first example actually end like this:
`
if (tainted.IsTainted || result.IsTainted)
return new Tainted(result.Value, true);
else
return result;
`
If result.IsTainted is already true, why would you need to create a new Tainted{T} instance?
Time for my second coffee obviously; thank you.
Hi. I got confused by the Tainted type name, which seems to imply that IsTainted is always true. Same goes for the instances named “tainted” (which may or may not be tainted). Maybe “Taintable” would be a better name?
Also, in the Bind function, why not just return new Tainted<R>(result.Value, tainted.IsTainted | result.IsTainted)? Slightly less performant, but easier to read (IMO).
Great article, though. And thanks again for opening my eyes to the world of Monads.
I was thinking about the NoThrow monad, assuming any type T can be easily converted to Func<T> , how about implementing it this way?
struct NoThrow<T>
{
private T value;
public T Value
{
get
{
if (this.Exception != null)
throw this.Exception;
else
return this.value;//Fix the Typo in original
}
}
public Exception Exception { get; private set; }
private NoThrow(T value, Exception exception) : this()
{
this.value = value;
this.Exception = exception;
}
public NoThrow(Func<T> func)
{
try
{
this.value = func();
}
catch(Exception ex)
{
this.Exception = ex;
}
}
public static NoThrow Bind(
NoThrow noThrow, Func<A, NoThrow> function)
{
if (noThrow.Exception != null)
return new NoThrow(default(R), noThrow.Exception);
return function(noThrow.Value);
}
}
Oh angle brackets…
public static NoThrow<R> Bind<A, R>(
NoThrow<A> noThrow, Func<A, NoThrow<R>> function)
{
if (noThrow.Exception != null)
return new NoThrow<R>(default(R), noThrow.Exception);
return function(noThrow.Value);
}
Cool Eric, great explanation! Looking forward to see how are you going to use LINQ syntax for binding… 🙂
I used (…abused?) “from”, “let” and “select” (SelectMany) a couple of years ago to build a continuation monad based on Task, before you introduced async. I would love to see how this relates to async/await! And maybe understand why you (C# team) went this way instead of a general monad support (performances?)
In general, I wish C# had better support for building these patterns; sure, you can weave them by hand, but some sugaring like F# do would be nice!
Compare
Bind(in1.Receive, (fun a ->
Let(a + 1, (fun a ->
Bind(in2.Receive, (fun b ->
Bind(out.Send(a + b), fun _ ->
Return(Unit.One))))))))
(which, as far as I understand, is what you can do in easily in C# given the information you provided so far)
with
let! a = in1.Receive
let a = a + 1
let! b = in2.Receive
let! _ = out.Send(a + b)
return Unit.One
…and you can see a clear win!
On the danger of the No Throw monad. When the constructed function is finally executed, an exception would short circuit execution. So long we check the exception, why would there be a problem? Is there some unclear semantics at play?
Pingback: Maybe monad what is Just for?
Pingback: Harder to C++: Monads for Mortals 2, First implementation | Clatter from the Byte Kitchen
Pingback: Harder to C++: Monads for Mortals [4], References en Move Semantics | Clatter from the Byte Kitchen