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包装器。

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

延续单子

这是我最喜欢的主题之一，因此我们将继续使用延续单子。重用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 循环实用

但是说实话：当我们忽略一个更明显的潜在解决方案时，这是很多仪式：使用foror 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用作安全的递归机制，则不仅使您无法从函数中同步返回值，而且速度太慢，您甚至都不想使用函数

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

我们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需要很长时间才能运行，以至于我放弃了尝试对其进行测量。我没有在下面的基准测试中包括它，因为它太慢了，甚至不能被认为是可行的方法。

承诺

承诺具有链接计算的能力并且是堆栈安全的。但是，repeat使用Promises
实现堆栈安全意味着我们必须放弃同步返回值，就像使用一样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环是 很多 快-几乎一样快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来证明无限递归是可能的，并且性能 不一定会 牺牲同步返回值- 在 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: 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回路和一流的功能仍然实现栈的安全递归在不牺牲性能的唯一的根本要求

在一个现代程序中，给定setTimeoutPromise ，我们将用一个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