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

当使用数组时，有规律地需要中间表示 - 特别是在与功能的编程连接，其中数据常常被视为不可变：如何在执行数组迭代时避免中间结果？

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此行为，以获得更高效的迭代算法？

来源

2016-02-19 rand

你看过发电机吗？ – deceze

@deceze我对于生成器有一点经验，但是和迭代器一样，它们似乎是一个可能的解决方案。你有代码示例吗？ – rand

我没有超越MDN的例子等，你可以谷歌自己。一般情况下，发电机允许您设置链条，只有在请求时才会生成/返回下一个项目。迭代生成器迭代发生器的生成器可以“懒惰”地产生你需要的结果。 – deceze

探头是一种可能的方式避免迭代算法内的中间结果。为了了解他们更好，你必须认识到，这本身传感器是毫无意义：

// 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]

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

没有中间表示
纯粹的功能和简洁的解决方案
通用性（与任何聚合/采集工作，而不仅仅是阵列）
非凡代码的可重用性（减速机/变压器是它们通常的特征的常见功能）

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

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

来源

2016-02-19 13:33:19 rand

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

回答

相关问题