Support for generalised monad tail-recursion

[louthy]

Quite a big release here. It's not had a huge amount of testing, but thought it would be good to get it out before I disappear for Christmas, in case anyone wants to have a play with the new features.

Monad.Recur

As suggested here and at various times over the years, we could support the same tailRecM pattern as seen in Cats and Scalaz libraries from the Scala ecosystem. I have been a little sceptical of the approach, mostly because it forces the user to manually trampoline. I wasn't keen on going all in, but then I woke up Saturday morning thinking about it (that's how sad my life is) and felt inspired to implement it.

150+ file changes later and we now have support. tailRecM in Scala becomes Monad.recur in language-ext. Every monad is expected to implement the Monad.Recur trait method, but you could also use the placeholder function (Monad.unsafeRecur) that still uses regular recursion. This is because:

• Sometimes it's not important to implement it right now
• It's not always trivial to implement and you may struggle to do so for certain monadic-types
• Some monads may already have their own trampoline built-in (like IO<A>), so using regular recursion is fine

There's also two other helper functions: Monad.iterableRecur and Monad.enumerableRecur which are default Monad.Recur implementations for collections.

You're unlikely to need recursion for collections anyway, because it'd be like the most insanely nested set of for-loops ever. But, technically you could have lots of singleton lists that blow a stack in a recursion scenario, so these helper functions save you the hassle of working out how to unfold a recursive bind on collections.

Here's the implementation of Monad.Recur for Option:

static K<Option, B> Monad<Option>.Recur<A, B>(A value, Func<A, K<Option, Next<A, B>>> f)
{
    while (true)
    {
        var mr = +f(value);
        if (mr.IsNone) return Option<B>.None;
        var mnext = (Next<A, B>)mr;
        if(mnext.IsDone) return Some(mnext.Done);
        value = mnext.Loop;
    }
}

If you're wondering what the prefix + operator is, it's the downcast-operator from K<Option, A> to Option<A>. Like calling f(value).As(), just more elegant.

What's really nice about this implementation is how 'light' it is. It's a simple while-loop with a test to see if we're done: if(mnext.IsDone) or a continuation-value (mnext.Loop) to be passed to the 'bind' function f. As well as the standard Option monad-bind logic of earlying-out when in a None state.

There were two reasons I decided to ignore my earlier concerns about this approach and this is one of them: Option is a struct and is designed to be a lightweight data-type. The only other way to support recursion would have been to make it into an interpreter style monad (like the IO monad) which would bring more overhead where we don't want it. So, this manual opt-in to recursion when you need it and the subsequent tight while-loop makes recursion with simple data-monads very effetive.

It's certainly not very elegant in C#, I would mostly advise using maps, folds, and traversals (where possible). But there's always that one time where recursion would be better, so now you can guarantee its safety.

I still want to build support for tail-recursion into the 'control' monads (those that are lazy computations and therefore can be backed by an interpreted DSL. I still believe that's more effective and elegant.

Iterable now supports IAsyncEnumerable

So Iterable which started life as a wrapper for IEnumerable now supports both synchronous and asynchronous lazy streams. This is continuing the goal of killing Task and async/await. Only when you use an Iterable do you care how you consume it. If you want asynchronicity then you can either call AsAsyncEnumerable() or use any of the *IO suffixed methods (like CountIO, FoldIO, etc.)

IterableNE is a new non-empty Iterable

Every wanted to work with a lazy stream that must have at least one item in it? Well, now you can: IterableNE. It's impossible for an IterableNE to be constructed without at least one item in it, so you can assume it will always have a Head value.

It also supports synchronous and asynchronous sequences.

Applicative.Actions in the Applicative trait updated

There were previously two methods:

Applicative.Actions(IEnumerable)
Applicative.Actions(IAsyncEnumerable)

Now there's one

Applicative.Actions(IterableNE);

Actions would previously throw exceptions with empty sequences.

Monad bind operator

Previous change to change the monad bind operator from >> to >>>` have been reverted. It just didn't 'feel' right, so we're back to where we were.

Lots of other minor tweaks

There are lots of other minor tweaks, but it's now 1am on Christmas day, so I'm going to stop typing! Happy (belated) Hanukkah, Merry Christmas, and/or Happy Holidays to you all.

---

This discussion was created from the release Support for generalised monad tail-recursion.