reduce（在FP中又名foldL）是Javascript中最通用的迭代高阶函数。例如，您可以实现map或filter reduce .我使用命令式循环来更好地说明算法：
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;
const result = map(inc)(xs);
console.log(result); // [2, 3, 4, 5]但是你不能从reduce中得出some或every，因为两者都能早点回来。
那么，一个更广义的部分归约函数会是什么样子呢？到目前为止，我已经提出了以下幼稚的实现：
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];
const result = foldLP(append)(takeN(3))([])(xs);
console.log(result); // [1,2,3]我还可以在foldLP方面实现map：
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]
缺点很明显：每当不需要提前退出机制时，就会不必要地调用always。转换和提前退出函数由foldLP静态组成，不能独立使用。有没有更有效的组合器，可以实现广义Array.prototype.reduce？
如果您查看调用堆栈，则归约函数acc => x => acc.concat([f(x)])的 return 语句必须跳过多个堆栈帧。这种堆栈操作让我想到了延续。也许有一种有效的方法可以在延续传递样式中解决此问题，以及经过调整的调用/cc 函数 - 或者至少使用生成器。
事实证明，一旦你习惯了CPS，就可以很容易地实现reduce的泛化：
const foldL = f => acc => xs => xs.length
? f(acc)(xs[0])(xss => foldL(f)(xss)(xs.slice(1)))
: acc;
const map = f => foldL(acc => x => cont => cont(acc.concat([f(x)])))([]);
const filter = pred => foldL(acc => x => cont => cont(pred(x) ? acc.concat([x]) : acc))([]);
const every = pred => foldL(acc => x => cont => pred(x) ? cont(true) : false)(true);
const some = pred => foldL(acc => x => cont => pred(x) ? true : cont(false))(false);
const takeN = n => foldL(acc => x => cont => acc.length < n ? cont(acc.concat([x])) : acc)([]);
const comp = f => g => x => f(g(x));
const not = f => x => !f(x);
const inc = x => ++x;
const odd = x => x & 1;
const even = not(odd);
const lt3 = x => x < 3;
const eq3 = x => x === 3;
const sqr = x => x * x;
const xs = [1, 2, 3, 4, 5];
map(inc)(xs); // [2, 3, 4, 5, 6]
filter(even)(xs); // [2, 4]
every(lt3)(xs); // false
some(lt3)(xs); // true
takeN(3)(xs); // [1, 2, 3]
// we can compose transforming functions as usual
map(comp(inc)(sqr))(xs); // [2, 5, 10, 17, 26]
// and the reducing functions as well
comp(map(inc))(filter(even))(xs); // [3, 5]
comp(takeN(2))(filter(odd))(xs); // [1, 3]
正如你所看到的，这不是真正的纯CPS，而是与直接风格混合在一起。这样做的好处是，foldL和通常的转换函数不必携带额外的延续参数，而是保持其正常的签名。
我只在代码的某些部分使用 CPS 函数，在这些代码中，它们对于实现所需的行为是不可替代的。CPS 是一个非常强大的结构，你总是使用你能用的表达最少的构造。
comp(takeN(2))(filter(odd))(xs)说明了实现的弱点之一（可能会有其他弱点）。归约函数的组合不会在数组元素的级别进行。因此，在计算最终结果之前需要一个中间数组（[1, 3, 5]）（[1, 3]）。但这就是换能器的问题...
惰性求值可以简单地解决这个问题。虽然我们在 JavaScript 中没有，但我们可以通过传递函数而不是值来模拟它：
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，您可以在其中轻松跳转到函数的末尾：
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