TailRecM in Language ext

[cheerio-pixel]

Something that I miss from scala is that all monads there implement the function tailRecM which translated to csharp would be like K<M, B> TailRecM<A, B>(A seed, Func<A, K<M, Either<A, B>>> f). This function allows for definitions like recursive monads that do not blow up the stack. For example, forever (which I know already exists as repeat):

    public static K<M, B> ForeverM<A, B>(K<M, A> ma) {
        var cachedLeft = Left<A, B>(default);
        return M.TailRecM<A, B>(default!, _ => ma.Map(_ => cachedLeft));
    }

Accumulate results:

    public static K<M, IEnumerable<A>> AccumulateUntilM<M, A>(K<M, A> ma, Func<A, bool> f)
        where M : TailRecMonad<M>
        => M.TailRecM(new List<A>() as IEnumerable<A>, acc =>
                M.Map<A, Either<IEnumerable<A>, IEnumerable<A>>>(
                    a => f(a) ?
                    Right(acc) :
                    Left(acc.Append(a)),
                    ma
                    )
                );

Or Accumulate N times

    public static K<M, IEnumerable<A>> ReplicateM<M, A>(K<M, A> ma, int count)
        where M : TailRecMonad<M>
        => count <= 0 ?
        M.Pure(new List<A>() as IEnumerable<A>)
        : M.TailRecM<(IEnumerable<A>, int), IEnumerable<A>>(
                (new List<A>(), count),
                pair =>
                M.Map<A, Either<(IEnumerable<A>, int), IEnumerable<A>>>(
                    x => pair.Item2 <= 1 ?
                    Right(pair.Item1.Append(x)) :
                    Left((pair.Item1.Append(x), pair.Item2 - 1)),
                    ma
                    )
                );

I found this function necessary when I was working through the Redis challenge of codecrafters, so I wanted to discuss if this would be a nice addition for all monads in the core library

[louthy]

If you use IO<A> or have IO in your monad-transformer stack (Streams example) you get this for free as it has a trampoline built in to its internal DSL.

But, yes, I can see value to generalising the idea. I'll look into it when I'm back full time on lang-ext.