如何在没有尾调用优化的情况下用函数式编程替代方案替换 while 循环？

Question

我正在我的 JavaScript 中尝试一种更函数式的风格；因此，我用 map 和 reduce 等实用函数替换了 for 循环。但是，我还没有找到 while 循环的功能替代品，因为尾调用优化通常不适用于 JavaScript。 （据我了解，ES6 可以防止尾部调用溢出堆栈，但不会优化它们的性能。）

我在下面解释了我尝试过的方法，但总而言之：如果我没有尾调用优化，那么实现 while 循环的功能方法是什么？

我试过的：

创建一个“while”效用函数：

 function while(func, test, data) {
  const newData = func(data);
  if(test(newData)) {
    return newData;
  } else {
    return while(func, test, newData);
  }
}

由于尾调用优化不可用，我可以将其重写为：

 function while(func, test, data) {
  let newData = *copy the data somehow*
  while(test(newData)) {
    newData = func(newData);
  }
  return newData;
}

然而在这一点上，感觉我已经让我的代码对于使用它的任何其他人来说变得更加复杂/混乱，因为我不得不绕过一个自定义实用程序函数。我看到的唯一实际优势是它迫使我使循环变得纯净；但似乎只使用常规 while 循环并确保我保持一切纯净会更直接。

我还试图找出一种方法来创建一个生成器函数，该函数模拟递归/循环的效果，然后使用诸如 find 或 reduce 之类的实用函数对其进行迭代。但是，我还没有找到一种可读的方法来做到这一点。

最后，用实用函数替换 for 循环使我试图完成的事情更加明显（例如，对每个元素做一件事，检查每个元素是否通过测试等）。然而，在我看来，一个 while 循环已经表达了我想要完成的事情（例如，迭代直到我们找到一个质数，迭代直到答案被充分优化，等等）。

所以在这之后，我的总体问题是：如果我需要一个 while 循环，我正在以函数式风格编程，并且我无法访问尾调用优化，那么什么是最好的策略。

原文由 David Moneysmith 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

JavaScript 中的一个例子

下面是一个使用 JavaScript 的示例。目前，大多数浏览器不支持尾调用优化，因此以下代码片段将失败

 const repeat = n => f => x =>
  n === 0 ? x : repeat (n - 1) (f) (f(x))

console.log(repeat(1e3) (x => x + 1) (0)) // 1000
console.log(repeat(1e5) (x => x + 1) (0)) // Error: Uncaught RangeError: Maximum call stack size exceeded

---

蹦床

我们可以通过改变我们写 repeat 的方式来解决这个限制，但只是稍微改变一下。我们将返回两种蹦床类型中的一种，而不是直接或立即重复返回值， Bounce 或 Done 。然后我们将使用我们的 trampoline 函数来处理循环。

 // trampoline
const Bounce = (f,x) => ({ isBounce: true, f, x })

const Done = x => ({ isBounce: false, x })

const trampoline = ({ isBounce, f, x }) => {
  while (isBounce)
    ({ isBounce, f, x } = f(x))
  return x
}

// our revised repeat function, now stack-safe
const repeat = n => f => x =>
  n === 0 ? Done(x) : Bounce(repeat (n - 1) (f), f(x))

// apply trampoline to the result of an ordinary call repeat
let result = trampoline(repeat(1e6) (x => x + 1) (0))

// no more stack overflow
console.log(result) // 1000000

柯里化 也会稍微减慢速度，但我们可以使用递归的辅助函数来补救。这也很好，因为它隐藏了蹦床实现细节，并且不希望调用者反弹返回值。这运行速度大约是上面的两倍 repeat

 // aux helper hides trampoline implementation detail
// runs about 2x as fast
const repeat = n => f => x => {
  const aux = (n, x) =>
    n === 0 ? Done(x) : Bounce(x => aux (n - 1, x), f (x))
  return trampoline (aux (n, x))
}

---

Clojure 风格 loop / recur

Trampolines 很好，但不得不担心调用 trampoline 函数的返回值有点烦人。我们看到另一种方法是使用辅助助手，但这也有点烦人。我相信你们中的一些人也不太热衷于 Bounce 和 Done 包装器。

Clojure 创建了一个使用一对函数的专用蹦床接口， loop 和 recur 这个串联对有助于非常优雅地表达程序

哦，它也非常快

 const recur = (...values) =>
  ({ recur, values })

const loop = run =>
{ let r = run ()
  while (r && r.recur === recur)
    r = run (...r.values)
  return r
}

const repeat = n => f => x =>
  loop
    ( (m = n, r = x) =>
        m === 0
          ? r
          : recur (m - 1, f (r))
    )

console.time ('loop/recur')
console.log (repeat (1e6) (x => x + 1) (0)) // 1000000
console.timeEnd ('loop/recur')              // 24 ms

最初这种风格会让人觉得很陌生，但随着时间的推移，我发现它在制作持久的程序时是最一致的。下面的评论有助于您轻松使用表达式丰富的语法 -

 const repeat = n => f => x =>
  loop  // begin a loop with
    ( ( m = n   // local loop var m: counter, init with n
      , r = x   // local loop var r: result, init with x
      ) =>
        m === 0 // terminating condition
          ? r   // return result
          : recur    // otherwise recur with
             ( m - 1 // next m value
             , f (r) // next r value
             )
    )

延续单子

不过，这是我最喜欢的主题之一，所以我们将通过 continuation monad 看看它是什么样子。 Reusing loop and recur , we implement a stack-safe cont that can sequence operations using chain and run operation sequences using runCont 。对于 repeat ，这是毫无意义的（而且很慢），但是在这个简单的例子中看到 cont 的机制是很酷的 -

 const identity = x =>
  x

const recur = (...values) =>
  ({ recur, values })

const loop = run =>
{ let r = run ()
  while (r && r.recur === recur)
    r = run (...r.values)
  return r
}

// cont : 'a -> 'a cont
const cont = x =>
  k => recur (k, x)

// chain : ('a -> 'b cont) -> 'a cont -> 'b cont
const chain = f => mx =>
  k => recur (mx, x => recur (f (x), k))

// runCont : ('a -> 'b) -> a cont -> 'b
const runCont = f => mx =>
  loop ((r = mx, k = f) => r (k))

const repeat = n => f => x =>
{ const aux = n => x =>
    n === 0 // terminating condition
      ? cont (x) // base case, continue with x
      : chain             // otherise
          (aux (n - 1))   // sequence next operation on
          (cont (f (x)))  // continuation of f(x)

  return runCont  // run continuation
    (identity)    // identity; pass-thru
    (aux (n) (x)) // the continuation returned by aux
}

console.time ('cont monad')
console.log (repeat (1e6) (x => x + 1) (0)) // 1000000
console.timeEnd ('cont monad')              // 451 ms

---

Y 组合器

Y组合器是我的精神组合器；如果不在其他技术中占有一席之地，这个答案将是不完整的。然而，Y 组合器的大多数实现都不是堆栈安全的，如果用户提供的函数重复出现太多次，将会溢出。由于这个答案都是关于保留堆栈安全行为的，所以我们当然会以安全的方式实施 Y 再次依赖我们可信赖的蹦床。

Y 演示了扩展易于使用、堆栈安全、同步无限递归的能力，而不会弄乱您的函数。

 const bounce = f => (...xs) =>
  ({ isBounce: true, f, xs })

const trampoline = t => {
  while (t && t.isBounce)
    t = t.f(...t.xs)
  return t
}

// stack-safe Y combinator
const Y = f => {
  const safeY = f =>
    bounce((...xs) => f (safeY (f), ...xs))
  return (...xs) =>
    trampoline (safeY (f) (...xs))
}

// recur safely to your heart's content
const repeat = Y ((recur, n, f, x) =>
  n === 0
    ? x
    : recur (n - 1, f, f (x)))

console.log(repeat (1e5, x => x + 1, 0)) // 10000

---

while 循环的实用性

但老实说：当我们忽略一个更明显的潜在解决方案时，这是很多仪式：使用 for 或 while 循环，但将其隐藏在功能接口后面

出于所有意图和目的，这个 repeat 函数的工作方式与上面提供的函数相同——除了这个函数快了大约一倍或两倍（除了 loop / recur 解决方案）。哎呀，可以说它也更容易阅读。

诚然，这个函数可能是一个人为的例子——并不是所有的递归函数都可以很容易地转换为 for 或 while 循环，但在可能的情况下，它可能是最好的就这样去做。当简单的循环不起作用时，将蹦床和延续留给繁重的工作。

 const repeat = n => f => x => {
  let m = n
  while (true) {
    if (m === 0)
      return x
    else
      (m = m - 1, x = f (x))
  }
}

const gadzillionTimes = repeat(1e8)

const add1 = x => x + 1

const result = gadzillionTimes (add1) (0)

console.log(result) // 100000000

---

setTimeout 不是堆栈溢出问题的解决方案

好的，它 确实 有效，但只是自相矛盾。如果你的数据集很小，你不需要 setTimeout 因为不会有堆栈溢出。如果你的数据集很大并且你使用 setTimeout 作为一种安全的递归机制，你不仅无法从你的函数同步返回一个值，而且它会慢得你甚至不想使用你的功能

有些人找到了一个 鼓励这种可怕策略的 面试问答准备网站

What our repeat would look like using setTimeout – notice it’s also defined in continuation passing style – ie, we must call repeat with a callback ( k ) 得到最终值

 // do NOT implement recursion using setTimeout
const repeat = n => f => x => k =>
  n === 0
    ? k (x)
    : setTimeout (x => repeat (n - 1) (f) (x) (k), 0, f (x))

// be patient, this one takes about 5 seconds, even for just 1000 recursions
repeat (1e3) (x => x + 1) (0) (console.log)

// comment the next line out for absolute madness
// 10,000 recursions will take ~1 MINUTE to complete
// paradoxically, direct recursion can compute this in a few milliseconds
// setTimeout is NOT a fix for the problem
// -----------------------------------------------------------------------------
// repeat (1e4) (x => x + 1) (0) (console.log)

我怎么强调这有多糟糕都不为过。甚至 1e5 运行时间太长，以至于我放弃了测量它的尝试。我没有将其包含在下面的基准测试中，因为它太慢了，甚至不能被认为是一种可行的方法。

---

承诺

Promises 具有链接计算的能力并且是堆栈安全的。然而，使用 Promises 实现堆栈安全 repeat 意味着我们将不得不放弃我们的同步返回值，就像我们使用 setTimeout 一样。我将其作为“解决方案”提供，因为它 确实 解决了问题，与 setTimeout 不同，但与蹦床或延续 monad 相比，它以一种非常简单的方式。正如您可能想象的那样，性能有些差，但远不及上面的示例 setTimeout 差

值得注意的是，在此解决方案中，Promise 实现细节对调用者完全隐藏。单个延续作为第四个参数提供，并在计算完成时调用。

 const repeat = n => f => x => k =>
  n === 0
    ? Promise.resolve(x).then(k)
    : Promise.resolve(f(x)).then(x => repeat (n - 1) (f) (x) (k))

// be patient ...
repeat (1e6) (x => x + 1) (0) (x => console.log('done', x))

---

基准

说真的， while 循环快了 _很多_——几乎快了 100 倍（当比较最好和最差时——但不包括异步答案： setTimeout 和 Promise f64d1）

 // sync
// -----------------------------------------------------------------------------
// repeat implemented with basic trampoline
console.time('A')
console.log(tramprepeat(1e6) (x => x + 1) (0))
console.timeEnd('A')
// 1000000
// A 114 ms

// repeat implemented with basic trampoline and aux helper
console.time('B')
console.log(auxrepeat(1e6) (x => x + 1) (0))
console.timeEnd('B')
// 1000000
// B 64 ms

// repeat implemented with cont monad
console.time('C')
console.log(contrepeat(1e6) (x => x + 1) (0))
console.timeEnd('C')
// 1000000
// C 33 ms

// repeat implemented with Y
console.time('Y')
console.log(yrepeat(1e6) (x => x + 1) (0))
console.timeEnd('Y')
// 1000000
// Y 544 ms

// repeat implemented with while loop
console.time('D')
console.log(whilerepeat(1e6) (x => x + 1) (0))
console.timeEnd('D')
// 1000000
// D 4 ms

// async
// -----------------------------------------------------------------------------

// repeat implemented with Promise
console.time('E')
promiserepeat(1e6) (x => x + 1) (0) (console.log)
console.timeEnd('E')
// 1000000
// E 2224 ms

// repeat implemented with setTimeout; FAILED
console.time('F')
timeoutrepeat(1e6) (x => x + 1) (0) (console.log)
console.timeEnd('F')
// ...
// too slow; didn't finish after 3 minutes

---

石器时代的JavaScript

上面的技术是使用更新的 ES6 语法演示的，但是你可以在尽可能早的 JavaScript 版本中实现一个蹦床——它只需要 while 和一流的功能

下面，我们使用石器时代的 javascript 来演示无限递归是可能的，并且在 不牺牲 同步返回值的情况下是高效的——在 6 秒内执行 100,000,000 次 递归——这与 setTimeout 相比是一个巨大的差异 --- 只能进行 1,000 次递归同样的时间。

 function trampoline (t) {
  while (t && t.isBounce)
    t = t.f (t.x);
  return t.x;
}

function bounce (f, x) {
  return { isBounce: true, f: f, x: x };
}

function done (x) {
  return { isBounce: false, x: x };
}

function repeat (n, f, x) {
  function aux (n, x) {
    if (n === 0)
      return done (x);
    else
      return bounce (function (x) { return aux (n - 1, x); }, f (x));
  }
  return trampoline (aux (n, x));
}

console.time('JS1 100K');
console.log (repeat (1e5, function (x) { return x + 1 }, 0));
console.timeEnd('JS1 100K');
// 100000
// JS1 100K: 15ms

console.time('JS1 100M');
console.log (repeat (1e8, function (x) { return x + 1 }, 0));
console.timeEnd('JS1 100M');
// 100000000
// JS1 100K: 5999ms

使用石器时代 JavaScript 的非阻塞无限递归

如果 出于某种原因，你想要非阻塞（异步）无限递归，我们可以依靠 setTimeout 在计算开始时推迟 _一个帧_。该程序还使用石器时代的 javascript 并在 8 秒内计算 100,000,000 次递归，但这次是以非阻塞方式进行的。

这表明非阻塞要求并没有什么特别之处。 A while 循环和一等函数仍然是在不牺牲性能的情况下实现堆栈安全递归的唯一基本要求

在现代程序中，给定 Promise，我们将替换 setTimeout 对单个 Promise 的调用。

 function donek (k, x) {
  return { isBounce: false, k: k, x: x };
}

function bouncek (f, x) {
  return { isBounce: true, f: f, x: x };
}

function trampolinek (t) {
  // setTimeout is called ONCE at the start of the computation
  // NOT once per recursion
  return setTimeout(function () {
    while (t && t.isBounce) {
      t = t.f (t.x);
    }
    return t.k (t.x);
  }, 0);
}

// stack-safe infinite recursion, non-blocking, 100,000,000 recursions in under 8 seconds
// now repeatk expects a 4th-argument callback which is called with the asynchronously computed result
function repeatk (n, f, x, k) {
  function aux (n, x) {
    if (n === 0)
      return donek (k, x);
    else
      return bouncek (function (x) { return aux (n - 1, x); }, f (x));
  }
  return trampolinek (aux (n, x));
}

console.log('non-blocking line 1')
console.time('non-blocking JS1')
repeatk (1e8, function (x) { return x + 1; }, 0, function (result) {
  console.log('non-blocking line 3', result)
  console.timeEnd('non-blocking JS1')
})
console.log('non-blocking line 2')

// non-blocking line 1
// non-blocking line 2
// [ synchronous program stops here ]
// [ below this line, asynchronous program continues ]
// non-blocking line 3 100000000
// non-blocking JS1: 7762ms

原文由 Mulan 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 2

更好的 loop / recur 模式

关于 接受的答案 中描述的 loop / recur 模式，我有两点不喜欢。请注意，我实际上喜欢 loop / recur 模式背后的想法。但是，我不喜欢它的实施方式。那么，让我们首先看看我将如何实现它。

 // Recur :: a -> Result a b
const Recur = (...args) => ({ recur: true, args });

// Return :: b -> Result a b
const Return = value => ({ recur: false, value });

// loop :: (a -> Result a b) -> a -> b
const loop = func => (...args) => {
    let result = func(...args);
    while (result.recur) result = func(...result.args);
    return result.value;
};

// repeat :: (Int, a -> a, a) -> a
const repeat = loop((n, f, x) => n === 0 ? Return(x) : Recur(n - 1, f, f(x)));

console.time("loop/recur/return");
console.log(repeat(1e6, x => x + 1, 0));
console.timeEnd("loop/recur/return");

将此与上述答案中描述的 loop / recur 模式进行比较。

 // recur :: a -> Recur a
const recur = (...args) => ({ recur, args });

// loop :: (a? -> Recur a ∪ b) -> b
const loop = func => {
    let result = func();
    while (result && result.recur === recur) result = func(...result.args);
    return result;
};

// repeat :: (Int, a -> a, a) -> a
const repeat = (n, f, x) => loop((m = n, r = x) => m === 0 ? r : recur(m - 1, f(r)));

console.time("loop/recur");
console.log(repeat(1e6, x => x + 1, 0));
console.timeEnd("loop/recur");

如果您注意到，第二个 loop 函数的类型签名使用 默认参数（即 a? ）和 未标记的联合（即 Recur a ∪ b cd）。这两个特性都与函数式编程范式不一致。

默认参数问题

上述答案中的 loop / recur 模式使用默认参数来提供函数的初始参数。我认为这是对默认参数的滥用。您可以使用我的版本 loop 轻松提供初始参数。

 // repeat :: (Int, a -> a, a) -> a
const repeat = (n, f, x) => loop((n, x) => n === 0 ? Return(x) : Recur(n - 1, f(x)))(n, x);

// or more readable
const repeat = (n, f, x) => {
    const repeatF = loop((n, x) => n === 0 ? Return(x) : Recur(n - 1, f(x)));
    return repeatF(n, x);
};

此外，它允许在传递所有参数时进行 eta 转换。

 // repeat :: (Int, a -> a, a) -> a
const repeat = (n, f, x) => loop((n, f, x) => n === 0 ? Return(x) : Recur(n - 1, f, f(x)))(n, f, x);

// can be η-converted to
const repeat = loop((n, f, x) => n === 0 ? Return(x) : Recur(n - 1, f, f(x)));

使用带有默认参数的 loop 版本不允许eta转换。此外，它会强制您 重命名参数，因为您不能在 JavaScript 中编写 (n = n, x = x) => ... 。

未标记联合的问题

未标记的联合是不好的，因为它们会删除重要信息，即数据来自何处的信息。例如，因为我的 Result 类型被标记了，所以我可以区分 Return(Recur(0)) 和 Recur(0) 。

另一方面，因为 Recur a ∪ b 的右侧变体没有标记，如果 b 专门化为 Recur a 如果专门化类型是， Recur a ∪ Recur a ，则无法确定 Recur a 是来自左侧还是右侧。

一种批评可能是 b 永远不会专门用于 Recur a ，因此 b 没有标记并不重要。这是该批评的一个简单反例。

 // recur :: a -> Recur a
const recur = (...args) => ({ recur, args });

// loop :: (a? -> Recur a ∪ b) -> b
const loop = func => {
    let result = func();
    while (result && result.recur === recur) result = func(...result.args);
    return result;
};

// repeat :: (Int, a -> a, a) -> a
const repeat = (n, f, x) => loop((m = n, r = x) => m === 0 ? r : recur(m - 1, f(r)));

// infinite loop
console.log(repeat(1, x => recur(1, x), "wow, such hack, much loop"));

// unreachable code
console.log("repeat wasn't hacked");

将此与我的防弹版本 repeat 进行比较。

 // Recur :: a -> Result a b
const Recur = (...args) => ({ recur: true, args });

// Return :: b -> Result a b
const Return = value => ({ recur: false, value });

// loop :: (a -> Result a b) -> a -> b
const loop = func => (...args) => {
    let result = func(...args);
    while (result.recur) result = func(...result.args);
    return result.value;
};

// repeat :: (Int, a -> a, a) -> a
const repeat = loop((n, f, x) => n === 0 ? Return(x) : Recur(n - 1, f, f(x)));

// finite loop
console.log(repeat(1, x => Recur(1, x), "wow, such hack, much loop"));

// reachable code
console.log("repeat wasn't hacked");

因此，未标记的联合是不安全的。然而，即使我们小心避免未标记联合的陷阱，我仍然更喜欢标记联合，因为标记在阅读和调试程序时提供有用的信息。恕我直言，标签使程序更易于理解和调试。

结论

引用 Python 之禅。

显式优于隐式。

默认参数和未标记的联合是不好的，因为它们是隐式的，并且可能导致歧义。

Trampoline 单子

现在，我想换个话题谈谈 monad。接受的答案演示了堆栈安全的延续 monad。但是，如果您只需要创建一个 monadic 堆栈安全递归函数，那么您不需要 continuation monad 的全部功能。您可以使用 Trampoline monad。

Trampoline monad 是 Loop monad 的更强大的表亲，它只是 loop 函数转换为 monad那么，让我们从了解 Loop monad 开始。然后我们将看到 Loop monad 的主要问题以及如何使用 Trampoline monad 来解决该问题。

 // Recur :: a -> Result a b
const Recur = (...args) => ({ recur: true, args });

// Return :: b -> Result a b
const Return = value => ({ recur: false, value });

// Loop :: (a -> Result a b) -> a -> Loop b
const Loop = func => (...args) => ({ func, args });

// runLoop :: Loop a -> a
const runLoop = ({ func, args }) => {
    let result = func(...args);
    while (result.recur) result = func(...result.args);
    return result.value;
};

// pure :: a -> Loop a
const pure = Loop(Return);

// bind :: (Loop a, a -> Loop b) -> Loop b
const bind = (loop, next) => Loop(({ first, loop: { func, args } }) => {
    const result = func(...args);
    if (result.recur) return Recur({ first, loop: { func, args: result.args } });
    if (first) return Recur({ first: false, loop: next(result.value) });
    return result;
})({ first: true, loop });

// ack :: (Int, Int) -> Loop Int
const ack = (m, n) => {
    if (m === 0) return pure(n + 1);
    if (n === 0) return ack(m - 1, 1);
    return bind(ack(m, n - 1), n => ack(m - 1, n));
};

console.log(runLoop(ack(3, 4)));

请注意， loop 已拆分为 Loop 和 runLoop 函数。 Loop 返回的数据结构是一个monad， pure 和 bind 函数实现了它的monadic接口。我们使用 pure 和 bind 函数来编写 Ackermann 函数 的直接实现。

不幸的是， ack 函数不是堆栈安全的，因为它会递归调用自身，直到达到 pure 值。相反，我们希望 ack 为其归纳案例返回一个 Recur 数据结构。但是， Recur 值的类型为 Result 而不是 Loop 。这个问题由 Trampoline monad 解决。

 // Bounce :: (a -> Trampoline b) -> a -> Trampoline b
const Bounce = func => (...args) => ({ bounce: true, func, args });

// Return :: a -> Trampoline a
const Return = value => ({ bounce: false, value });

// trampoline :: Trampoline a -> a
const trampoline = result => {
    while (result.bounce) result = result.func(...result.args);
    return result.value;
};

// pure :: a -> Trampoline a
const pure = Return;

// bind :: (Trampoline a, a -> Trampoline b) -> Trampoline b
const bind = (first, next) => first.bounce ?
    Bounce(args => bind(first.func(...args), next))(first.args) :
    next(first.value);

// ack :: (Int, Int) -> Trampoline Int
const ack = Bounce((m, n) => {
    if (m === 0) return pure(n + 1);
    if (n === 0) return ack(m - 1, 1);
    return bind(ack(m, n - 1), n => ack(m - 1, n));
});

console.log(trampoline(ack(3, 4)));

Trampoline 数据类型是 Loop 和 Result 的组合。 Loop 和 Recur 数据构造函数已合并为一个 Bounce 数据构造函数。 runLoop 函数已简化并重命名为 trampoline 。 pure 和 bind 功能也已简化。事实上， pure 只是 Return 。最后，我们将 Bounce 应用于 ack 函数的原始实现。

Trampoline 的另一个优点是它可以用来定义堆栈安全的相互递归函数。例如，这里是 Hofstadter Female 和 Male 序列 函数的实现。

 // Bounce :: (a -> Trampoline b) -> a -> Trampoline b
const Bounce = func => (...args) => ({ bounce: true, func, args });

// Return :: a -> Trampoline a
const Return = value => ({ bounce: false, value });

// trampoline :: Trampoline a -> a
const trampoline = result => {
    while (result.bounce) result = result.func(...result.args);
    return result.value;
};

// pure :: a -> Trampoline a
const pure = Return;

// bind :: (Trampoline a, a -> Trampoline b) -> Trampoline b
const bind = (first, next) => first.bounce ?
    Bounce(args => bind(first.func(...args), next))(first.args) :
    next(first.value);

// female :: Int -> Trampoline Int
const female = Bounce(n => n === 0 ? pure(1) :
    bind(female(n - 1), f =>
        bind(male(f), m =>
            pure(n - m))));

// male :: Int -> Trampoline Int
const male = Bounce(n => n === 0 ? pure(0) :
    bind(male(n - 1), m =>
        bind(female(m), f =>
            pure(n - f))));

console.log(Array.from({ length: 21 }, (_, n) => trampoline(female(n))).join(" "));
console.log(Array.from({ length: 21 }, (_, n) => trampoline(male(n))).join(" "));

编写 monadic 代码的主要痛点是 回调地狱。但是，这可以使用生成器来解决。

 // Bounce :: (a -> Trampoline b) -> a -> Trampoline b
const Bounce = func => (...args) => ({ bounce: true, func, args });

// Return :: a -> Trampoline a
const Return = value => ({ bounce: false, value });

// trampoline :: Trampoline a -> a
const trampoline = result => {
    while (result.bounce) result = result.func(...result.args);
    return result.value;
};

// pure :: a -> Trampoline a
const pure = Return;

// bind :: (Trampoline a, a -> Trampoline b) -> Trampoline b
const bind = (first, next) => first.bounce ?
    Bounce(args => bind(first.func(...args), next))(first.args) :
    next(first.value);

// bounce :: (a -> Generator (Trampoline b)) -> a -> Trampoline b
const bounce = func => Bounce((...args) => {
    const gen = func(...args);

    const next = data => {
        const { value, done } = gen.next(data);
        return done ? value : bind(value, next);
    };

    return next(undefined);
});

// female :: Int -> Trampoline Int
const female = bounce(function* (n) {
    return pure(n ? n - (yield male(yield female(n - 1))) : 1);
});

// male :: Int -> Trampoline Int
const male = bounce(function* (n) {
    return pure(n ? n - (yield female(yield male(n - 1))) : 0);
});

console.log(Array.from({ length: 21 }, (_, n) => trampoline(female(n))).join(" "));
console.log(Array.from({ length: 21 }, (_, n) => trampoline(male(n))).join(" "));

最后，相互递归函数还展示了具有单独的 trampoline 函数的优势。它允许我们调用一个返回 Trampoline 值的函数，而无需实际运行它。这允许我们构建更大的 Trampoline 值，然后在需要时运行整个计算。

结论

如果您想编写间接或相互递归的堆栈安全函数，或单子堆栈安全函数，请使用 Trampoline monad。如果你想直接编写非单子递归堆栈安全函数，那么使用 loop / recur / return pattern.cab

原文由 Aadit M Shah 发布，翻译遵循 CC BY-SA 4.0 许可协议