Как сделать отложенные структуры вызова вложенных функций стека безопасными?

Question

Безопасная для стека рекурсия иногда создает отложенные вложенные деревья вызовов функций, которые после оценки могут исчерпать стек:

const compn = fs => // non-recursive to keep it simple
  fs.reduce((f, g) => comp(f) (g), x => x);

const compn_ = fs => x => // non-recursive to keep it simple
  fs.reduce((x, f) => f(x), x);

const comp = f => g => x => f(g(x));

const inc = x => x + 1;

const fs = Array(1e5).fill(inc);

try {compn(fs) (0)}
catch (e) {
  console.log(e.message);
}

console.log(compn_(fs) (0));

Мы можем вообще избежать строительства таких структур (compn_), но мне интересно, есть ли менее ограниченный способ борьбы с ними:

const rec = f => (...args) => {
  let step = f(...args);
  const stack = [];

  while (step.tag !== Base) {
    stack.push(step.f);
    step = f(...step.step.args);
  }

  return x => {
    for (let i = stack.length - 1; i >= 0; i--) {
      x = stack[i] (x);

      if (x && x.tag === Base) {
        x = x.x;
        break;
      }
    }

    return x;
  }
};

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

const Call = (f, step) =>
  ({tag: Call, f, step});

const Step = (...args) =>
  ({tag: Step, args});

const id = x => x;

const comp = f => g => x => f(g(x));

const inc = x => x + 1;

const fold = f => acc => xs =>
  rec(i =>
    i === xs.length
      ? Base(acc)
      : Call(f(xs[i]) (id), Step(i + 1))) (0);
//                     ^^ works but is nonsensical

const fs = Array(1e5).fill(inc);

console.log(
  fold(f => g => comp(f) (g))
    (id)
      (fs)
        (0)); // 100000

Это работает, но применение id к каждому рекурсивному шагу сводит на нет цель использования comp в первую очередь. Есть ли способ работать с такими отложенными древовидными структурами в Javascript или мы должны вернуться к линейным структурам, подобным стеку?

Answer 1

Один из способов обеспечения безопасности стека comp(inc) (comp(inc) (comp(inc) (..))) - отложить выполнение еще больше, уточнив продолжение:

const Cont = k => ({tag: "Cont", k});

const compk = f => g => x =>
  Cont(k => k(f(g(x))));

const compn = fs =>
  fs.reduce((f, g) => compk(f) (g), x => x);

const id = x => x;

const inc = x => x + 1;

const postRec = cont => {
  do {
    cont = cont.k(id);
  } while (cont && cont.tag === "Cont")

  return cont;
};

const fs = Array(1e5).fill(inc);

const main = compn(fs) (0);

console.log(
  postRec(main));

Теперь обработка каждого вложенного уровня структуры откладывается и выполняется в батуте. Я называю этот батут postRec, так как он запускается после того, как оригинальный рекурсивный алгоритм уже закончил свою работу. Я не знаю, насколько этот подход достаточно полезен.