Skip to main content

The Worst Monad Tutorial... Except For All Those Others.

I've found other monad tutorials very frustrating. They are typically written in expressive languages with type inference, which permits concise descriptions, but obscures the underlying type structure. I've been struggling with writing something close to a monad in C# for quite some time, simply because none of these tutorials give a sufficiently complete description of a monad's structure. Suprisingly, the Wikipedia page on monads helped clarify what I was missing.

Here is the general structure of a monad all these tutorials use:
-- the type of monad m
type m a = ...

-- return is a type constructor that creates monad instances
return :: a → m a

-- bind is a function that combines a monad instance m a with a
-- computation that produces another monad instance m b from a's
-- to produce a new monad instance m b
bind :: m a → (a → m b) → m b

So the monad type 'm', has a function 'return' that constructs instances of that type, and 'bind' which converts an instance of that monad into another instance of a monad by passing its private state to the provided function. For instance, meet Haskell's Identity monad:
instance Monad Identity where
return a = Identity a -- i.e. return = id
(Identity x) >>= f = f x -- i.e. x >>= f = f x

Looks simple enough. Now meet Haskell's List monad:
instance Monad [] where
bind m f = concatMap f m
return x = [x]
fail s = []

What's not at all obvious from any of the above signatures, or any of the existing tutorials, is that the monad that the function f returns, must be the same monad type. If you're in the list monad, f must return a new instance of the list monad. If you're in the identity monad, f must return a new instance of the identity monad. This simple fact eluded me for quite some time, and explains why the monad interface cannot be expressed in C#. We can still program using monads, but the interface can't be enforced by the type system.

So without further ado, here is the Identity monad in C#:
public class Identity<T> : Monad<T>
{
T value;

public Identity(T t)
{
value = t;
}
public Identity<B> Bind<B>(Fun<T, Identity<B>> f)
{
return f(value);
}
}
The Monad<T> base class is actually empty, so it's just a marker interface. For those of you unfamiliar with the "Fun" delegate, it's just one of the many standard delegates I use for function signatures in my FP# library. Here is the List monad in C#:
public class ListMonad<T> : Monad<T>
{
protected List.t<T> l;

public ListMonad(T t)
{
l = t;
}

public ListMonad()
{
l = List.Nil<T>();
}

public ListMonad<B> Bind<B>(Fun<T, ListMonad<B>> f)
{
return new ListMonad<B>(
List.MapFlat<T, B>(
l, delegate(T t) { return f(t).l; }));
}
}

Note that all of these monads in C# share a common structure. They have at least one constructor used to wrap a value (called 'return' earlier), and they all have a Bind method which operates on the value encapsulated in the monad, and maps it to a new instance of the monad. Since we have such a similar structure, is there a way to declare an interface or an abstract base class declaring the signature for the Bind method?

Unfortunately not, because C# cannot abstract over type constructors. If it could, the abstract monad class and the Identity monad would look something like:
public abstract class Monad<M,T> where M : Monad
{
public abstract M<M, R> Bind<R>(Fun<T, M<M, R>> f);
}
public sealed class Identity<T> : Monad<Identity,T>
{
...
public override Identity<R> Bind<R>(Fun<T, Identity<R>> f)
...
}

Note the two emphasized sections: the class constraint on Monad, and the type parameter Identity provides to Monad when inheriting from it. They are both used without a type argument. This is illegal in C#/.NET, but it's perfectly legal in languages with more powerful type systems, such as those with "kinds". Identity<int> has kind *, while Identity without a type argument has type *⇒*, ie. a function that constructs a type of kind * when given a type of kind *. This is why monads are not so easily translated into languages like C#.

Coming soon, a real example of using monads in C#?

Comments

What's not at all obvious from any of the above signatures, or any of the existing tutorials, is that the monad that the function f returns, must be the same monad type.

It is obvious from the signatures, if you know how to read Haskell types! Most tutorials about monads in Haskell understandably consider that a prerequisite.
Sandro Magi said…
Fair enough. Of course, most things look obvious in retrospect. ;-)

I've used OCaml extensively in the past, but never Haskell, so I only have a superficial familiarity with it. I couldn't find any monad tutorials in OCaml, a single poor one in Java, and none in C# last time I checked. I see there's a good one here that was just posted. Perhaps I should brush off the old OCaml skills and write one up.
James Iry said…
One point to make (which I haven't yet made in my own monad tutorial series for Scala) is that if your language supports subtypes then your language's usual co- and contravariance rules apply as well.
You can implement them in Ocaml using a signature:

module type MONAD =
sig
     type 'a t
     val unit : 'a -> 'a t
     val bind : ('a -> 'b t) -> 'a t -> 'b t
end
Albert Y.C. Lai said…
I think I see why you didn't find it obvious. You were thinking

class Monad<A> {
...
Monad<B> bind<B>(Fun<A, Monad<B>> f)
}

This would suggest that at different occurrences of Monad, you could plug in different versions of Monad, as that is a main point of OOP.

But it is a confused translation. In the real signature

m a → (a → m b) → m b

m is just as type-variable as a and b. If you translate a to <A> and b to <B>, you should also translate m to <M>, not fixate it to Monad.

If only C# allowed you to write something like

class <M><A> {
...
<M><B> bind<B>(Fun<A, <M><B>> f)
}

you would think that obviously all three M's are to be "synchronized", just as it is obvious to all C# readers that all three B's are to be "synchronized".
Sandro Magi said…
That, and confused wording like in the wikipedia article I linked to: "A binding operation of polymorphic type (M t)→(t→M u)→M u [...] Its first argument is a value in a monadic type, its second argument is a function that maps from the underlying type of the first argument to another monadic type, and its result is in that other monadic type." The wording implies that the monadic types are or may be different.

Popular posts from this blog

async.h - asynchronous, stackless subroutines in C

The async/await idiom is becoming increasingly popular. The first widely used language to include it was C#, and it has now spread into JavaScript and Rust. Now C/C++ programmers don't have to feel left out, because async.h is a header-only library that brings async/await to C! Features: It's 100% portable C. It requires very little state (2 bytes). It's not dependent on an OS. It's a bit simpler to understand than protothreads because the async state is caller-saved rather than callee-saved. #include "async.h" struct async pt; struct timer timer; async example(struct async *pt) { async_begin(pt); while(1) { if(initiate_io()) { timer_start(&timer); await(io_completed() || timer_expired(&timer)); read_data(); } } async_end; } This library is basically a modified version of the idioms found in the Protothreads library by Adam Dunkels, so it's not truly ground bre

Building a Query DSL in C#

I recently built a REST API prototype where one of the endpoints accepted a string representing a filter to apply to a set of results. For instance, for entities with named properties "Foo" and "Bar", a string like "(Foo = 'some string') or (Bar > 99)" would filter out the results where either Bar is less than or equal to 99, or Foo is not "some string". This would translate pretty straightforwardly into a SQL query, but as a masochist I was set on using Google Datastore as the backend, which unfortunately has a limited filtering API : It does not support disjunctions, ie. "OR" clauses. It does not support filtering using inequalities on more than one property. It does not support a not-equal operation. So in this post, I will describe the design which achieves the following goals: A backend-agnostic querying API supporting arbitrary clauses, conjunctions ("AND"), and disjunctions ("OR"). Implemen

Easy Automatic Differentiation in C#

I've recently been researching optimization and automatic differentiation (AD) , and decided to take a crack at distilling its essence in C#. Note that automatic differentiation (AD) is different than numerical differentiation . Math.NET already provides excellent support for numerical differentiation . C# doesn't seem to have many options for automatic differentiation, consisting mainly of an F# library with an interop layer, or paid libraries . Neither of these are suitable for learning how AD works. So here's a simple C# implementation of AD that relies on only two things: C#'s operator overloading, and arrays to represent the derivatives, which I think makes it pretty easy to understand. It's not particularly efficient, but it's simple! See the "Optimizations" section at the end if you want a very efficient specialization of this technique. What is Automatic Differentiation? Simply put, automatic differentiation is a technique for calcu