如何在没有尾调用优化的情况下用函数式编程替代方案替换 while 循环？
How do I replace while loops with a functional programming alternative without tail call optimization?
我正在 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;
}
但是在这一点上，感觉我已经为使用它的任何其他人做了更多 complicated/confusing，因为我不得不拖着一个自定义实用程序函数。我看到的唯一实际优势是它迫使我使循环变得纯净；但似乎只使用常规 while 循环并确保我保持一切纯净会更直接。
我还试图找出一种方法来创建一个生成器函数，该函数模仿 recursion/looping 的效果，然后使用实用函数（如 find 或 reduce）对其进行迭代。但是，我还没有想出一个可读的方法来做到这一点。
最后，用实用函数替换 for 循环使我想要完成的事情更加明显（例如，对每个元素做一件事，检查每个元素是否通过测试等）。然而，在我看来，一个 while 循环已经表达了我想要完成的事情（例如，迭代直到我们找到一个质数，迭代直到答案被充分优化，等等）。
所以在这之后，我的总体问题是：如果我需要一个 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)) // 1000
console.log(repeat(1e5) (x => x + 1) (0)) // Error: Uncaught RangeError: Maximum call stack size exceeded
蹦床
我们可以通过改变我们写 repeat 的方式来解决这个限制，但只是稍微改变一下。我们将 return 我们的两种蹦床类型之一，Bounce 或 Done，而不是直接 returning 一个值或立即重复出现。然后我们将使用我们的 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 也会稍微减慢速度，但我们可以使用递归的辅助函数来补救。这也很好，因为它隐藏了 trampoline 实现细节，并且不希望调用者反弹 return 值。这个 运行s 大约是上面 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 很好，但是不得不担心在函数的 return 值上调用 trampoline 有点烦人。我们看到另一种方法是使用辅助助手，但这也有点烦人。我相信你们中的一些人也不太喜欢 Bounce 和 Done 包装器。
Clojure 创建了一个专门的 trampoline 接口，它使用了一对函数，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
)
)
continuation monad
不过，这是我最喜欢的主题之一，所以我们将通过 continuation 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 作为一种安全的递归机制，你不仅不可能从你的函数中同步 return 一个值，它会非常慢你甚至不会想使用你的功能
有些人找到了一个面试问答准备网站 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 具有链接计算的能力并且是堆栈安全的。然而，使用 Promises 实现堆栈安全 repeat 意味着我们将不得不放弃我们的同步 return 值，就像我们使用 setTimeout 一样。我将其作为 "solution" 提供，因为它 确实 解决了问题，与 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 和第一个 class 函数
下面，我们使用石器时代 javascript 来证明无限递归是可能的，并且在 不必 牺牲同步 return 值的情况下是高效的 – 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延迟一个单frame 在计算的开始。该程序还使用石器时代 javascript 并在 8 秒内计算 100,000,000 次递归，但这次是以非阻塞方式。
这表明非阻塞要求并没有什么特别之处。 while 循环和 first-class 函数仍然是在不牺牲性能的情况下实现堆栈安全递归的唯一基本要求
在现代程序中，给定 Promise，我们会将 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
函数范式意义上的编程意味着我们以类型为指导来表达我们的算法。
要将尾递归函数转换为堆栈安全版本，我们必须考虑两种情况：
- 基本案例
- 递归案例
我们必须做出选择，这与标记的联合很相配。然而，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));
另见 unfold 其中（来自 Ramda 文档）
Builds a list from a seed value. Accepts an iterator function, which
returns either false to stop iteration or an array of length 2
containing the value to add to the resulting list and the seed to be
used in the next call to the iterator function.
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>
这个问题我想了很久。最近我发现需要一个功能性的 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"
None 这实际上将我们的 while 循环的核心变成了一个函数。但它确实允许我们使用内联循环。我只是想与任何可能有帮助的人分享这个。
更好的loop/recur模式
中描述的 loop/recur 模式有两点我不喜欢。请注意，我实际上喜欢 loop/recur 模式背后的想法。但是，我不喜欢它的实施方式。那么，让我们先看看我的实现方式吧。
// 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");
将此与上述答案中描述的 loop/recur 模式进行比较。
// 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");
如果您注意到，第二个 loop 函数的类型签名使用 default parameters (i.e. a?) and untagged unions（即 Recur a ∪ b）。这两个特性都与函数式编程范式不一致。
默认参数有问题
上述答案中的 loop/recur 模式使用默认参数来提供函数的初始参数。我认为这是对默认参数的滥用。您可以使用我的 loop.
版本轻松提供初始参数
// 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 conversion。
// 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)));
使用默认参数的loop版本不允许eta转换。另外，它强制你因为你不能在JavaScript中写(n = n, x = x) => ...。
未标记联合的问题
未标记的联合是不好的，因为它们会删除重要信息，即数据来自何处的信息。例如，因为我的 Result 类型被标记了，所以我可以区分 Return(Recur(0)) 和 Recur(0)。
另一方面，因为 Recur a ∪ b 的右侧变体没有标记，如果 b 专门化为 Recur a，即如果类型专门化为 Recur a ∪ Recur a，则无法确定Recur a是来自左侧还是右侧。
一种批评可能是 b 永远不会专门用于 Recur a，因此 b 未标记并不重要。这是该批评的一个简单反例。
// 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");
因此，未标记的联合是不安全的。然而，即使我们小心避免未标记联合的陷阱，我仍然更喜欢标记联合，因为标记在阅读和调试程序时提供有用的信息。恕我直言，标签使程序更易于理解和调试。
结论
引用 Zen of Python.
Explicit is better than implicit.
默认参数和未标记的联合是不好的，因为它们是隐式的，并且会导致歧义。
Trampoline monad
现在，我想换个话题谈谈 monad。接受的答案演示了堆栈安全的延续 monad。但是，如果您只需要创建一个 monadic 堆栈安全递归函数，那么您不需要 continuation monad 的全部功能。您可以使用 Trampoline monad。
Trampoline monad 是 Loop monad 的更强大的表亲，后者只是将 loop 函数转换为 monad。那么，让我们从了解 Loop monad 开始。然后我们将看到 Loop monad 的主要问题以及如何使用 Trampoline monad 来解决该问题。
// 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)));
请注意，loop 已拆分为 Loop 和 runLoop 函数。 Loop编辑的数据结构return是一个monad，pure和bind函数实现了它的monadic接口。我们使用 pure 和 bind 函数来编写 Ackermann function.
的直接实现
不幸的是，ack 函数不是堆栈安全的，因为它递归调用自身直到达到 pure 值。相反，我们希望 ack 到 return 一个类似于 Recur 的数据结构用于其归纳案例。但是，Recur 值的类型是 Result 而不是 Loop。 Trampoline monad.
解决了这个问题
// 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)));
Trampoline 数据类型是 Loop 和 Result 的组合。 Loop 和 Recur 数据构造函数已合并为一个 Bounce 数据构造函数。 runLoop 函数已简化并重命名为 trampoline。 pure 和 bind 函数也得到了简化。事实上，pure 就是 Return。最后，我们将 Bounce 应用于 ack 函数的原始实现。
Trampoline的另一个优点是它可以用来定义堆栈安全的相互递归函数。例如，下面是 Hofstadter Female and Male sequence 函数的实现。
// 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(" "));
编写monadic代码的主要痛点是callback hell。但是，这可以使用生成器来解决。
// 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(" "));
最后，相互递归函数也展示了具有单独 trampoline 函数的优势。它允许我们调用函数 returning 一个 Trampoline 值而不用实际 运行ing 它。这允许我们构建更大的 Trampoline 值，然后在需要时 运行 整个计算。
结论
如果您想编写间接或相互递归的堆栈安全函数，或单子堆栈安全函数，请使用 Trampoline 单子。如果您想直接编写非单子递归堆栈安全函数，请使用 loop/recur/return 模式。
我正在 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;
}
但是在这一点上，感觉我已经为使用它的任何其他人做了更多 complicated/confusing，因为我不得不拖着一个自定义实用程序函数。我看到的唯一实际优势是它迫使我使循环变得纯净；但似乎只使用常规 while 循环并确保我保持一切纯净会更直接。
我还试图找出一种方法来创建一个生成器函数，该函数模仿 recursion/looping 的效果，然后使用实用函数（如 find 或 reduce）对其进行迭代。但是，我还没有想出一个可读的方法来做到这一点。
最后，用实用函数替换 for 循环使我想要完成的事情更加明显（例如，对每个元素做一件事，检查每个元素是否通过测试等）。然而，在我看来，一个 while 循环已经表达了我想要完成的事情（例如，迭代直到我们找到一个质数，迭代直到答案被充分优化，等等）。
所以在这之后，我的总体问题是：如果我需要一个 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)) // 1000
console.log(repeat(1e5) (x => x + 1) (0)) // Error: Uncaught RangeError: Maximum call stack size exceeded
蹦床
我们可以通过改变我们写 repeat 的方式来解决这个限制，但只是稍微改变一下。我们将 return 我们的两种蹦床类型之一，Bounce 或 Done，而不是直接 returning 一个值或立即重复出现。然后我们将使用我们的 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 也会稍微减慢速度，但我们可以使用递归的辅助函数来补救。这也很好，因为它隐藏了 trampoline 实现细节，并且不希望调用者反弹 return 值。这个 运行s 大约是上面 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 很好，但是不得不担心在函数的 return 值上调用 trampoline 有点烦人。我们看到另一种方法是使用辅助助手，但这也有点烦人。我相信你们中的一些人也不太喜欢 Bounce 和 Done 包装器。
Clojure 创建了一个专门的 trampoline 接口，它使用了一对函数，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
)
)
continuation monad
不过，这是我最喜欢的主题之一，所以我们将通过 continuation 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 作为一种安全的递归机制，你不仅不可能从你的函数中同步 return 一个值，它会非常慢你甚至不会想使用你的功能
有些人找到了一个面试问答准备网站 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 具有链接计算的能力并且是堆栈安全的。然而，使用 Promises 实现堆栈安全 repeat 意味着我们将不得不放弃我们的同步 return 值，就像我们使用 setTimeout 一样。我将其作为 "solution" 提供，因为它 确实 解决了问题，与 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 和第一个 class 函数
下面，我们使用石器时代 javascript 来证明无限递归是可能的，并且在 不必 牺牲同步 return 值的情况下是高效的 – 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延迟一个单frame 在计算的开始。该程序还使用石器时代 javascript 并在 8 秒内计算 100,000,000 次递归，但这次是以非阻塞方式。
这表明非阻塞要求并没有什么特别之处。 while 循环和 first-class 函数仍然是在不牺牲性能的情况下实现堆栈安全递归的唯一基本要求
在现代程序中，给定 Promise，我们会将 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
函数范式意义上的编程意味着我们以类型为指导来表达我们的算法。
要将尾递归函数转换为堆栈安全版本，我们必须考虑两种情况：
- 基本案例
- 递归案例
我们必须做出选择，这与标记的联合很相配。然而，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));
另见 unfold 其中（来自 Ramda 文档）
Builds a list from a seed value. Accepts an iterator function, which returns either false to stop iteration or an array of length 2 containing the value to add to the resulting list and the seed to be used in the next call to the iterator function.
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>
这个问题我想了很久。最近我发现需要一个功能性的 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"
None 这实际上将我们的 while 循环的核心变成了一个函数。但它确实允许我们使用内联循环。我只是想与任何可能有帮助的人分享这个。
更好的loop/recur模式
loop/recur 模式有两点我不喜欢。请注意，我实际上喜欢 loop/recur 模式背后的想法。但是，我不喜欢它的实施方式。那么，让我们先看看我的实现方式吧。
// 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");
将此与上述答案中描述的 loop/recur 模式进行比较。
// 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");
如果您注意到，第二个 loop 函数的类型签名使用 default parameters (i.e. a?) and untagged unions（即 Recur a ∪ b）。这两个特性都与函数式编程范式不一致。
默认参数有问题
上述答案中的 loop/recur 模式使用默认参数来提供函数的初始参数。我认为这是对默认参数的滥用。您可以使用我的 loop.
// 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 conversion。
// 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)));
使用默认参数的loop版本不允许eta转换。另外，它强制你(n = n, x = x) => ...。
未标记联合的问题
未标记的联合是不好的，因为它们会删除重要信息，即数据来自何处的信息。例如，因为我的 Result 类型被标记了，所以我可以区分 Return(Recur(0)) 和 Recur(0)。
另一方面，因为 Recur a ∪ b 的右侧变体没有标记，如果 b 专门化为 Recur a，即如果类型专门化为 Recur a ∪ Recur a，则无法确定Recur a是来自左侧还是右侧。
一种批评可能是 b 永远不会专门用于 Recur a，因此 b 未标记并不重要。这是该批评的一个简单反例。
// 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");
因此，未标记的联合是不安全的。然而，即使我们小心避免未标记联合的陷阱，我仍然更喜欢标记联合，因为标记在阅读和调试程序时提供有用的信息。恕我直言，标签使程序更易于理解和调试。
结论
引用 Zen of Python.
Explicit is better than implicit.
默认参数和未标记的联合是不好的，因为它们是隐式的，并且会导致歧义。
Trampoline monad
现在，我想换个话题谈谈 monad。接受的答案演示了堆栈安全的延续 monad。但是，如果您只需要创建一个 monadic 堆栈安全递归函数，那么您不需要 continuation monad 的全部功能。您可以使用 Trampoline monad。
Trampoline monad 是 Loop monad 的更强大的表亲，后者只是将 loop 函数转换为 monad。那么，让我们从了解 Loop monad 开始。然后我们将看到 Loop monad 的主要问题以及如何使用 Trampoline monad 来解决该问题。
// 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)));
请注意，loop 已拆分为 Loop 和 runLoop 函数。 Loop编辑的数据结构return是一个monad，pure和bind函数实现了它的monadic接口。我们使用 pure 和 bind 函数来编写 Ackermann function.
不幸的是，ack 函数不是堆栈安全的，因为它递归调用自身直到达到 pure 值。相反，我们希望 ack 到 return 一个类似于 Recur 的数据结构用于其归纳案例。但是，Recur 值的类型是 Result 而不是 Loop。 Trampoline monad.
// 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)));
Trampoline 数据类型是 Loop 和 Result 的组合。 Loop 和 Recur 数据构造函数已合并为一个 Bounce 数据构造函数。 runLoop 函数已简化并重命名为 trampoline。 pure 和 bind 函数也得到了简化。事实上，pure 就是 Return。最后，我们将 Bounce 应用于 ack 函数的原始实现。
Trampoline的另一个优点是它可以用来定义堆栈安全的相互递归函数。例如，下面是 Hofstadter Female and Male sequence 函数的实现。
// 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(" "));
编写monadic代码的主要痛点是callback hell。但是，这可以使用生成器来解决。
// 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(" "));
最后，相互递归函数也展示了具有单独 trampoline 函数的优势。它允许我们调用函数 returning 一个 Trampoline 值而不用实际 运行ing 它。这允许我们构建更大的 Trampoline 值，然后在需要时 运行 整个计算。
结论
如果您想编写间接或相互递归的堆栈安全函数，或单子堆栈安全函数，请使用 Trampoline 单子。如果您想直接编写非单子递归堆栈安全函数，请使用 loop/recur/return 模式。