如何在不进行尾部调用优化的情况下用功能性编程替代方法替换while循环？

Javascript中的示例

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

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

蹦床

我们可以通过更改重复写入的方式来解决此限制，但要稍做一些。而不是直接或立即返回值，我们将返回两种蹦床类型之一

Bounce

Done

trampoline

// trampolineconst 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-safeconst repeat = n => f => x =>  n === 0 ? Done(x) : Bounce(repeat (n - 1) (f), f(x))// apply trampoline to the result of an ordinary call repeatlet result = trampoline(repeat(1e6) (x => x + 1) (0))// no more stack overflowconsole.log(result) // 1000000

Currying也会使事情放慢一点，但是我们可以补救使用递归的辅助功能。这也很好，因为它隐藏了蹦床的实现细节，并且不希望调用者退回返回值。运行速度是上述速度的两倍

repeat

// aux helper hides trampoline implementation detail// runs about 2x as fastconst 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

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)) // 1000000console.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  )    )

延续单子

这是我最喜欢的主题之一，因此我们将继续使用延续单子。重用

loop

recur

cont

chain

runCont

repeat

cont

const identity = x =>  xconst recur = (...values) =>  ({ recur, values })const loop = run =>{ let r = run ()  while (r && r.recur === recur)    r = run (...r.values)  return r}// cont : 'a -> 'a contconst cont = x =>  k => recur (k, x)// chain : ('a -> 'b cont) -> 'a cont -> 'b contconst chain = f => mx =>  k => recur (mx, x => recur (f (x), k))// runCont : ('a -> 'b) -> a cont -> 'bconst 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)) // 1000000console.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 combinatorconst Y = f => {  const safeY = f =>    bounce((...xs) => f (safeY (f), ...xs))  return (...xs) =>    trampoline (safeY (f) (...xs))}// recur safely to your heart's contentconst 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 + 1const result = gadzillionTimes (add1) (0)console.log(result) // 100000000

setTimeout

好的，它 确实可以
工作，但是矛盾的是。如果数据集很小，则不需要，

setTimeout

setTimeout

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

我们

repeat

setTimeout

repeat

k

// do NOT implement recursion using setTimeoutconst 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 recursionsrepeat (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

承诺

承诺具有链接计算的能力并且是堆栈安全的。但是，

repeat

setTimeout

setTimeout

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

setTimeout

Promise

// sync// -----------------------------------------------------------------------------// repeat implemented with basic trampolineconsole.time('A')console.log(tramprepeat(1e6) (x => x + 1) (0))console.timeEnd('A')// 1000000// A 114 ms// repeat implemented with basic trampoline and aux helperconsole.time('B')console.log(auxrepeat(1e6) (x => x + 1) (0))console.timeEnd('B')// 1000000// B 64 ms// repeat implemented with cont monadconsole.time('C')console.log(contrepeat(1e6) (x => x + 1) (0))console.timeEnd('C')// 1000000// C 33 ms// repeat implemented with Yconsole.time('Y')console.log(yrepeat(1e6) (x => x + 1) (0))console.timeEnd('Y')// 1000000// Y 544 ms// repeat implemented with while loopconsole.time('D')console.log(whilerepeat(1e6) (x => x + 1) (0))console.timeEnd('D')// 1000000// D 4 ms// async// -----------------------------------------------------------------------------// repeat implemented with Promiseconsole.time('E')promiserepeat(1e6) (x => x + 1) (0) (console.log)console.timeEnd('E')// 1000000// E 2224 ms// repeat implemented with setTimeout; FAILEDconsole.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次 递归- 与之 相比，这是一个巨大的差异，而在相同的时间内只能进行 1000次 递归。

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: 15msconsole.time('JS1 100M');console.log (repeat (1e8, function (x) { return x + 1 }, 0));console.timeEnd('JS1 100M');// 100000000// JS1 100K: 5999ms

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

如果 出于某种原因，您想要非阻塞（异步）无限递归，我们可以依靠在计算开始时

setTimeout

这表明具有非阻塞要求并没有什么特别的。一

while

在一个现代程序中，给定

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