我们可以实现尾递归模的缺点吗？通过蹦床？

Question

您可以将蹦床视为程序中优化的编译器优化。因此，是什么使我们无法以完全相同的方式来适应更通用的优化技术。

这是尾递归模态缺点的草图：

const loop = f => {

  let step = f();

 while (step && step[step.length - 1] && step[step.length - 1].type === recur) {

    let step_ = step.pop();

    step.push(...f(...step_.args));

  }

  return step;

};

const recur = (...args) =>

  ({type: recur, args});

const push = (xs, x) => (xs.push(x), xs);

const map = f => xs =>

  loop((i = 0) =>

    i === xs.length

      ? []

      : push([f(xs[i])], recur(i + 1)));

const xs = 

  map(x => x * 2) (Array(1e6).fill(0).map((x, i) => i))

  .slice(0,5);

console.log(xs); // [0, 2, 4, 6, 8]

这种优化取决于表达式的关联性。乘法也具有关联性，因此存在尾递归模乘。但是，我必须作弊才能在Javascript中实现它：

const loop = f => {

  let step = f();

  const acc = [];

  while (step && step[1] && step[1].type === recur) {

    acc.push(step[0]);

    step = f(...step[1].args);

  }

  return acc.reduce((acc, f) => f(acc), step);

};

const recur = (...args) =>

  ({type: recur, args});

const mul = x => step => [y => x * y, step];

const pow = (x_, n_) =>

  loop((x = x_, n = n_) =>

    n === 0 ? 1

    : n === 1 ? x

    : mul(x) (recur(x, n - 1)));

    

console.log(

  pow(2, 1e6)); // Infinity, no stack overflow

如您所见，我不能使用mul不是特别令人满意的Regular 。这与Javascript蜜蜂语言紧密相关吗？有没有更好的方法来实现JS中的尾递归模乘而不必引入笨拙的二进制运算符？

Answer 1

与其使用loop/ recur（我认为这是一种丑陋和不必要的hack），不如考虑使用folds：const recNat = (zero, succ) => n => {&nbsp; &nbsp; let result = zero;&nbsp; &nbsp; while (n > 0) {&nbsp; &nbsp; &nbsp; &nbsp; result = succ(result);&nbsp; &nbsp; &nbsp; &nbsp; n = n - 1;&nbsp; &nbsp; }&nbsp; &nbsp; return result;};const mul = x => y => x * y;const pow = x => recNat(1, mul(x));console.log([0,1,2,3,4,5,6,1e6].map(pow(2))); // [1,2,4,8,16,32,64,Infinity]几乎每个递归函数都可以使用折叠来定义（也称为结构递归，又称为归纳）。例如，甚至可以使用折叠来定义Ackermann函数：const recNat = (zero, succ) => n => {&nbsp; &nbsp; let result = zero;&nbsp; &nbsp; while (n > 0) {&nbsp; &nbsp; &nbsp; &nbsp; result = succ(result);&nbsp; &nbsp; &nbsp; &nbsp; n = n - 1;&nbsp; &nbsp; }&nbsp; &nbsp; return result;};const add = x => y => x + y;const ack = recNat(add(1),&nbsp; &nbsp; ackPredM => recNat(ackPredM(1),&nbsp; &nbsp; &nbsp; &nbsp; ackMPredN => ackPredM(ackMPredN)));console.time("ack(4)(1)");console.log(ack(4)(1)); // 65533console.timeEnd("ack(4)(1)");上面的代码段大约需要18秒才能在笔记本电脑上计算出答案。现在，您可能会问为什么我recNat使用迭代而不是自然递归来实现：const recNat = (zero, succ) => function recNatZS(n) {&nbsp; &nbsp; return n <= 0 ? zero : succ(recNatZS(n - 1));};我使用迭代的原因与您使用迭代实现的原因相同loop。踩踏。通过为要折叠的每种数据类型实现不同的蹦床，您可以编写功能代码，而不必担心堆栈溢出。底线：使用折叠而不是显式递归。它们比您想像的强大得多。