2

使用数组时，经常需要中间表示 - 特别是在函数式编程中，其中数据通常被视为不可变：

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 中避免这种行为以获得更有效的迭代算法？

4

1 回答 1

5

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

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

map当所需的函数始终相同时，为什么我们应该为每个调用传递一个归约函数，concat即？

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

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

Transducer 只有结合功能组合才能发挥其表达能力：

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

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

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

至此，maptransducer 的定义就可以理解了：可组合性需要匹配的函数签名。

请注意，转换器堆栈的评估顺序从左到右，因此与函数组合的正常顺序相反。

传感器的一个重要特性是它们能够提前退出迭代过程。在选择的实现中，这种行为是通过实现转换器和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 开发人员来说应该更熟悉。

于 2016-02-19T13:33:19.783 回答