logo标签列表

如何在链接map reduce filter时减少迭代次数？

javascriptfunctional-programmingmonads
3

因为在React和FP中使用频繁，我已经阅读了很多关于 map, reduce 和 filter 的内容。如果我们像下面这样写：

let myArr = [1,2,3,4,5,6,7,8,9]
let sumOfDoubleOfOddNumbers = myArr.filter(num => num % 2)
                                   .map(num => num * 2)
                                   .reduce((acc, currVal) => acc + currVal, 0);

运行了三个不同的循环。

我也阅读过Java 8流的相关内容，知道它们使用所谓的单子（monad），即首先存储计算结果。它们仅在一次迭代中执行一次。例如，

Stream.of("d2", "a2", "b1", "b3", "c")
    .map(s -> {
        System.out.println("map: " + s);
        return s.toUpperCase();
    })
    .filter(s -> {
        System.out.println("filter: " + s);
        return s.startsWith("A");
    })
    .forEach(s -> System.out.println("forEach: " + s));

// map:     d2
// filter:  D2
// map:     a2
// filter:  A2
// forEach: A2
// map:     b1
// filter:  B1
// map:     b3
// filter:  B3
// map:     c
// filter:  C

PS：Java代码来自：http://winterbe.com/posts/2014/07/31/java8-stream-tutorial-examples/

许多其他语言也使用这种方法，那么在JS中是否有同样的方法呢？

Java中的流确实形成了一个单子，但这并不是它们只执行一次迭代的原因。只执行一次迭代是来自于一种叫做惰性求值的特性。 - 4castle
有没有办法将这种惰性求值行为应用到这些JS函数中？ - ayushgp
Lodash库目前在使用_.chain时采用惰性求值。 - 4castle
只是一点小建议：你可以把它缩短为 myArr.reduce((acc, num) => num % 2 ? acc += num * 2 : acc, 0);。 - guijob
4
了解一下变压器。当然，你也可以始终采用直接递归的方式。 - user6445533
@guijob 这将违背可读性的目的。我猜这些函数首先是用来使代码更易读的。 - ayushgp
4个回答
5
这是您Java代码的精确克隆。与Bergi的解决方案不同，无需修改全局原型。 

class Stream {
    constructor(iter) {
        this.iter = iter;
    }

    * [Symbol.iterator]() {
        yield* this.iter;
    }

    static of(...args) {
        return new this(function* () {
            yield* args
        }());
    }

    _chain(next) {
        return new this.constructor(next.call(this));
    }

    map(fn) {
        return this._chain(function* () {
            for (let a of this)
                yield fn(a);
        });
    }

    filter(fn) {
        return this._chain(function* () {
            for (let a of this)
                if (fn(a))
                    yield (a);
        });
    }

    forEach(fn) {
        for (let a of this)
            fn(a)
    }
}


Stream.of("d2", "a2", "b1", "b3", "c")
    .map(s => {
        console.log("map: " + s);
        return s.toUpperCase();
    })
    .filter(s => {
        console.log("filter: " + s);
        return s.startsWith("A");
    })
    .forEach(s => console.log('forEach', s));

实际上，链接功能可以从特定的迭代器中解耦出来，以提供一个通用的框架：
// polyfill, remove me later on
Array.prototype.values = Array.prototype.values || function* () { yield* this };

class Iter {
    constructor(iter)     { this.iter = iter }
    * [Symbol.iterator]() { yield* this.iter }
    static of(...args)    { return this.from(args) }
    static from(args)     { return new this(args.values()) }
    _(gen)                { return new this.constructor(gen.call(this)) }
}

现在，您可以将任意生成器放入其中，包括预定义的和即席创建的生成器，例如：
let map = fn => function* () {
    for (let a of this)
        yield fn(a);
};

let filter = fn => function* () {
    for (let a of this)
        if (fn(a))
            yield (a);
};

it = Iter.of("d2", "a2", "b1", "b3", "c", "a000")
    ._(map(s => s.toUpperCase()))
    ._(filter(s => s.startsWith("A")))
    ._(function*() {
        for (let x of [...this].sort())
            yield x;
    });

console.log([...it])
你可能想要将 next.bind(this.iter)() 简化为 next.call(this.iter)。或者，考虑到你的 Stream 是可迭代的，甚至可以简化为 next.call(this) :-) 另外，static of(...args) { return new this(args[Symbol.iterator]()); } - Bergi
@Bergi：是的，谢谢！一旦每个人都实现它，of 应该变成 args.values。 - georg
你也可以这样写：*_map(fn) { for (const x of this) yield fn(x); } map(fn) { return new this.constructor(this._map(fn)); }。不确定它是否更简单，但应该比创建所有这些生成器函数表达式更有效，这些表达式很容易共享。 - Bergi
1
您可以使用管道实现此操作，我不知道这是否会使它过于复杂，但是通过使用管道，您可以在管道上调用Array.reduce，并且它会在每次迭代中执行相同的行为。
const stream = ["d2", "a2", "b1", "b3", "c"];

const _pipe = (a, b) => (arg) => b(a(arg));
const pipe = (...ops) => ops.reduce(_pipe);

const _map = (value) => (console.log(`map: ${value}`), value.toUpperCase());
const _filter = (value) => (console.log(`filter: ${value}`), 
value.startsWith("A") ? value : undefined);
const _forEach = (value) => value ? (console.log(`forEach: ${value}`), value) : undefined;

const mapFilterEach = pipe(_map,_filter,_forEach);

const result = stream.reduce((sum, element) => {
    const value = mapFilterEach(element);
    if(value) sum.push(value);
    return sum;
}, []);

我从这里获取了pipe函数

这是一个管道 reduce 的 polyfill，如果您想将其用于更动态的目的，以下是一个示例。
Array.prototype.pipeReduce = function(...pipes){
    const _pipe = (a, b) => (arg) => b(a(arg));
    const pipe = (...ops) => ops.reduce(_pipe);
    const reducePipes = pipe(...pipes);
    return this.reduce((sum, element) => {
        const value = reducePipes(element);
        if(value) sum.push(value);
        return sum;
    }, []);
};

const stream = ["d2", "a2", "b1", "b3", "c"];

const reduced = stream.pipeReduce((mapValue) => {
    console.log(`map: ${mapValue}`);
    return mapValue.toUpperCase();
}, (filterValue) => {
    console.log(`filter: ${filterValue}`);
    return filterValue.startsWith("A") ? filterValue : undefined;
}, (forEachValue) => {
    if(forEachValue){
        console.log(`forEach: ${forEachValue}`);
        return forEachValue;
    }
    return undefined;
});

console.log(reduced); //["A2"]
你不能像那样使用 filter 函数，进一步传递的函数需要处理 undefined 值（它本身只是一个避免使用正确的 Option 数据类型的 hack） 。 - Bergi
1

所谓的单子，即将计算结果先存储起来

嗯，不是这个意思。单子的含义不同。

在JS中有没有相同的方法？

是的，你可以使用迭代器。查看这个实现或那个（关于单子方法，在这里）。

const myArr = [1,2,3,4,5,6,7,8,9];
const sumOfDoubleOfOddNumbers = myArr.values() // get iterator
                                .filter(num => num % 2)
                                .map(num => num * 2)
                                .reduce((acc, currVal) => acc + currVal, 0);
console.log(sumOfDoubleOfOddNumbers);

["d2", "a2", "b1", "b3", "c"].values()
.map(s => {
    console.log("map: " + s);
    return s.toUpperCase();
})
.filter(s => {
    console.log("filter: " + s);
    return s.startsWith("A");
})
.forEach(s => console.log("forEach: " + s));


var IteratorPrototype = Object.getPrototypeOf(Object.getPrototypeOf([][Symbol.iterator]()));
IteratorPrototype.map = function*(f) {
    for (var x of this)
        yield f(x);
};
IteratorPrototype.filter = function*(p) {
    for (var x of this)
        if (p(x))
            yield x;
};
IteratorPrototype.reduce = function(f, acc) {
    for (var x of this)
        acc = f(acc, x);
    return acc;
};
IteratorPrototype.forEach = function(f) {
    for (var x of this)
        f(x);
};
Array.prototype.values = Array.prototype[Symbol.iterator];

const myArr = [1,2,3,4,5,6,7,8,9];
const sumOfDoubleOfOddNumbers = myArr.values() // get iterator
                                .filter(num => num % 2)
                                .map(num => num * 2)
                                .reduce((acc, currVal) => acc + currVal, 0);
console.log({sumOfDoubleOfOddNumbers});

["d2", "a2", "b1", "b3", "c"].values()
.map(s => {
    console.log("map: " + s);
    return s.toUpperCase();
})
.filter(s => {
    console.log("filter: " + s);
    return s.startsWith("A");
})
.forEach(s => console.log("forEach: " + s));

在生产代码中，您应该使用静态函数而不是将自定义方法放在内置迭代器原型上。
你需要一个全新的基础设施来实现迭代协议，只为了获得惰性属性，而这种属性本来就存在于函数组合中。我认为这不值得。此外，在生成器函数的作用域中无法使用高阶函数，因为您无法在它们的回调内部使用yield。这不再感觉像函数式编程。 - user6445533
@ftor 抱歉，我不明白。你所说的“全新基础架构”是什么意思？我们总是需要一种新的基础架构来替换数组作为数据结构。无论是 Georg 的自定义 Stream 类，还是像我示例中的本地 Iterator 接口，或者使用自己的迭代协议的更复杂的东西（转换器...）。另外，HOF 和生成器函数有什么问题吗？我只是将 Array 单子换成了 Iterator 单子 - 其他什么都没有改变。 - Bergi
从FP的角度来看，JS已经有了实现惰性迭代的手段，不需要迭代器/可迭代对象，至少对于惰性而言是这样。transducers的“迭代协议”完全基于一级/HO函数，特别是普通函数组合。没有新的语言结构，没有状态，也没有隐式变异。至于function* HOF问题：我指的是一般情况 - 与您提供的特定示例无关。 - user6445533
1

Array.prototype.map和Array.prototype.filter可以从之前的数组创建新的数组。 Array.prototype.reduce将函数应用于累加器和数组中的每个元素（从左到右），以将其减少为单个值。

因此，它们都不允许惰性评估。

您可以通过将多个循环减少为一个来实现惰性：

const array = [1, 2, 3, 4, 5, 6, 7, 8, 9]
const result = array.reduce((acc, x) => x % 2 ? acc += x * 2 : acc, 0);
console.log(result);

另一种方法是通过在自定义对象中手动处理延迟计算。下面的代码片段是重新定义 filter 和 map 的示例：

const array = [1, 2, 3, 4, 5, 6, 7, 8, 9];
// convert to a lazy structure...
const results = toLazy(array)
  .filter(x => {
    console.log('filter', x);
    return x % 2 !== 0;
  })
  .map(x => {
    console.log('map', x);
    return x * 2;
  });

// check logs for `filter` and `map` callbacks
console.log(results.run()); // -> [2, 6, 10, 14, 18]

function toLazy(array) {
  const lazy = {};
  let callbacks = [];

  function addCallback(type, callback) {
    callbacks.push({ type, callback });
    return lazy;
  }

  lazy.filter = addCallback.bind(null, 'filter');
  lazy.map = addCallback.bind(null, 'map');

  lazy.run = function () {
    const results = [];

    for (var i = 0; i < array.length; i += 1) {
      const item = array[i];
      for (var { callback, type } of callbacks) {
        if (type === 'filter') {
          if (!callback(item, i)) {
            break;
          }
        } else if (type === 'map') {
          results.push(callback(item, i));
        }
      }
    }

    return results;
  };

  return lazy;
}

然而，您可以查看像lazy.js这样的库，它在底层使用迭代器提供了一个惰性引擎。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接