StateT1 ChainRec

[waynevanson]

The M: ChainRec must handle trampolining to ensure there is no stack overflow.

I may revisit this if I figure out a better way.

import { either as E, stateT as ST } from "fp-ts"
import { URIS } from "fp-ts/HKT"
import { ChainRec1 } from "fp-ts/lib/ChainRec"
import { pipe } from "fp-ts/lib/function"

export const chainRec =
  <F extends URIS>(M: ChainRec1<F>) =>
  <S, A, B>(
    a: A,
    f: (a: A) => ST.StateT1<F, S, E.Either<A, B>>,
  ): ST.StateT1<F, S, B> =>
  (s) =>
    M.chainRec([a, s] as const, ([a, s]) =>
      M.map(f(a)(s), ([ea, s]) =>
        pipe(
          ea,
          E.bimap(
            (e) => [e, s] as const,
            (a) => [a, s],
          ),
        ),
      ),
    )