Dav*_*ith 38 javascript recursion functional-programming while-loop tail-call-optimization
我正在尝试使用JavaScript中更实用的样式; 因此,我已经用for实用函数替换了for循环,例如map和reduce.但是,我没有找到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循环,我正在以函数式编程,而且我无法访问尾调用优化,那么什么是最佳策略.
Tha*_*you 73
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) // 1000000Currying会使事情变得缓慢,但我们可以使用辅助函数来补救递归.这也很好,因为它隐藏了trampoline实现细节,并且不希望调用者反弹返回值.其运行速度约为上述速度的两倍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创建了一个专门的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延续monad
这是我最喜欢的主题之一,所以我们将看看Continuation monad的样子.我们还会更进一步,使用辅助函数()隐藏函数内部的trampoline实现细节,这样调用者就不必担心每次都会弹回返回值looprecur
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
)
)
cont 组合子
Y组合子是我的精神组合者; 如果没有在其他技术中占有一席之地,这个答案将是不完整的.但是,Y组合器的大多数实现都不是堆栈安全的,并且如果用户提供的函数重复次数过多,它将会溢出.由于这个答案都是关于保持堆栈安全行为的,所以我们当然会chain以安全的方式实施- 再次依靠我们可信赖的蹦床.
runCont 演示了扩展易于使用,堆栈安全,同步无限递归的能力,而不会使您的功能混乱.
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 msrepeat循环的实用性
但是说实话:当我们忽略一个更明显的潜在解决方案时,这是很多仪式:使用cont或Y循环,但隐藏在功能界面后面
对于所有意图和目的,此Y功能与上面提供的功能完全相同 - 除了这个功能大约快一到两倍(Y/ while解决方案除外).哎呀,它可以说也更容易阅读.
当然,这个函数可能是一个人为的例子 - 并非所有的递归函数都可以很容易地转换为一个for或while循环,但是在这种可能的情况下,最好像这样做.当一个简单的循环不起作用时,保存蹦床和延续物以进行繁重的提升.
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)) // 10000repeat 不是堆栈溢出问题的解决方案
好的,它确实有效,但只是矛盾的.如果您的数据集很小,则不需要,loop因为没有堆栈溢出.如果您的数据集很大而且您使用的recur是一种安全的递归机制,那么您不仅无法同步返回函数中的值,它也会如此慢,您甚至不想使用您的函数
有些人发现了一个面试Q&A准备网站,鼓励这种可怕的策略
我们for看起来像是使用什么while- 注意它也是以延续传递方式定义的 - 也就是说,我们必须setTimeout使用callback(setTimeout)来调用以获得最终值
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需要很长时间才能运行,我放弃了尝试测量它.我没有在下面的基准测试中包括这个,因为它太慢甚至不被认为是一种可行的方法.
承诺
Promise具有链式计算和堆栈安全的能力.但是,repeat使用Promises 实现堆栈安全意味着我们必须放弃我们的同步返回值,就像我们使用的那样setTimeout.我提供这个作为"解决方案",因为它确实解决了问题,不像repeat,但是与蹦床或延续monad相比,这种方式非常简单.然而,正如您可能想象的那样,性能有点糟糕,但远不及k上面的例子那么糟糕
值得注意的是,在此解决方案中,Promise实现细节完全隐藏在调用者之外.提供单个延续作为第4个参数,并在计算完成时调用它.
// 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环是很多快-几乎一样快100倍(最好比较最坏的时候-但不包括异步答案:repeat和setTimeout)
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))石器时代的JavaScript
使用较新的ES6语法演示了上述技术,但您可以在尽可能早的JavaScript版本中实现蹦床 - 它只需要setTimeout和第一类函数
下面,我们使用石器时代javascript来演示无限递归是可能的和高性能而不必牺牲同步返回值 - 在6秒内100,000,000次递归- 这是一个显着的差异,相比之下,在相同的时间内只能进行1,000次递归.setTimeout
// 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的非阻塞无限递归
如果由于某种原因,您想要非阻塞(异步)无限递归,我们可以依赖于在计算开始时while推迟单个帧.该程序还使用石器时代javascript并在8秒内计算100,000,000次递归,但这次是以非阻塞方式.
这表明具有非阻塞要求没有什么特别之处.一setTimeout回路和一流的功能仍然实现栈的安全递归在不牺牲性能的唯一的根本要求
在一个现代程序中,给定Promises,我们会用Promise一个Promise 替换这个函数.
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: 5999msloop/recur模式我不喜欢接受的答案中描述的loop/recur模式的两件事。请注意，我实际上喜欢/模式背后的想法。但是，我不喜欢它的实施方式。所以，让我们首先看看我将如何实现它。looprecur
// 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函数的类型签名使用默认参数（即a?）和未标记的联合（即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 转换。
// 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) => ...JavaScript 编写。
未标记的联合是不好的，因为它们会删除重要信息，即数据来自何处的信息。例如，因为我的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");因此，未标记的联合是不安全的。然而，即使我们小心避免未标记联合的陷阱，我仍然更喜欢标记联合，因为标记在阅读和调试程序时提供了有用的信息。恕我直言，标签使程序更易于理解和调试。
显式优于隐式。
默认参数和未标记的联合是不好的，因为它们是隐式的，并且会导致歧义。
Trampoline单子现在，我想换个角度谈谈 monad。接受的答案演示了一个堆栈安全的延续 monad。但是，如果您只需要创建一个 monadic 堆栈安全递归函数，那么您就不需要延续 monad 的全部功能。您可以使用Trampoline单子。
该Trampoline单子是更强大的表妹Loop单子，这仅仅是loop转换成一个单子功能。所以，让我们从理解Loopmonad开始。然后我们将看到Loopmonad的主要问题以及如何使用Trampolinemonad 来解决该问题。
// 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已经拆分成aLoop和arunLoop函数了。by 返回的数据结构Loop是一个 monad，pure和bind函数实现了它的 monadic 接口。我们使用pure和bind函数来编写阿克曼函数的简单实现。
不幸的是，该ack函数不是堆栈安全的，因为它会递归调用自身直到达到某个pure值。相反，我们希望为其归纳案例ack返回一个Recur类似的数据结构。但是，Recur值是类型Result而不是Loop。这个问题是由Trampolinemonad解决的。
// 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 女性和男性序列函数的实现。
// 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 代码的主要痛点是回调地狱。但是，这可以使用生成器解决。
// 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函数的优势。它允许我们调用一个返回Trampoline值的函数，而无需实际运行它。这允许我们构建更大的Trampoline值，然后在需要时运行整个计算。
如果您想编写间接或相互递归的堆栈安全函数或 monadic 堆栈安全函数，请使用Trampolinemonad。如果你想写非单子直接递归栈的安全保护功能，然后使用loop/ recur/return模式。
| 归档时间： |
|
| 查看次数： |
11912 次 |
| 最近记录： |