Безопасная для стека взаимная рекурсия без утечки деталей реализации на стороне вызова - PullRequest
Новая
       46

Безопасная для стека взаимная рекурсия без утечки деталей реализации на стороне вызова

3 голосов
/ 04 апреля 2019

Я обобщил батут Clojure loop / recur так, чтобы он работал с косвенной рекурсией: 

const trampoline = f => (...args) => {
  let acc = f(...args);

  while (acc && acc.type === recur) {
    let [f, ...args_] = acc.args;
    acc = f(...args_);
  }

  return acc;
};

const recur = (...args) =>
  ({type: recur, args});

const even = n =>
  n === 0
    ? true
    : recur(odd, n - 1);

const odd = n =>
  n === 0
    ? false
    : recur(even, n - 1);


console.log(
  trampoline(even) (1e5 + 1)); // false

Тем не менее, я должен позвонить на батуте явно на стороне вызова. Есть ли способ сделать это снова неявным, как с loop / recur?

Кстати, здесь loop / recur: 

const loop = f => {
  let acc = f();

  while (acc && acc.type === recur)
    acc = f(...acc.args);

  return acc;
};


const recur = (...args) =>
  ({type: recur, args});

1 Ответ

2 голосов
/ 04 апреля 2019

Очевидно, что если вы хотите, чтобы трамплин был вызван, его нельзя пропустить вообще. Простейшей вещью будет просто обернуть эти трамплинные вызовы в нужный вам API, возможно, что-то вроде этого: 

// Utility code
const trampoline = f => (...args) => {
  let acc = f(...args);

  while (acc && acc.type === recur) {
    let [f, ...args_] = acc.args;
    acc = f(...args_);
  }

  return acc;
};

const recur = (...args) =>
  ({type: recur, args});

// Private implementation
const _even = n =>
  n === 0
    ? true
    : recur(_odd, n - 1);

const _odd = n =>
  n === 0
    ? false
    : recur(_even, n - 1);

// Public API
const even = trampoline(_even);

const odd = trampoline(_odd);

// Demo code
console.log(
  even (1e5 + 1)); // false

console.log(
  odd (1e5 + 1)); // true
...