Do we need R.trampoline for tail-call elimination?

[semmel]

Recursive functions are integral to FP.

8 years after ES6, Tail-Call Elimination is just supported by WebKit — so on Safari and Bun JS runtimes.
On other runtimes, trampoline is needed to avoid stack overflow errors.

Since it would be a great use-case for R.thunkify, trampoline too would be a good fit for Ramda. IMO.

History:

• R.trampoline was already suggested in R.trampoline #1484.
• RA.trampoline was attempted in #1425

Usage:

import { thunkify } from 'ramda';
// A tail-call recursive function, needs to return its thunk.
// fib :: (Number, Number, Number) → ( Number | () → ( Number | () → ( Number | … ) ) )
const fib = thunkify((n, k = 0, m = 1) => n === 1 ? m : fib(n - 1, m, k + m));

// trampoline as higher-order function
// fibT :: Number → Number
const fibT = trampoline(fib)
fibT(10); //=> 55

// trampoline as direct function application
trampolineApp(fib(10)); //=> 55

Signature

As high-order function returning an auto-curried function the signature could be something like
trampoline :: ((a, b, …, j) → Thunk k) → a → b → … → f → k
Thunk k = (() → (k | () → (k | … )))

Otherwise when simply applying the recursion
trampolineApp :: Thunk a → a

I'd prefer the higher-order function, though.

The implementation is straight forward.

Do we need this?

[CrossEye]

I think this would be a very good idea.

We should have done it years ago, but we did hope that the ES6 specifications would win out and TCO would be implemented. Instead the vendors are claiming it's too problematic, even after Safari demonstrated that it's not a real issue.

I think we'd have to come up with a different implementation than the linked

  trampoline = pc => {
    while (typeof pc === 'function') {
      pc = pc();
    }
    return pc;
  },

This treats functions as different from other values, with the implicit assumption that a recursive function couldn't return a function.

I'd have to think about how best to implement one, though.

[CrossEye]

Maybe related, a gist of mine using a Loop-Recur implementation adapted from one seen on StackOverflow:

const Loop = (fn, ... init) => { 
  let r = fn (... init)
  while (r instanceof Recur) r = fn (... r)
  return r
}

const Recur = ( ...v) => Object .create (
  Recur .prototype, 
  {[Symbol .iterator]: {value: _ => v .values ()}}
)

[semmel]

(The implementation) treats functions as different from other values, with the implicit assumption that a recursive function couldn't return a function.

I'd have to think about how best to implement one, though.

Indeed that is not good! I had a slight feeling that it was too easy.

Perhaps we can do it analog to chainRec?
Like

const fib = (next, done, n, k = 0, m = 1) => n === 1 ? done(m) : next(n - 1, m, k + m);

So, trampoline(fn)(x) would be something like Identity.chainRec(fn, x)?
Perhaps the Ramda users are already accustomed to rewrite their recursive functions in that chainRec style (next, done, x) => trampoline :: ((a → c a b, b → c a b, a) → c a b, a) → b