javascript - 如何实现更通用的 reduce 功能以允许提前退出？

Question

reduce(在 FP 中又称为 foldL)是 Javascript 中最通用的迭代高阶函数。例如，您可以根据 reduce 实现 map 或 filter。我使用命令式循环来更好地说明算法:

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？

如果你查看调用堆栈，reducing 函数 acc => x => acc.concat([f(x)]) 的返回语句将不得不跳过几个堆栈帧.这种堆栈操作让我想到了延续。也许有一种有效的方法可以解决 Continuation Passing Style 中的这个问题，同时使用经过调整的 call/cc 函数 - 或者至少使用生成器。

Answer 1

事实证明，一旦您习惯了 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，而是混合了 Direct Style。这有一个很大的好处，即 foldL 和通常的转换函数不必携带额外的延续参数，而是保持它们的正常签名。

我只在部分代码中使用 CPS 函数，它们对于实现所需的行为是不可替代的。 CPS 是一种极其强大的结构，您总是会尽可能使用表达能力最低的结构。

comp(takeN(2))(filter(odd))(xs) 说明了该实现的一个弱点(可能还有其他弱点)。归约函数的组合不发生在数组元素的级别。因此，在计算最终结果 ([1, 3]) 之前，需要一个中间数组 ([1, 3, 5])。但这是换能器的问题......