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:

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:

Looks simple enough. Now meet Haskell's List monad:

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

So without further ado, here is the Identity monad in C#:

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:

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

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

**. 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.***the same monad type*So without further ado, here is the Identity monad in C#:

public class Identity<T> : Monad<T>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#:

{

T value;

public Identity(T t)

{

value = t;

}

public Identity<B> Bind<B>(Fun<T, Identity<B>> f)

{

return f(value);

}

}

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> whereM : Monad

{

public abstract M<M, R> Bind<R>(Fun<T, M<M, R>> f);

}

public sealed class Identity<T> : Monad<,T>Identity

{

...

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.

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.

module type MONAD =

sig

type 'a t

val unit : 'a -> 'a t

val bind : ('a -> 'b t) -> 'a t -> 'b t

end

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".