How to reduce iterations when chaining map reduce filter?

Question

I have been reading about map, reduce and filter a lot because of how much they are used in react and FP in general. If we write something like:

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);

3 different loops are run.

I've read about Java 8 streams as well and know that they use what is called a monad, ie, the computations are stored first. They are performed once only in one iteration. For example,

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 code is taken from: http://winterbe.com/posts/2014/07/31/java8-stream-tutorial-examples/

There are many other languages that use this same method. Is there a way to do it the same way in JS as well?

Streams in Java do form a monad, but that's not why they're performed in only one iteration. The one iteration comes from a feature called laziness. — 4castle, Mar 11 '18 at 15:25
Is there a way to get this Lazy Evaluation behaviour to these js functions? — ayushgp, Mar 11 '18 at 15:27
The Lodash library currently uses lazy evaluation if you use `_.chain` — 4castle, Mar 11 '18 at 15:33
just a side note: use could make it shorter `myArr.reduce((acc, num) => num % 2 ? acc += num * 2 : acc, 0);` — guijob, Mar 11 '18 at 15:39
Look into [transducers](https://stackoverflow.com/a/45168026). Alternatively, you can always resort to direct recursion, of course. — , Mar 11 '18 at 15:39
@guijob that defeats the readability purpose. I guess these functions are used in the first place to make the code more readable. — ayushgp, Mar 11 '18 at 15:44

georg · Accepted Answer · 2018-03-11T20:13:57.613

This is an exact clone of your Java code. Unlike Bergi's solution, no need to modify global prototypes.

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));

Actually, the chaining functionality could be decoupled from specific iterators to provide a generic framework:

// 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)) }
}

Now, you can throw arbitrary generators into this, both predefined and ad-hoc ones, for example:

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

You'll want to simplify `next.bind(this.iter)()` to `next.call(this.iter)`. Or even `next.call(this)`, given that your `Stream` is iterable :-) Also, `static of(...args) { return new this(args[Symbol.iterator]()); }` — Bergi, Mar 11 '18 at 18:51
@Bergi: yep, thanks! `of` should become `args.values` once everybody implements it. — georg, Mar 11 '18 at 18:57
You also could write it like `*_map(fn) { for (const x of this) yield fn(x); } map(fn) { return new this.constructor(this._map(fn)); }`. Not sure whether it's much simpler, but it should be more efficient than creating all these generator function expressions that could easily be shared. — Bergi, Mar 11 '18 at 19:45

Pavlo · Answer 2 · 2018-03-11T16:45:58.970

You can achieve this using piping, i dunno if this makes it too complicated, but by using piping you can call Array.reduce on the pipe and it performs the same behaviour on each iteration.

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;
}, []);

I took the pipe function from here

Here is a polyfill of the pipe reduce and an example if you want to use it for more dynamic purposes

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

You cannot do `filter` like that, further piped functions would need to cope with the `undefined` value (which in itself is just a hack to avoid a proper `Option` data type). — Bergi, Mar 11 '18 at 17:01

Bergi · Answer 3 · 2018-03-11T16:58:31.320

what is called a monad, ie, the computations are stored first

Um, no, that's not what Monad means.

Is there a way to do it the same way in JS as well?

Yes, you can use iterators. Check this implementation or that one (and for the monad methods, here).

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));

In production code, you probably should use static functions instead of putting custom methods on the builtin iterator prototype.

You need a whole new infrastructure for the iteration protocols just to gain the lazy property, which is inherent in function composition. I don't think it is worth it. Additionally, you cannot use HOFs in the scope of generator functions, because you cannot yield inside their callbacks. This doesn't feel like FP anymore. — , Mar 11 '18 at 19:26
@ftor Sorry, I don't get it. What do you mean by "whole new infrastructure"? We always need a new infrastructure to replace the arrays as the data structure. Doesn't really matter whether it's Georg's custom `Stream` class, the native `Iterator` interface like in my example, or something more complicated (transducers...) that uses its own iteration protocol. Also, what is that problem with HOFs and generator functions? I've just swapped the `Array` monad out for the `Iterator` monad - nothing else changes. — Bergi, Mar 11 '18 at 19:43
From a FP perspective JS had already the means to realize lazy iteration, no iterators/iterables necessary, at least not for lazyness. The "iteration protocol" of transducers is solely based on first class/HO functions, normal function composition in particular. No new language constructs, no state, no implicit mutations. And as for the function* HOF issue: I meant that in general - not related to the particular example you gave. — , Mar 11 '18 at 20:17

Carloluis · Answer 4 · 2018-03-11T17:01:24.060

Array.prototype.map and Array.prototype.filter creates new arrays from the previous one. Array.prototype.reduce applies a function against an accumulator and each element in the array (from left to right) to reduce it to a single value.

Therefore, neither of them allow lazy evaluation.

You can achieve laziness by reducing your multiples loops into one:

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);

Another way could be handling lazy evaluations by yourself in a custom object as follows. Next snippet is an example redefining filter and 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;
}

However, you can check libraries like lazy.js which provides a lazy engine under the hood using iterators.

How to reduce iterations when chaining map reduce filter?

4 Answers4

Linked