Add ChainRec type class

[safareli]

TailRec - A type class which captures stack-safe monadic tail recursion.

It would be nice to have a common specification for Tail Recursive Monads in JS community, so that libraries like Free could use the interface to be stack safe.

in PS MonadRectype class looks like this:

class Monad m <= MonadRec m where
  tailRecM :: forall a b. (a -> m (Either a b)) -> a -> m b

So we could have something like this without stack overflow:

Identity.tailRecM((n) => {
  if (n == 0) {
    return Identity(Either.Right("DONE"))
  }
  return Identity(Either.Left(n - 1))
})(20000)

one thing is that there are multiple Either implementations in js and this spec should depend on bare minimum from any Either type. from what I have found the minimum api from Either type is to have a cata method. but before that let's see an implementation of tailRecM of Identity:

const tailRec = (f) => (a) => {
  let v = f(a)
  while (!isDone(v)) {
    v = f(getValue(v))
  }
  return getValue(v)
}

const runIdentity = (i) => i.x

Identity.tailRecM = (f) => (a) => Identity(tailRec((v) => runIdentity(f(v)))(a))

So we have seen usage of it and part of it's implementation. now what we have left is implement isDone and getValue so that they are as generic as possible.

const isDone = (e) => e.cata({
  Right: () => true,
  Left: () => false,
})

const getValue = (e) => e.cata({
  Right: (v) => v,
  Left: (v) => v,
})

so as it looks any Either with cata would work so users shouldn't be tied to some particular Either implementation (as long as it has cata).
To note this Either implementation would work with tailRecM.

const Either = {
  Right: (v) => ({ cata: (c) => c.Right(v) }),
  Left: (v) => ({ cata: (c) => c.Left(v) }),
}

---

The hardest was to implement tailRecM for Task/Future but i have made it and after we agree on some interface I would create PRs for some popular Task/Future implementations

[safareli]

@paf31 @garyb your suggestions will be helpful on this

[scott-christopher]

Regarding Either, a generic interface could be defined using a church-encoded representation:

type Either a b = forall c. (a -> c) -> (b -> c) -> c

Such that

const Left  = x => (whenLeft, whenRight) => whenLeft(x)
const Right = x => (whenLeft, whenRight) => whenRight(x)

So you're Identity example could look like:

const tailRec = (f) => (a) => {
  let state = { done: false, value: a }
  while (!state.done) {
    f(state.value)(
      x => { state.value = x },
      x => { state.value = x, state.done = true }
    )
  }
  return state.value
}

/* other bits remain the same */

Identity.tailRecM((n) => {
  if (n == 0) {
    return Identity((_, done) => done("DONE"))
  }
  return Identity((next, _) => next(n - 1))
})(20000)

[safareli]

The church notation is basically a fold method of Either.
I think it would be great if one could use any of Either implementations (data.either, fantasy-eithers....). For that tailRecM should depend on minimal api so it's as easy to use as possible. With the church notation user should write their own implementation of Either (those two functions Left/Right). I have show sample implementation of Either to demonstrate that tailRecM just needs cata (or possiblyfold)

[SimonRichardson]

I would love to see the usage of fold, it's more generalised imo.

Also 👍 on this.

[rpominov]

What if instead of relying on an unified Either interface the type itself would provide methods that would create Type(Left(a)) and Type(Right(a)) values?

So usage would look something like this:

Identity.tailRecM((n) => {
  if (n == 0) {
    return Identity.tailRecurDone("DONE")
  }
  return Identity.tailRecurNext(n - 1)
})(20000)

tailRecurDone and tailRecurNext names is just first what came to my mind, we could came up with better ones.

One reason why this might be a better approach is because many Future/Task implementations have built-in Either.

[safareli]

With fold, isDone and getValue would change to:

const isDone   = (e) => e.fold(() => false, () => true)
const getValue = (e) => e.fold((v) => v, (v) => v)

[SimonRichardson]

Folds all the way down.

[safareli]

@rpominov that's also interesting.
user of some Type.tailRecM might not even use Either (most likely they do use thou).
If every type conforming TailRec interface have there own two line Either implementations that would also do a trick.

something like this?:

Identity.tailRecM((n) => {
  if (n == 0) {
    return Identity.tailRecM.done("DONE")
  }
  return Identity.tailRecM.next(n - 1)
})(20000)

Also, the advantage is that, user doesn't need to care if Left does recursion of Right when done and next explicitly state what they do.

[SimonRichardson]

This is very reminiscent of a trampoline and has worked well there already, so I'm not against that idea either.

[safareli]

In the sense of accessibility, using done/next is better for newcomers, and even ones who understand Either, might get confused which one to use for looping/returning.

So now question is, which one should be used:

a	b
Identity.tailRecMNext	Identity.tailRecM.next
Identity.tailRecMDone	Identity.tailRecM.done

[SimonRichardson]

b imo.

[scott-christopher]

In the sense of accessibility, using done/next is better for newcomers, and even ones who understand Either, might get confused which one to use for looping/returning.

Another option would be to provide the Left & Right constructors as arguments to the function given to tailRecM.

tailRecM :: MonadRec m => (a -> (b -> Either b c) -> (c -> Either b c) -> m (Either a a)) -> a -> m a

Which would look like the following to a user:

Identity.tailRecM((n, next, done) => n == 0 ? done("DONE") : next(n - 1))(20000)

This has the advantage of avoiding naming things all together, though at the expense of being a little more difficult to describe in the spec.

[rjmk]

If we want to avoid the 2-line Either duplication, I think it would also be possible to change the signature like this

tailRecM
  :: MonadRec m => ((a1 -> c1) -> (b1 -> c1) -> Either a1 b1 -> c1)
  -> (a -> m (Either a b)) -> a -> m b

-- Can we replace `Either` with a variable `t` here?

i.e. provide the fold to tailRecM.