An Almost Type-Safe General Monad in C#, aka how to Abstract over Type Constructors using Dynamics

Extending the work in my last post, I've developed a way to express an almost type-safe, general monad in C#. Similar to my module translation, the single monad object becomes a pair of co-operating objects, only one of which the monad implementor must define. Since C# cannot abstract over type constructors, I had to exploit the only feature that could accomodate the flexibility I needed: C#'s dynamic typing.

// The Monad object, indexed by a singleton type that implements the
// monad operations.
public sealed class Monad<M, T>
        where M : struct, IMonadOps<M> { ... }

// An object that implements operations on the monad's encapsulated
// state.
public interface IMonadOps<M>
   where M : struct, IMonadOps<M>
{
   /// Return the encapsulated state for the monad's zero value.
   object Zero<T>();

   // Return the encapsulated state for the 'unit' operation.
   object Unit<T>(T t);

   // Perform a bind operation given the monad's encapsulated state,
   // and the binding function f.
   Monad<M, R> Bind<T, R>(
     object state,
     Fun<T, Monad<M, R>> f,
     Fun<Monad<M, R>, object> from,
     Fun<object, Monad<M, R>> to);
}

Looks a bit complicated, I know, but every piece is well-motivated. IMonadOps is fortunately the only interface that new monads must implement. Note the type constraints. The interface and the general monad both have a "phantom" or "witness" type M, constraining the type of the monad operations to the same IMonadOps type that created the monad. This means that the monad is entirely closed to extension and inspection.

Each IMonadOps is effectively a stateless singleton. The constraint to a struct is merely an optimization. Every IMonadOps implementor is actually very similar to the body of an ML module. If I want to invoke Identity.Zero, I can do it thusly:

default(Identity).Zero<int>();

This reveals the magic I used to define the Monad type. Whenever the Monad<M,T> type needs to invoke the underlying monad operations, it invokes the operation on the corresponding singleton M just like the above. Indexing the Monad by an IMonadOps implementation M, is like a linking step between Monad and M.

public sealed class Monad<M, T>
    where M : struct, IMonadOps<M>
{
    object state;

    Monad(object state)
    {
        this.state = state;
    }

    // The projection function.
    static object get<R>(Monad<M, R> m)
    {
        return m.state;
    }

    // The injection function.
    static Monad<M, R> ctor<R>(object state)
    {
        return new Monad<M, R>(state);
    }

    // The standard 'bind' operation. It dispatches to the
    // type-indexed 'bind', defined by M.
    public Monad<M, R> Bind<R>(Fun<T, Monad<M, R>> f)
    {
        return default(M).Bind<T, R>(state, f, get<R>, ctor<R>);
    }

    // The standard 'unit' operation, injecting a value into
    // the monad. It dispatches to the type-indexed unit
    // function defined by M.
    public static Monad<M, T> Unit(T t)
    {
        return new Monad<M, T>(default(M).Unit<T>(t));
    }

    public static Monad<M, T> Zero()
    {
        return new Monad<M, T>(default(M).Zero<T>());
    }
}

You can see the dispatching at work here. All monad operations are dispatched to the "linked" methods of M. In a sense, we have succeeded in abstracting over the concrete implementation of Monad.

Now comes the catch: it's not fully type-safe, because the encapsulated state of the monad must be stored as 'object'. This means that each monad body must ensure it properly casts to and from the appropriate type. This is again due to the type constructor abstraction limitation.

Your first thought might be, why can't the encapsulated state simply be 'T'? Well, if all you wanted was an Identity monad, then that would be fine. But consider the Maybe monad:

public struct Maybe : IMonadOps<Maybe>
{
    public object Unit<T>(T t)
    {
        return new Option<T>(t);
    }

    public object Zero<T>()
    {
        return new Option<T>();
    }

    public Monad<Maybe, R> Bind<T, R>(
      object state,
      Fun<T, Monad<Maybe, R>> f,
      Fun<Monad<Maybe, R>, object> from,
      Fun<object, Monad<Maybe, R>> to)
    {
        Option<T> value = (Option<T>)state;
        return (value.HasValue) ? f(value.Value) : Fail<R>();
    }

    public static Monad<Maybe, T> Fail<T>()
    {
        return Monad<Maybe, T>.Zero();
    }
}

The encapsulated state is an Option of type T, not a T. As another example, the List monad encapsulates a list of T's. Since we can't abstract over the type constructor for the encapsulated state, we thus need to resort to dynamic typing.

Now comes a slightly bizarre part: what are the injection and projection functions for? Well, despite the fact that IMonadOps is the "internal implementation" of Monad, it doesn't have direct access to the monad's internals. Unfortunately, sometimes that access is needed. Consider the List monad:

public struct ListM : IMonadOps<ListM>
{
    public object Unit<T>(T t)
    {
        return List.Cons<T>(t, List.Nil<T>());
    }

    public object Zero<T>()
    {
        return List.Nil<T>();
    }

    public Monad<ListM, R> Bind<T, R>(
      object state,
      Fun<T, Monad<ListM, R>> f,
      Fun<Monad<ListM, R>, object> from,
      Fun<object, Monad<ListM, R>> to)
    {
        return to(
            List.MapFlat<T, R>(
                state as List.t<T>, delegate(T t)
                {
                    return from(f(t)) as List.t<R>;
                }));
    }
}

ListM needs access to the private state of the returned list of Monads in order to flatten the list, but that access is not permitted since Monad is a separate, encapsulated type. There is no way to make this state available using inheritance or access modifiers, without also permitting the state to escape inadvertently.

Instead, the Monad provides an injection/projection pair, which are used to construct monad instances when given private state, or read out the private state of a monad instance, respectively. Note that encapsulation is maintained since this ability is granted only to the implementor of a given monad, which is already trusted with its own state.

I suspect there's a more efficient way to share the monad's state, but I'm a little tired from standing on my head all day for C#, so if anyone has any ideas, I welcome them. :-)

While this encoding is less efficient than the one described in my previous post, it's safer in some ways for users monad implementors alike, and I proved to myself that C#'s type system is powerful enough to encode the monad interface if you contort yourself appropriately. This technique for abstracting over type constructors might even be usable in my tagless Orc implementation.