TailRecM

[waynevanson]

🚀 Feature request

Current Behavior

Desired Behavior

Stack safe tail recursion that can be applied to a Monad.

Prior art is the member "tailRecM" under Purescript's MonadRec class

Suggested Solution

import { either as E } from "fp-ts";
import { pipe } from "fp-ts/lib/function";
import { Kind2, URIS2 } from "fp-ts/lib/HKT";
import { Monad2 } from "fp-ts/lib/Monad";

/**
 * @summary
 * Tail recursion via Monad.
 *
 * **note:** not stack safe
 */
export const tailRecM =
  <M extends URIS2>(M: Monad2<M>) =>
  <E, A, B>(f: (a: A) => Kind2<M, E, E.Either<A, B>>) =>
  (fa: Kind2<M, E, A>): Kind2<M, E, B> =>
    pipe(M.chain(fa, f), (fea) =>
      M.chain(
        fea,
        E.fold(
          (a) => tailRecM(M)(f)(M.of(a)),
          (b) => M.of(b)
        )
      )
    );

Who does this impact? Who is this for?

Users who need performance and safety in their recursive operations.

Describe alternatives you've considered

Additional context

When consumers need a stack safe version, they could perhaps implement a stack safe version for a particular monad. I'm using StateTask with this and haven't run into stack issues yet.

Your environment

Software	Version(s)
fp-ts	2.10.5
TypeScript	4.3.5

[gcanti]

Looks like ChainRec

[waynevanson]

You're right, it is. I didn't check.

The difference is that this is a default implementation that can create a chainRec from a Monad (or some members of a Monad instance).

Should yhis default factory be added, or instead add sane chainRecs for those classes that allow it?

[mikearnaldi]

It's not stack safe, tailRecM is implemented recursively which means any sync execution will make it unsafe, it is safe when used in combo with task because task is safe

[waynevanson]

It's not stack safe, tailRecM is implemented recursively which means any sync execution will make it unsafe, it is safe when used in combo with task because task is safe

Are you sure that's correct? It's a thunk which returns a function, so I would think with or without the promise it would be unsafe.

[mikearnaldi]

Unless I am missing something it is not stack safe it is a plain recursive function, in tailRec safety is achieved implementing the logic in an iterative manner https://github.com/gcanti/fp-ts/blob/master/src/ChainRec.ts#L73 but in the case of a generic monad you can't really do that