Required (or at least Opt-In) stack safety for monadic types.

[antagonist112358]

We (one of my teams) is working on a port of the Scala library "doobie" over to C#, and making heavy use of LanguageExt to even begin to make this possible.

Having said that, I was surprised to not find required (or at least opt-in) stack-safety for monads. This is required in Cats for something to be a monad, and opt-in for Scalaz, and giving that recursion is a very common pattern in FP, this seems like a sorely missing feature.

See:

• Cats FlatMap
• ScalaZ's BindRec

Before I start working on a PR for this, I want to check that:

1. You are on-board with the idea in principal and won't reject the PR outright
2. You are OK with opt-in stack safety. I think this is OK, but perhaps given that C# is eager, it should be a required feature of all monads?
3. I'm leaning towards creating a FlatMap<M> and FlatMapRec<M> type classes (a la Scalaz style), and then having Monad<M> extend Bind<M>. In this way, implementors can "opt-in" to declaring their monads "stack safe", by including implementing BindRec<M> (and library implementers can require it as a gen param constraint).
4. Provide an additional law for BindRec<M> that (e.g.) 100,000 left/right nested binds do not blow the stack.
5. I'll implement this for a few of the exiting monads in LanguageExt (Option, IO, Seq).

Rough draft sketch:

using System;

namespace LanguageExt.Traits;

// Applicative without point / pure
public interface FunctorApply<F> : Functor<F> where F : FunctorApply<F>
{
    public static abstract K<F, B> Apply<A, B>(K<F, Func<A, B>> mf, K<F, A> ma);
}

// FlatMap, because `Bind` is taken
public interface FlatMap<M> : FunctorApply<M> where M : FlatMap<M>
{
    public static abstract K<M, B> Bind<A, B>(K<M, A> ma, Func<A, K<M, B>> f);
    
    public new static virtual K<M, B> Apply<A, B>(K<M, Func<A, B>> mf, K<M, A> ma) =>
        M.Bind(mf, f => M.Map(f, ma));
    
    static K<M, B> FunctorApply<M>.Apply<A, B>(K<M, Func<A, B>> mf, K<M, A> ma) =>
        M.Apply(mf, ma);
}

public interface BindRec<M> : FlatMap<M> where M : BindRec<M>
{
    /**
      * Keeps calling <b><i>cont</i></b> until a <see cref="Either{A, B}.Right">Right[B]</see> is returned.
      * <p/>
      * Implementations of this method should use constant stack space (no recursion) relative to `cont`.
      * <remarks>
      * Based on Phil Freeman's
      * [[http://functorial.com/stack-safety-for-free/index.pdf Stack Safety for Free]].
      * </remarks>
      */    
    public static abstract K<M, B> TailRecM<A, B>(A initial, Func<A, K<M, Either<A, B>>> cont);
}

@louthy - thoughts?

[louthy]

I don't really have the bandwidth to get into this right now, but it's the same trampoline principle that's in the IO<A> monad state-machine (although I take the concept much further there).

As I noted in this comment, I'm fully loaded with tasks, and dealing with this feature + replacing all of the core functionality of every monad is reeeeeeally not on my list of desires right now.

I appreciate the offer of help, but this feature (which I will implement at some point), will likely be far too noisy for me to deal with. I'd definitely prefer to attack it myself once I can free up some time.

[louthy]

Some news for you.