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

Question

我正在尝试在我的 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 循环，我正在以函数式风格进行编程，而且我无法访问尾调用优化，那么最好的策略是什么。

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

蹦床

我们可以通过改变我们写重复的方式来解决这个限制，但只是稍微改变一下。我们将返回两种蹦床类型之一，而不是直接或立即重复返回值，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

Currying也会稍微减慢速度，但我们可以使用递归的辅助函数来解决这个问题。这也很好，因为它隐藏了蹦床的实现细节，并且不期望调用者反弹返回值。这运行速度大约是上述 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

蹦床很好，但不得不担心打电话trampoline有点烦人在你的函数的返回值上。我们看到了另一种选择是使用辅助助手，但拜托，这也有点烦人。我相信你们中的一些人不太热衷于 Bounce和 Done wrapper 也是。

Clojure 创建了一个专门的蹦床接口(interface)，它使用了一对函数，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
             )
    )

延续 monad

这是我最喜欢的主题之一，所以我们将看看延续 monad 是什么样子。重用 loop和 recur ，我们实现了一个堆栈安全 cont可以使用 chain 对操作进行排序并使用 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作为一种安全的递归机制，您不仅无法从您的函数中同步返回一个值，而且速度会非常慢，您甚至不想使用您的函数

有些人发现了一个面试问答准备网站encourages this dreadful strategy

我们的什么 repeat看起来像使用 setTimeout – 注意它也是以连续传递方式定义的 – 即，我们必须调用 repeat使用回调( 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运行时间太长，我放弃了尝试测量它。我没有将其包含在下面的基准测试中，因为它太慢而无法被视为可行的方法。

promise

Promise 具有链接计算的能力并且是堆栈安全的。但是，实现堆栈安全repeat使用 Promises 意味着我们将不得不放弃我们的同步返回值，就像我们使用 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 )

// 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 来演示无限递归是可能的和高性能的，而不必牺牲同步返回值 – 100,000,000 下的递归 6 秒 - 与 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 次递归，但这次是以非阻塞方式。

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

在现代程序中，给定 Promises，我们将替换 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