Friday, January 18, 2008

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

7 comments:

Philippa Cowderoy said...

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.

Neel Krishnaswami said...

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.

Jonathan Ho said...

This tutorial may be helpful