如何在没有尾调用优化的情况下用函数式编程替代方法替换 while 循环? [英] How do I replace while loops with a functional programming alternative without tail call optimization?

问题描述

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

I am experimenting with a more functional style in my JavaScript; therefore, I have replaced for loops with utility functions such as map and reduce. However, I have not found a functional replacement for while loops since tail call optimization is generally not available for JavaScript. (From what I understand ES6 prevents tail calls from overflowing the stack but does not optimize their performance.)

我解释了我在下面尝试过的内容，但 TLDR 是:如果我没有尾调用优化，那么实现while循环的功能方式是什么?

I explain what I have tried below, but the TLDR is: If I don't have tail call optimization, what is the functional way to implement while loops?

我尝试过的:

创建一个while"实用函数:

Creating a "while" utility function:

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

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

Since tail call optimization isn't available I could rewrite this as:

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

然而，在这一点上，我让我的代码变得更加复杂/让其他使用它的人感到困惑，因为我不得不拖着一个自定义实用程序函数.我看到的唯一实际优势是它迫使我使循环纯；但似乎只使用常规的 while 循环并确保我保持一切纯净会更直接.

However at this point it feels like I have made my code more complicated/confusing for anyone else who uses it, since I have to lug around a custom utility function. The only practical advantage that I see is that it forces me to make the loop pure; but it seems like it would be more straightforward to just use a regular while loop and make sure that I keep everything pure.

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

I also tried to figure out a way to create a generator function that mimics the effects of recursion/looping and then iterate over it using a utility function like find or reduce. However, I haven't figured out an readable way to do that yet.

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

Finally, replacing for loops with utility functions makes it more apparent what I am trying to accomplish (e.g. do a thing to each element, check if each element passes a test, etc.). However, it seems to me that a while loop already expresses what I am trying to accomplish (e.g. iterate until we find a prime number, iterate until the answer is sufficiently optimized, etc.).

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

So after all this, my overall question is: If I need a while loop, I am programming in a functional style, and I don't have access to tail call optimization, then what is the best strategy.

推荐答案

JavaScript 中的一个例子

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

Here's an example using JavaScript. Currently, most browsers do not support tail call optimisation and therefore the following snippet will fail

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 函数来处理循环.

We can work around this limitation by changing the way we write repeat, but only slightly. Instead of returning a value directly or immediately recurring, we will return one of our two trampoline types, Bounce or Done. Then we will use our trampoline function to handle the loop.

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

Currying slows things down a little bit too, but we can remedy that using an auxiliary function for the recursion. This is nice too because it hides the trampoline implementation detail and does not expect the caller to bounce the return value. This runs about twice as fast as the above 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 包装器.

Trampolines are nice and all but it's kind of annoying to have to have to worry about calling trampoline on your function's return value. We saw the alternative was to use an auxiliary helper, but c'mon that's kind of annoying, too. I'm sure some of you aren't too keen about the Bounce and Done wrappers, too.

Clojure 创建了一个专门的trampoline 接口，它使用了一对函数，loop 和 recur——这对串联函数有助于对程序进行非常优雅的表达

Clojure creates a specialised trampoline interface that uses a pair of functions, loop and recur – this tandem pair lends itself to a remarkably elegant expression of a program

哦，它也真的很快

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

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

Initially this style will feel foreign, but over time I am finding it to be the most consistent while producing durable programs. Comments below help ease you into the expression-rich syntax -

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 是什么样子.重用loop和recur，我们实现了一个栈安全的cont，可以使用chain对操作进行排序并运行操作序列使用 runCont.对于 repeat，这是毫无意义的(而且很慢)，但是在这个简单的例子中看到 cont 的机制是很酷的 -

This is one of my favourite topics tho, so we're gonna see what this looks like with the continuation monad. Reusing loop and recur, we implement a stack-safe cont that can sequence operations using chain and run operation sequences using runCont. For repeat, this is senseless (and slow), but it's cool to see the mechanics of cont at work in this simple example -

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 combinator

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

The Y combinator is my spirit combinator; this answer would be incomplete without giving it some place amongst the other techniques. Most implementations of the Y combinator however, are not stack-safe and will overflow if the user-supplied function recurs too many times. Since this answer is all about preserving stack-safe behaviour, of course we'll implement Y in a safe way – again, relying on our trusty trampoline.

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

Y demonstrates the ability to extend easy-to-use, stack-safe, synchronous infinite recursion without cluttering up your function.

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

Practicality with while loop

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

But let's be honest: that's a lot of ceremony when we're overlooking one of the more obvious potential solutions: use a for or while loop, but hide it behind a functional interface

对于所有意图和目的，这个 repeat 函数的工作方式与上面提供的函数完全相同——除了这个函数快一到两亿倍(loop 除外)>/recur 解决方案).哎呀，它也可以说更容易阅读.

For all intents and purposes, this repeat function works identically to the ones provided above – except this one is about one or two gadzillion times faster (with exception to the loop/recur solution). Heck, it's arguably a lot easier to read too.

诚然，这个函数可能是一个人为的例子——并非所有的递归函数都可以如此轻松地转换为 for 或 while 循环，但在这种情况下可能，最好这样做.当一个简单的循环不起作用时，保存蹦床和继续进行繁重的工作.

Granted, this function is perhaps a contrived example – not all recursive functions can be converted to a for or while loop so easily, but in such a scenario where it's possible, it's probably best to just do it like this. Save the trampolines and continuations for heavy lifting when a simple loop won't do.

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 is NOT a solution to the stack overflow problem

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

OK, so it does work, but only paradoxically. If your dataset is small, you don't need setTimeout because there will be no stack overflow. If your dataset is large and you use setTimeout as a safe recursion mechanism, not only do you make it impossible to synchronously return a value from your function, it will be so F slow you won't even want to use your function

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

Some people have found an interview Q&A prep site that encourages this dreadful strategy

使用 setTimeout 时我们的 repeat 会是什么样子——注意它也是以延续传递风格定义的——即，我们必须用一个回调(k)获取最终值

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) to get the final value

// 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 也需要很长时间才能运行，以至于我放弃了对其进行测量的尝试.我没有将其包含在下面的基准测试中，因为它太慢而无法被视为可行的方法.

I can't stress enough how bad this is. Even 1e5 takes so long to run that I gave up trying to measure it. I'm not including this in the benchmarks below because it's just too slow to even be considered a viable approach.

承诺

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

Promises have the ability to chain computations and are stack safe. However, achieving a stack-safe repeat using Promises means we'll have to give up our synchronous return value, the same way we did using setTimeout. I'm providing this as a "solution" because it does solve the problem, unlike setTimeout, but in a way that's very simple compared to the trampoline or continuation monad. As you might imagine though, the performance is somewhat bad, but nowhere near as bad as the setTimeout example above

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

Worth noting in this solution, the Promise implementation detail is completely hidden from the caller. A single continuation is provided as a 4th argument and its called when the computation is complete.

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 倍(比较最好和最差 - 但不包括异步答案:setTimeoutcode> 和 Promise)

Seriously, the while loop is a lot faster - like almost 100x faster (when comparing best to worst – but not including async answers: setTimeout and 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 和第一类函数

The above techniques are demonstrated using newer ES6 syntaxes, but you could implement a trampoline in the earliest possible version of JavaScript – it only requires while and first class functions

下面，我们使用石器时代的 javascript 来证明无限递归是可能的和高性能的，而必然牺牲同步返回值 - 100,000,000 次6 下的递归strong> 秒 - 与 setTimeout 相比，这是一个巨大的差异，后者只能在相同的时间内 1,000 次递归.

Below, we use stone age javascript to demonstrate infinite recursion is possible and performant without necessarily sacrificing a synchronous return value – 100,000,000 recursions in under 6 seconds - this is a dramatic difference compared to setTimeout which can only 1,000 recursions in the same amount of time.

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 次递归，但这次是以非阻塞方式进行的.

If, for some reason, you want non-blocking (asynchronous) infinite recursion, we can rely on setTimeout to defer a single frame at the start of the computation. This program also uses stone age javascript and computes 100,000,000 recursions in under 8 seconds, but this time in a non-blocking way.

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

This demonstrates that there's nothing special about having a non-blocking requirement. A while loop and first-class functions are still the only fundamental requirement to achieve stack-safe recursion without sacrificing performance

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

In a modern program, given Promises, we would substitute the setTimeout call for a single 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

这篇关于如何在没有尾调用优化的情况下用函数式编程替代方法替换 while 循环?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！