Можем ли мы реализовать хвостовую рекурсию по модулю cons и соавт. через батуты?

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, что не особенно удовлетворяет.Связано ли это с тем, что в Javascript строгий язык?Есть ли лучший способ для достижения умножения хвостовой рекурсии по модулю в JS без необходимости вводить неуклюжие бинарные операторы?

Answer 1

Вместо использования loop / recur (который я считаю уродливым и ненужным взломом), рассмотрите возможность использования складок:

const recNat = (zero, succ) => n => {
    let result = zero;

    while (n > 0) {
        result = succ(result);
        n = n - 1;
    }

    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]

Почти каждая рекурсивная функция может быть определена с использованием складок (структурная рекурсия, или индукция).Например, даже функция Аккермана может быть определена с помощью сгибов:

const recNat = (zero, succ) => n => {
    let result = zero;

    while (n > 0) {
        result = succ(result);
        n = n - 1;
    }

    return result;
};

const add = x => y => x + y;

const ack = recNat(add(1),
    ackPredM => recNat(ackPredM(1),
        ackMPredN => ackPredM(ackMPredN)));

console.time("ack(4)(1)");
console.log(ack(4)(1)); // 65533
console.timeEnd("ack(4)(1)");

Приведенный выше фрагмент кода занимает около 18 секунд для вычисления ответа на моем ноутбуке.

Теперь вы можете спросить, почему я реализовал recNat, используя итерациювместо естественной рекурсии:

const recNat = (zero, succ) => function recNatZS(n) {
    return n <= 0 ? zero : succ(recNatZS(n - 1));
};

Я использовал итерацию по той же причине, по которой вы использовали итерацию для реализации loop.Батуте.Реализуя разные батуты для каждого типа данных, которые вы собираетесь свернуть, вы можете писать функциональный код, не беспокоясь о переполнении стека.

Итог: Используйте сгибы вместо явной рекурсии,Они намного мощнее, чем вы думаете.