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

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]

请注意，此实现更多的是概念验证，而不是成熟的解决方案。传感器的明显好处是：

• 没有中间表示
• 纯功能且简洁的解决方案
• 通用性（适用于任何聚合/集合，而不仅仅是数组）
• 非凡的代码可重用性（reducers/transformers是具有常用签名的常见功能）

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

这种方法对于 Javascript 解决方案是否足够惯用被认为是有争议的。我更喜欢这种实用的风格。然而，最常见的转换器库是以对象风格实现的，对于 OO 开发人员来说应该更熟悉。

Answer 2

您可以重复地从另一个迭代器创建一个新的迭代器，应用任何这些操作（过滤、映射、切片），并像这样进行链接，而无需创建任何数组，直到到达链的末尾。

ECMAScript 2025 包含迭代器辅助方法，使这项任务变得简单。您的代码只需要从初始数组中获取迭代器，然后您可以链接与您使用的名称相同的方法，区别在于现在它们是迭代器辅助方法，而不是数组方法。对于

slice(0, 2)

，您可以使用相应的

take(2)

调用。要使用迭代器链，只需在链的末尾附加

toArray()

即可：

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

// No more unnecessary intermediate array:
const result1 = xs.values().map(square).filter(odd).toArray();
console.log(...result1); // => [1,9,25,49,81]

// ...even if you just need the first two results:
const result2 = xs.values().map(square).filter(odd).take(2).toArray();
console.log(...result2); // => [1,9]