执行数组迭代时如何避免中间结果？

Question

使用数组时，通常需要中间表示形式-尤其是在函数编程中，在这种编程中，数据通常被视为不可变的：

const square = x => x * x;
const odd = x => (x & 1) === 1;
let xs = [1,2,3,4,5,6,7,8,9];

// unnecessary intermediate array:
xs.map(square).filter(odd); // [1,4,9,16,25,36,49,64,81] => [1,9,25,49,81]

// even worse:
xs.map(square).filter(odd).slice(0, 2); // [1,9]

如何在Javascript / Ecmascript 2015中避免这种行为，以获得更有效的迭代算法？

Answer 1

换能器是避免迭代算法中出现中间结果的一种可能方法。为了更好地理解它们，您必须意识到，换能器本身是毫无意义的：

// map transducer
let map = tf => rf => acc => x => rf(acc)(tf(x));

map当要求的功能始终相同时，为什么要为每个调用传递一个归约函数concat？

这个问题的答案位于官方的传感器定义中：

换能器是可组合的算法转换。

换能器仅结合功能组成来发挥其表达能力：

const comp = f => g => x => f(g(x));
let xf = comp(filter(gt3))(map(inc));

foldL(xf(append))([])(xs);

comp传递了任意数量的换能器（filter和map）和单个归约函数（append）作为最终参数。由此comp构建不需要中间数组的转换序列。每个数组元素在下一个元素排成一行之前都要经过整个序列。

此时，map换能器的定义是可以理解的：可组合性需要匹配的功能签名。

注意，换能器叠层的评估顺序从左到右，因此与功能组合的正常顺序相反。

换能器的一个重要属性是其尽早退出迭代过程的能力。在所选的实现方式中，此行为是通过实现换能器并foldL以连续传递方式实现的。另一种选择是惰性评估。这是CPS实施：

const foldL = rf => acc => xs => {
  return xs.length
   ? rf(acc)(xs[0])(acc_ => foldL(rf)(acc_)(xs.slice(1)))
   : acc;
};

// transducers
const map = tf => rf => acc => x => cont => rf(acc)(tf(x))(cont);
const filter = pred => rf => acc => x => cont => pred(x) ? rf(acc)(x)(cont) : cont(acc);
const takeN = n => rf => acc => x => cont =>
 acc.length < n - 1 ? rf(acc)(x)(cont) : rf(acc)(x)(id);

// reducer
const append = xs => ys => xs.concat(ys);

// transformers
const inc = x => ++x;
const gt3 = x => x > 3;

const comp = f => g => x => f(g(x));
const liftC2 = f => x => y => cont => cont(f(x)(y));
const id = x => x;

let xs = [1,3,5,7,9,11];

let xf = comp(filter(gt3))(map(inc));
foldL(xf(liftC2(append)))([])(xs); // [6,8,10,12]

xf = comp(comp(filter(gt3))(map(inc)))(takeN(2));
foldL(xf(liftC2(append)))([])(xs); // [6,8]

请注意，此实现更多是概念验证，没有完善的解决方案。换能器的明显好处是：

• 无中间表示
• 纯粹实用且简洁的解决方案
• 通用性（使用任何聚合/集合，而不仅仅是数组）
• 非凡的代码可重用性（缩减器/变压器是具有其通常签名的常用功能）

从理论上讲，CPS与命令式循环一样快，至少在Ecmascript 2015中如此，因为所有尾部调用都具有相同的返回点，从而可以共享相同的堆栈帧（TCO）。

对于Javascript解决方案而言，这种方法是否足够惯用，这是有争议的。我更喜欢这种功能风格。但是，最常见的换能器库是以对象样式实现的，对OO开发人员来说应该看起来更熟悉。