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#?