Idea: Split MonadIO so that non-MonadT types aren't assumed IO-capable

[hermanda19]

I was reading up on the role of MonadIO and how it enables monad-transformer-stacks to expose their underlying IO monad (if one exists) with static dispatch given C#'s limitations and had a quick thought about how this might be improved.

Since Monad <: MonadIO, all monad kinds are eligible for use as generic arguments in IO-performing methods.

Take this method for example:

public static K<M, Unit> performIO<M>()
    where M : MonadIO => 
    M.LiftIO(/* Some IO<Unit> operation. */);

Unfortunately, despite monads like Option and Fin definitely not wrapping IO, this method is still callable for those types.
This results in an error at run time instead of compile time.

performIO<Option>(); // throws LiftIO not supported
performIO<Fin>();    // throws LiftIO not supported

How about extracting out the monad-transformer-required methods from MonadIO into a new MonadMaybeIO interface?
I imagine the inheritance chain would like this:
MonadT <: MonadIO <: Monad <: MonadMaybeIO
IO <: MonadIO
Option <: Monad

With this setup, MonadIO indicates a stronger likelihood of supporting IO operations than MonadMaybeIO.
My example performIO method would therefore fail to compile in more cases:

performIO<Option>(); // Option does not implement `MonadIO`
performIO<Fin>(); // Fin does not implement `MonadIO`
performIO<IO>();
performIO<IdentityT<IO>>();
performIO<IdentityT<Option>(); //throws LiftIO not supported

Additionally, this should exclude MonadIO extension methods from IDE suggestions for these types since they're not applicable.

Unfortunately, this doesn't improve the situation for MonadT types. However, maybe it's worth it for the Monad types alone? I imagine transformer-stacks will commonly be wrapped by a domain-monad and so can explicitly choose to implement MonadIO or not depending on whether their underlying transformer-stack contains IO and thus benefit from this extra type-safety.

[louthy]

I don't see how this improves anything really? If I have a ReaderT<E, IO, A> then it won't support the MonadIO trait, so performIO couldn't be called if the M was a ReaderT<E, IO>, that would be pretty bizarre behaviour. IO based transformers not being allowed in MonadIO constraining functions is a non-starter IMHO.

The reason for the compromise is that an exception on first-usage is the least-worst option and really isn't that much worse than a type-check failure. It's certainly not as elegant, but it doesn't bury time-bombs in the code (like null for example). I tried a number of different solutions, but I always ended up being backed into a corner by C#'s type-system, unfortunately.

Here's a minimal standalone version if anyone wants to experiment. I'd love to solve this in a general way, if possible. My gut is that there's probably a 'double dispatch' technique that would make it work generally (like the OO visitor pattern). I just never quite got the mechanics clear in my mind.

var mr = from x in ReaderT<string, IO>.Pure(1)
         from y in ReaderT<string, IO>.Pure(2)
         from z in MonadIO.liftIO<ReaderT<string, IO>, int>(IO.Pure(3).As())
         select x + y + z;

public static class LINQExtensions
{
    public static K<F, B> Map<F, A, B>(this K<F, A> ma, Func<A, B> f) 
        where F : Functor<F> =>
        F.Map(f, ma);
    
    public static K<F, B> Select<F, A, B>(this K<F, A> ma, Func<A, B> f) 
        where F : Functor<F> =>
        F.Map(f, ma);
    
    public static K<F, B> Apply<F, A, B>(this K<F, Func<A, B>> mf, K<F, A> ma) 
        where F : Applicative<F> =>
        F.Apply(mf, ma);
    
    public static K<M, B> Bind<M, A, B>(this K<M, A> ma, Func<A, K<M, B>> f) 
        where M : Monad<M> =>
        M.Bind(ma, f);
    
    public static K<M, C> SelectMany<M, A, B, C>(this K<M, A> ma, Func<A, K<M, B>> f, Func<A, B, C> g) 
        where M : Monad<M> =>
        ma.Bind(a => f(a).Map(b => g(a, b)));
}

public record IO<A>(Func<A> runIO) : K<IO, A>;

public static class IOExtensions
{
    public static IO<A> As<A>(this K<IO, A> ma) =>
        (IO<A>)ma;
}
    
public class IO : MonadIO<IO>
{
    public static K<IO, B> Map<A, B>(Func<A, B> f, K<IO, A> fa) =>
        new IO<B>(() => f(fa.As().runIO()));

    public static K<IO, A> Pure<A>(A x) =>
        new IO<A>(() => x);

    public static K<IO, B> Apply<A, B>(K<IO, Func<A, B>> ff, K<IO, A> fa) =>
        new IO<B>(() => ff.As().runIO()(fa.As().runIO()));

    public static K<IO, B> Bind<A, B>(K<IO, A> ma, Func<A, K<IO, B>> f) =>
        new IO<B>(() => f(ma.As().runIO()).As().runIO());

    public static K<IO, A> LiftIO<A>(IO<A> io) =>
        io;
}

public record ReaderT<E, M, A>(Func<E, K<M, A>> runReader) : K<ReaderT<E, M>, A>
    where M : Monad<M>
{
    public K<ReaderT<E, M>, A> AsLower() =>
        this;
}

public static class ReaderExtensions
{
    public static ReaderT<E, M, A> As<E, M, A>(this K<ReaderT<E, M>, A> ma)
        where M : Monad<M> =>
        (ReaderT<E, M, A>)ma;
}

public class ReaderT<E, M> : MonadT<ReaderT<E, M>, M>
    where M : Monad<M>
{
    public static K<ReaderT<E, M>, B> Map<A, B>(Func<A, B> f, K<ReaderT<E, M>, A> fa) =>
        new ReaderT<E, M, B>(e => fa.As().runReader(e).Map(f));

    public static K<ReaderT<E, M>, A> Pure<A>(A a) =>
        new ReaderT<E, M, A>(_ => M.Pure(a));

    public static K<ReaderT<E, M>, B> Apply<A, B>(K<ReaderT<E, M>, Func<A, B>> ff, K<ReaderT<E, M>, A> fa) =>
        new ReaderT<E, M, B>(e => ff.As().runReader(e).Apply(fa.As().runReader(e)) );

    public static K<ReaderT<E, M>, B> Bind<A, B>(K<ReaderT<E, M>, A> ma, Func<A, K<ReaderT<E, M>, B>> f) =>
        new ReaderT<E, M, B>(e => ma.As().runReader(e).Bind(a => f(a).As().runReader(e)));

    public static K<ReaderT<E, M>, A> Lift<A>(K<M, A> ma) =>
        new ReaderT<E, M, A>(_ => ma);
}

public static class MonadIO
{
    public static K<M, A> liftIO<M, A>(IO<A> ma)
        where M : MonadIO<M> =>
        M.LiftIO(ma);
}

public interface K<in F, A>;

public interface Functor<F>
    where F : Functor<F>
{
    public static abstract K<F, B> Map<A, B>(Func<A, B> f, K<F, A> fa);
}

public interface Applicative<F> : Functor<F>
    where F : Applicative<F>
{
    public static abstract K<F, A> Pure<A>(A a);
    public static abstract K<F, B> Apply<A, B>(K<F, Func<A, B>> ff, K<F, A> fa);
}

public interface MaybeMonadIO<in M>
    where M : MaybeMonadIO<M>
{
    public static virtual K<M, A> LiftIO<A>(IO<A> io) =>
        throw new NotImplementedException();
}

public interface Monad<M> : Applicative<M>, MaybeMonadIO<M>
    where M : Monad<M>
{
    public static abstract K<M, B> Bind<A, B>(K<M, A> ma, Func<A, K<M, B>> f);
}

public interface MonadIO<M> : Monad<M>
    where M : MonadIO<M>;

public interface MonadT<T, M> : Monad<T> 
    where T : MonadT<T, M>
    where M : Monad<M>
{
    public static abstract K<T, A> Lift<A>(K<M, A> ma);
}

[hermanda19]

Thanks for considering! However, I think you misunderstood me. Specifically, my proposal for this inheritance chain:

MonadT <: MonadIO <: Monad <: MonadMaybeIO

According to this, MonadT in your example should inherit from MonadIO and not Monad:

public interface MonadT<T, M> : MonadIO<T>
    where T : MonadT<T, M>
    where M : Monad<M>
{
    public static abstract K<T, A> Lift<A>(K<M, A> ma);
}

Of course, this still throws an exception if MonadT isn't wrapping IO in its stack, but I admit as much in my original post:

Unfortunately, this doesn't improve the situation for MonadT types. However, maybe it's worth it for the Monad types alone?

I hope it's now clear what I meant!

[hermanda19]

EDIT: Changed N to B for better visual clarity when adjacent to M and to serve as a more intuitive abbreviation: T for top, M for middle, and B for bottom.

EDIT: Replaced ReaderT<E, T, M, B>.Lift with default implementation from MonadT<T, M, B>.

Here's a minimal standalone version if anyone wants to experiment. I'd love to solve this in a general way, if possible.

So, I've been thinking about this since and I think I've come up with, at least, a framework for how full type-safety could be achieved.
Of course, it's not without its own tradeoffs, but I'll get into that.

The main idea is this: what if we treat monads as trivial monad transformers of themselves?

Forget about the current MonadT definition and consider this one instead:

public interface MonadT<M, B> : Monad<M>
    where M : MonadT<M, B>
    where B : MonadT<B, B> // B is a transformer of itself!
{
    public static abstract K<M, A> Lift<A>(K<B, A> ma);
    // case M: Lifts B into M. Standard monad transformer behavior.
    // case B: Lifts B into B! Equivalent to the identity function.
}

Now, let's implement this for the IO monad:

public class IO : MonadT<IO, IO> // IO is a transformer to itself!
{
    public static K<IO, A> Lift<A>(K<IO, A> ma) => ma;
    // This is just IO's current MonadIO.LiftIO() implementation!
}

So far, so good. However, this MonadT implementation limits B to be a "trivial transformer". As a consequence, it only supports a single level of transformer nesting, which is far too limiting.

So, let's introduce an additional MonadT interface:

public interface MonadT<T, M, B> : MonadT<T, B>
    where T : MonadT<T, M, B> // top-level
    where M : MonadT<M, B>    // intermediate transformers
    where B : MonadT<B, B>    // base monad
{
    public static abstract K<T, A> LiftT<A>(K<M, A> ma);
    // Lifts the smaller transformer, M, into the larger transformer, T.
    // Importantly, the base monad, B, is the same for both!

    static K<T, A> MonadT<T, B>.Lift<A>(K<B, A> ma) =>
        T.LiftT(M.Lift(ma));
}

Putting this all together, we can reimplement ReaderT like so:

public record ReaderT<E, M, B, A>(Func<E, K<M, A>> runReader) : K<ReaderT<E, M, B>, A>;

public class ReaderT<E, M, B> : MonadT<ReaderT<E, M, B>, M, B>
    where M : MonadT<M, B>
    where B : MonadT<B, B>
{
    public static K<ReaderT<E, M, B>, A> LiftT(K<M, A> ma) =>
        new ReaderT<E, M, B>(e => ma);
}

What all this essentially does is encode the base monad into the type signature of every monad transformer. This allows us to write where clauses which ensure that the monad sitting at the bottom of any stack is a particular type. Therefore, we can define liftIO() with complete type-safety like so:

public static class MonadIO
{
    public static K<T, A> LiftIO<T, A>(IO<A> ma)
        where T : MonadT<T, IO> => // Only type-checks if IO is the base monad of T!
        T.Lift(ma);
}

Pretty cool, huh? There are downsides to this approach, though; So, let's take a look:

The Good

All MonadIO operations can be checked at compile time regardless if using a monad or monad-transformer. My original proposal only checks monads at compile time; so, this is an improvement in that regard.

The Bad

In this design, monad-transformers simply don't work with Monad types! The base monad must implement MonadT instead, which is an extra requirement that the existing system does not have.

On the bright-side, I would expect all monads provided by this library to implement this trait anyway. For a custom monad defined by a user, implementing this trait is trivial since it's just the identity function. However, in the rare case a user needs to use a custom monad they don't control (provided by some third-party library) that doesn't implement MonadT (for whatever reason), we can define a wrapper type that does implement it for any Monad.

The Ugly

This requires every MonadT type to carry around an extra generic type parameter to represent the monad-transformer stack sitting between the top-level transformer and the base monad. On top of that, it requires an additional MonadT interface with more complicated where bounds.

At least you only have to define it once?

Conclusion

I'm not advocating for this design exactly as I've presented it per se, nor am I completely confident that its benefits outweigh its downsides. However, even if it turns out to be insufficient, I hope this idea can maybe inspire a better solution overall. At the very least, I wanted to get this out of my head and into writing!

[louthy]

I've already done it. It's on the 'streaming' branch. Was going to write it up fully later today.

Edit: just noticed your different approach. I'm away from my pc right now, I'll take a look later

[louthy]

I decided this was a bit too generics heavy, so decided to not go with it. However, the original idea is now released.

[hermanda19]

Fair's fair! I suspected as much. Thanks for your consideration anyway! It was at least fun to work out on my own end!