如何实现更普遍降低功能允许提前退场? [英] How to implement a more general reduce function to allow early exit?
问题描述
减少
(又名与foldl
在FP)是在Javascript中最一般的迭代高阶函数。您可以实现,例如,地图
或过滤
而言减少
。我用命令式循环更好地说明算法:
reduce
(aka foldL
in FP) is the most general iterative higher order function in Javascript. You can implement, for instance, map
or filter
in terms of reduce
. I've used an imperative loop to better illustrate the algorithm:
const foldL = f => acc => xs => {
for (let i = 0; i < xs.length; i++) {
acc = f(acc)(xs[i]);
}
return acc;
};
const map = f => xs => {
return foldL(acc => x => acc.concat([f(x)]))([])(xs);
}
let xs = [1, 2, 3, 4];
const inc = x => ++x;
map(inc)(xs); // [2, 3, 4, 5]
但是,你不能获得部分
或每个
从减少
,因为两者都能够提前返回。
But you can't derive some
or every
from reduce
, because both are able to return early.
那么,如何能在更广义的部分减少功能是什么样子?到现在为止,我想出了以下幼稚的做法:
So how can a even more generalized partial reduce function look like? Until now I've come up with following naive implementation:
const foldLP = f => pred => acc => xs => {
for (let i = 0, r; i < xs.length; i++) {
r = pred(i, acc, xs[i]);
if (r === true) { // normal iteration
acc = f(acc)(xs[i]);
} else if (r === false) { // early exit
break;
} /* else { // skip iteration
continue;
} */
}
return acc;
};
const takeN = n => (idx, acc, x) => idx < n;
const append = xs => ys => xs.concat(ys);
let xs = [1,2,3,4,5];
foldLP(append)(takeN(3))([])(xs); // [1,2,3]
我也可以实施地图
而言 foldLP
:
const always = x => y => x;
const map = f => xs => {
return foldLP(acc => x => acc.concat([f(x)]))(always(true))([])(xs);
}
map(inc)(xs); // [2,3,4,5,6]
的缺点是显而易见的:当不需要提前退出机制,总是
不必要调用。转化和早期退出功能是由 foldLP
静态组成,不能独立使用。有没有更有效的组合子,使广义 Array.prototype.reduce
?
The drawback is obvious: Whenever an early exit mechanism isn't needed, always
is invoked unnecessarily. The transforming and early exiting function are composed statically by foldLP
and can't be used independently. Is there a more efficient combinator, that enables a generalized Array.prototype.reduce
?
如果你看看调用堆栈,还原功能 ACC =&gt;中return语句; X =&GT; acc.concat([F(X)])
将必须跳过几个堆栈帧。这种堆栈操作的让我觉得延续的。也许有解决继续与适于呼叫/ cc的函数传递样式沿着这个问题的有效方法。 - 或至少与发电机
If you look at the call stack, the return statement of the reducing function acc => x => acc.concat([f(x)])
would have to skip several stack-frames. This kind of stack manipulation makes me think of continuations. Maybe there is an efficient way to solve this problem in Continuation Passing Style along with an adapted call/cc function - or at least with a generator.
推荐答案
懒惰的评价平凡的解决这个问题。虽然我们没有在JavaScript中,我们可以通过传递一个函数,而不是一个值的效仿:
Lazy evaluation solves this trivially. While we don't have that in JavaScript, we can emulate it by passing a function instead of a value:
const foldR = f => acc => xs => xs.length
? f(xs[0])(() => foldR(f)(acc)(xs.slice(1)))
: acc // ^^^^^ "lazy"
const map = f => foldR(x => acc => [f(x)].concat(acc()))([])
const every = f => foldR(x => acc => f(x) && acc())(true)
// ^^^^^^^^ short-circuited - f(x) ? acc() : false
let xs = [1, 2, 3, 4];
console.log(map(x => x+1)(xs)); // [2, 3, 4, 5]
console.log(every(x => x%2==0)(xs)); // false
另一种方法是使用CPS,在那里你可以很容易地跳转到函数的末尾:
An alternative would be to use CPS, where you can easily jump to the end of the function:
const foldL = f => acc => xs => cont => xs.length
? f(acc)(xs[0])(res => foldL(f)(res)(xs.slice(1))(cont))
: cont(acc);
const map = f => foldL(acc => x => cont => f(x)(res => cont(acc.concat([res]))))([]);
//const every = f => // xs => cont =>
// foldL(acc => x => c => f(x)(res => c(acc && res)))(true) // (xs)(cont)
// ^^^^ eager call
const every = f => xs => cont =>
foldL(acc => x => c => acc ? f(x)(c) : cont(false))(true)(xs)(cont)
// call only when acc=true ^^^^ ^^^^^^^^^^^ jump out early otherwise
let xs = [1, 2, 3, 4];
let inc = x => cont => cont(x+1);
map(inc)(xs)(console.log.bind(console)); // [2, 3, 4, 5]
let even = x => cont => cont(x%2==0)
every(even)(xs)(console.log.bind(console)); // false
这篇关于如何实现更普遍降低功能允许提前退场?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!