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

How do I replace while loops with a functional programming alternative without tail call optimization?

提问人：David Moneysmith 提问时间：4/24/2017 更新时间：1/16/2020 访问量：35506

问：

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

我在下面解释我尝试过的内容，但 TLDR 是： 如果我没有尾调用优化，实现 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 循环，我以函数式风格编程，并且我无法访问尾部调用优化，那么最好的策略是什么。

JavaScript 递归 while-loop 函数编程 tail-call-optimization

评论

1赞 Bergi 4/24/2017
如果您需要性能并且 TCO 不可用，那么就没有办法绕过这个循环。如果你不这样做，并且你想以函数式风格编程，那就使用递归。
1赞 apsillers 4/24/2017
在我看来，ES6 确实需要尾部调用优化;即当通过尾部调用创建新的堆栈帧时，ES6 要求使用的内存仅增加新堆栈帧和旧堆栈帧的差异，因此递归调用同一函数创建的堆栈帧应该不会导致内存增加。也就是说，并不是每个实现都支持ES6（ES6只支持严格模式下的TCO），所以这里仍然存在一个有效的问题。
3赞 apsillers 4/24/2017
据我所知，消除递归的传统（也是唯一？）方法是蹦床——即通过返回函数来弹出调用堆栈，然后使用之前的返回值再次调用函数。蹦床需要一个循环，或多或少是你在这里所做的。
0赞 Bergi 9/10/2017
“但不优化其性能”是什么意思？

答：

130赞 Mulan 4/25/2017 #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

蹦 床

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

// 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 式循环/循环

蹦床很好，但不得不担心调用函数的返回值有点烦人。我们看到另一种选择是使用辅助助手，但来吧，这也有点烦人。我敢肯定，你们中的一些人也不太热衷于包装器。trampolineBounceDone

Clojure 创建了一个专门的蹦床界面，它使用一对功能，并且 - 这对串联组合有助于表达一个非常优雅的程序looprecur

哦，它也非常快

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
             )
    )

延续单子

这是我最喜欢的话题之一，所以我们要看看延续单子是什么样子的。重用 和 ，我们实现了一个堆栈安全，它可以使用 对操作进行排序，并使用 运行操作序列。对于 ，这是毫无意义的（而且很慢），但在这个简单的例子中看到工作中的机制很酷——looprecurcontchainrunContrepeatcont

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 循环的实用性

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

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

诚然，这个函数可能是一个人为的例子——并非所有递归函数都可以如此轻松地转换为 or 循环，但在这种可能的情况下，最好这样做。将蹦床和延续物留作举重，当简单的循环无法完成时。forwhile

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 不是堆栈溢出问题的解决方案

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

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

我们使用的样子 - 请注意，它也是以延续传递样式定义的 - 即，我们必须使用回调 （） 调用以获取最终值repeatsetTimeoutrepeatk

// 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

承诺

Promise 具有链接计算的能力，并且是堆栈安全的。但是，使用 Promise 实现堆栈安全意味着我们必须放弃同步返回值，就像我们使用 .我将其作为“解决方案”提供，因为它确实解决了问题，与 不同，但与蹦床或延续单子相比，它的方式非常简单。正如你所想象的那样，性能有点差，但远没有上面的例子那么糟糕repeatsetTimeoutsetTimeoutsetTimeout

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

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))

基准

说真的，循环要快得多——就像快了近 100 倍（将最好和最差进行比较时——但不包括异步答案：和whilesetTimeoutPromise)

// 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 次递归——与在相同的时间内只能进行 1,000 次递归相比，这是一个巨大的差异。setTimeout

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 的非阻塞无限递归

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

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

在现代程序中，给定 Promises，我们会用调用代替单个 Promise。setTimeout

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

评论

8赞 james emanon 8/28/2017
跆拳道！！神圣的烟雾，这是全面的..真的很好.>但我认为 es6 现在支持尾调用优化......你有什么“更简单的例子可以放松”吗？洛洛尔
1赞 Mulan 8/28/2017
@jamesemanon，花一些时间学习蹦床片段——这是最直接的，并提供出色的性能
4赞 Mulan 9/10/2017
更新：我不得不承认 / 界面比传统的要好得多——它更适合表达函数式程序，而且它仍然非常快looprecurtrampoline
1赞 Aadit M Shah 9/21/2019
“我不得不承认，循环/递归界面比传统的蹦床要好得多”——它更适合表达功能程序......”我不同意。蹦床界面要好得多。您可以在定义站点包装尾部调用，而不是将尾部调用包装在调用站点。因此，您将拥有 Bounce/Return 模式，而不是 / 模式。其他优点是，您可以使用蹦床指定任意尾部调用函数，并且可以创建一个 monad 实例，因为 .BouncelooprecurTrampoline = Free Identity
1赞 Mulan 5/26/2021
@Rewind“表示法”只是普通的 JavaScript。 并返回简单对象，并在每个步骤中计算对象，并决定是再次运行循环（反弹）还是停止并返回值（完成）。这个想法在本问答中得到了扩展，我们为堆栈安全的复杂递归模式设计了自己的赋值器。我还推荐 Aadit 的答案以获得更正式的解释。Aadit 很聪明。像 Aadit 一样。BounceDonetrampoline
2赞 user6445533 4/26/2017 #2

函数范式意义上的编程意味着我们以类型为指导来表达我们的算法。

要将尾部递归函数转换为堆栈安全版本，我们必须考虑两种情况：

  • 基本情况
  • 递归案例

我们必须做出选择，这与标记工会相得益彰。但是，Javascript 没有这样的数据类型，因此我们必须创建一个或回退到编码。Object

对象编码

// simulate a tagged union with two Object types

const Loop = x =>
  ({value: x, done: false});
  
const Done = x =>
  ({value: x, done: true});

// trampoline

const tailRec = f => (...args) => {
  let step = Loop(args);

  do {
    step = f(Loop, Done, step.value);
  } while (!step.done);

  return step.value;
};

// stack-safe function

const repeat = n => f => x =>
  tailRec((Loop, Done, [m, y]) => m === 0
    ? Done(y)
    : Loop([m - 1, f(y)])) (n, x);

// run...

const inc = n =>
  n + 1;

console.time();
console.log(repeat(1e6) (inc) (0));
console.timeEnd();

函数编码

或者，我们可以创建一个带有函数编码的真正标记联合。现在我们的风格更接近成熟的函数式语言：

// type/data constructor

const Type = Tcons => (tag, Dcons) => {
  const t = new Tcons();
  t.run = cases => Dcons(cases);
  t.tag = tag;
  return t;
};

// tagged union specific for the case

const Step = Type(function Step() {});

const Done = x =>
  Step("Done", cases => cases.Done(x));
  
const Loop = args =>
  Step("Loop", cases => cases.Loop(args));

// trampoline

const tailRec = f => (...args) => {
  let step = Loop(args);

  do {
    step = f(step);
  } while (step.tag === "Loop");

  return step.run({Done: id});
};

// stack-safe function

const repeat = n => f => x => 
  tailRec(step => step.run({
    Loop: ([m, y]) => m === 0 ? Done(y) : Loop([m - 1, f(y)]),
    Done: y => Done(y)
  })) (n, x);

// run...

const inc = n => n + 1;
const id = x => x;

console.log(repeat(1e6) (inc) (0));

评论

1赞 Mulan 4/27/2017
我正在尝试各种方法来实现像您这样的函数，该函数可以容纳咖喱函数 - vs 但我遇到了一些障碍。在这一点上，我会非常小心地使用作为循环条件，因为函数返回其他函数是很常见的，有时可能是 的误报。这就是为什么我为我的蹦床使用特定的容器。无论如何，按照往常^_^，答案真的很好eagerrepeat = n => f => x => ...repeat = (n, f, x) =>typeof g === 'function'eagerBounce
1赞 gpilotino 1/11/2018 #3

另请参阅展开哪个（来自 Ramda 文档）

从种子值生成列表。接受迭代器函数，该函数 返回 false 以停止迭代或长度为 2 的数组 包含要添加到结果列表的值和要 在下次调用迭代器函数时使用。

var r = n => f => x => x > n ? false : [x, f(x)];
var repeatUntilGreaterThan = n => f => R.unfold(r(n)(f), 1);
console.log(repeatUntilGreaterThan(10)(x => x + 1));
<script src="https://cdnjs.cloudflare.com/ajax/libs/ramda/0.22.1/ramda.min.js"></script>

评论

0赞 Drenai 2/19/2019
Ramda 的功能在引擎盖下使用一个循环，所以不确定是否有任何优化（尽管肯定更干净）unfoldwhile
0赞 bronkula 12/20/2018 #4

我一直在思考这个问题。最近，我遇到了对函数式while循环的需求。

在我看来，这个问题唯一真正想要的是一种内联 while 循环的方法。有一种方法可以使用闭包来做到这一点。

"some string "+(a=>{
   while(comparison){
      // run code
   }
   return result;
})(somearray)+" some more"

或者，如果你想要的是链接数组的东西，那么你可以使用 reduce 方法。

somearray.reduce((r,o,i,a)=>{
   while(comparison){
      // run code
   }
   a.splice(1); // This would ensure only one call.
   return result;
},[])+" some more"

这些实际上都没有将我们的 while 循环的核心变成一个函数。但它确实允许我们使用内联循环。我只是想与任何可能有帮助的人分享这一点。

13赞 Aadit M Shah 11/20/2019 #5

更好的/模式looprecur

关于公认的答案中描述的 / 模式，我不喜欢两件事。请注意，我实际上喜欢 / 模式背后的想法。但是，我不喜欢它的实现方式。所以，让我们先看看我实现它的方式。looprecurlooprecur

// 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");

将其与上述答案中描述的 / 模式进行比较。looprecur

// 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");

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

默认参数问题

上述答案中的 / 模式使用默认参数来提供函数的初始参数。我认为这是对默认参数的滥用。您可以使用我的 .looprecurloop

// 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)));

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

未标记联合的问题

未标记的联合是不好的，因为它们会擦除重要信息，即数据来源的信息。例如，因为我的类型被标记了，所以我可以区分 .ResultReturn(Recur(0))Recur(0)

另一方面，由于 的右侧变体是未标记的，如果专门用于 ，即如果类型专门用于 ，则无法确定 是来自左侧还是右侧。Recur a ∪ bbRecur aRecur a ∪ Recur aRecur a

一个批评可能是永远不会专门用于 ，因此没有标记并不重要。这里有一个简单的反例来反驳这种批评。bRecur ab

// 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

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

monad 是 monad 的一个更强大的表亲，它只是转换为 monad 的函数。所以，让我们从了解单子开始。然后，我们将看到单子的主要问题，以及如何使用单子来解决该问题。TrampolineLooploopLoopLoopTrampoline

// 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)));

请注意，它已拆分为 a 和 a 函数。返回的数据结构是一个 monad，和 函数实现其 monadic 接口。我们使用 and 函数来编写 Ackermann 函数的简单实现。loopLooprunLoopLooppurebindpurebind

不幸的是，该函数不是堆栈安全的，因为它会递归调用自身，直到达到一个值。相反，我们希望为其归纳情况返回一个类似的数据结构。但是，值的类型不是 。这个问题由单子解决。ackpureackRecurRecurResultLoopTrampoline

// 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)));

数据类型是 和 的组合。和 数据构造函数已合并为单个数据构造函数。该函数已简化并重命名为 。和 函数也得到了简化。其实，只是.最后，我们应用到函数的原始实现。TrampolineLoopResultLoopRecurBouncerunLooptrampolinepurebindpureReturnBounceack

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

// 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(" "));

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

// 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(" "));

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

结论

如果要编写间接或相互递归的堆栈安全函数或一元堆栈安全函数，请使用 monad。如果要编写非monadic直接递归堆栈安全函数，请使用//模式。Trampolinelooprecurreturn

评论

3赞 1/24/2020
拥有正确的类型不仅是一个学术问题，而且考虑到您的代码将来可能会被转换为打字稿（即 fp-ts）。很好的答案！
0赞 3/17/2020
如果递归步骤也发生在 的第一个参数中，其中操作被传递 （），则递归有可能耗尽堆栈。在这种情况下，单子可以增强吗？bindbind(ack(m, n - 1), n => ack(m - 1, n))Trampoline
0赞 Aadit M Shah 3/17/2020
你能给我一个堆栈耗尽的例子吗？
0赞 customcommander 2/10/2021
顶部的这个循环/循环示例非常出色。如果你不介意的话，我可能会借用它。（有适当的归属 ofc）
1赞 Aadit M Shah 5/29/2022
@Mulan 在不挥手的情况下键入的一种方法是将类型变量约束为类似数组的类型，就像我们在 TypeScript 中所做的那样。例如。这是行多态性的一个示例，它不需要单独的 、 、 等类型。不幸的是，在 TypeScript 中无法使用上述定义，因为它不支持存在量化。...argsBouncedeclare const Bounce: <A extends unknown[], B>(func: (...args: A) => Trampoline<B>) => (...args: A) => Trampoline<B>Bounce0Bounce1Bounce2Trampoline

上一个：如何将输入管道传递到 Bash while 循环并在循环结束后保留变量

下一个：如何通过击键杀死 while 循环？