Why FL specifies the ChainRec typeclass when there is the trampoline monad?

[ivenmarquardt]

Here is an example of a computation, which is both monadic and recursive. It either yields a result or short circuits and yields nothing, if a single element of the array is nothing.

const maybeSum = xs => {
  const go = (tx, i) =>
    i === xs.length
      ? tx
      : optChain(tx) (acc =>
          optChain(xs[i]) (x => go(optOf(acc + x), i + 1)))

  return go(optOf(0), 0);
};

maybeSum is not stack safe. The recursive step go is in tail position, so we might be inclined to apply a normal trampoline. However, such a trampoline would break the short circuit semantics of the Option monad (runnable example).

AFAIK, making such a computation stack safe only requires a monad, not a new typeclass. Here is the monad instance of the trampoline type:

const monadRec = step => {
    while (step.tag !== Base)
      step = step.f(...step.args);

    return step.x;
};

const Base = x =>
  ({tag: Base, x});

Chain = f => (...args) =>
  ({tag: Chain, f, args});

const recChain = tf => fm =>
  tf.tag === Chain
    ? Chain(args => recChain(tf.f(...args)) (fm)) (tf.args)
    : fm(tf.x);

const recOf = Base;

Given this monad instance we can implement sum using the Option monad transformer:

const optChainT = ({chain, of}) => mmx => fmm =>
  chain(mmx)
    (mx =>
      match(mx, {
        None: _ => of(None),
        Some: ({some: x}) => fmm(x)
      }));

const optOfT = of => x => of(Some(x));

const optRecChain = optChainT({chain: recChain, of: recOf});

const optRecOf = optOfT(recOf);

const sum = xs => {
  const go =
    Chain((tx, i) =>
      i === xs.length
        ? tx
        : optRecChain(tx) (acc =>
            optRecChain(recOf(xs[i])) (x => go(optRecOf(acc + x), i + 1))));

  return go(optRecOf(0), 0);
};

All we need to do is to add the trampoline monad as the innermost monad of our transformer stack. Here is an runnable example.

So what is the motivation behind the ChainRec typeclass when all we need seems to be a new monad instance. Please note that I don't want to imply that there is no good reason for ChainRec. I just cannot see it right now, hence the question. Thank you!

[davidchambers]

Did you answer your own question, @ivenmarquardt?

[ivenmarquardt]

Actually not, @davidchambers. I have continued my study of different forms of monadic recursion and am far from done, Since nobody answered I figured the question was a bit rash.

[davidchambers]

I think it's a good question. I've always found ChainRec confusing, though, so I'm no help. ;)

[safareli]

Maybe take a look at the original issue https://github.com/fantasyland/fantasy-land/issues/151#issue-174171650

for example in PureScript there are instances of MonadRec for many monads https://pursuit.purescript.org/search?q=MonadRec

This example might highlight motivation: https://github.com/purescript/purescript-tailrec/blob/master/src/Control/Monad/Rec/Class.purs#L33-L55

[ivenmarquardt]

OK, will look into that more closely. I figured that purescript just needs it this way, so that the compiler could apply the usual tail call elimination. Then, however, it would be a purescript specific issue.

[safareli]

One of the reasons MonadRec exists is that purescript compiler can't optimize monadic recursion. It can optimize regular tail call recursion into for loop but not monadic.

[ivenmarquardt]

I wonder why PS cannot optimize recursion within a monad when we can write a stack-safe monad instance for the Trampoline type in a principled way. I am not a compiler programmer though.

With Trampoline you can add stack-safety to many transfromer stacks and keep your code DRY. ChainRec on the other hand is probably more efficient. I will use the monad instance for the time being and report here if I ever feel the need for ChainRec.