Feature request: Lazy.partition()

[dead-claudia]

This operation is fundamentally equivalent to [filter, reject], but can be done in one pass. The native JavaScript implementation would be this:

function partition(array, fn) {
  var good = [];
  var bad = [];
  for (var i = 0, len = array.length; i < len; i++) {
    var entry = array[i];
    (fn(entry, i, array) ? good : bad).push(entry);
  }
}

It would be really useful, and is relatively common in functional programming. It isn't in Lodash/Underscore, but in more pure functional programming circles, it's hard not to find them.

[hazeledmands]

I've wanted this for a while. Perhaps I'll write a pull request, this shouldn't be too hard to implement...

[dtao]

Dumb question: what does this function return? (I can't tell from your example.)

If it's something like good.concat(bad) then you could achieve the same thing with sortBy. If it's something like {good: good, bad: bad} then you could do it with groupBy:

function partition(array, fn) {
  var groups = Lazy(array).groupBy(fn).toObject();
  return {
    good: groups[true],
    bad: groups[false]
  };
}

In the latter case, I'm not saying partition wouldn't still be a useful further abstraction and a method worth adding. I'm just trying to understand exactly what you're asking for.

[dead-claudia]

@dtao It returns something like this:

partition([1, 2, 3, 4, 5], isEven); //=> [[2, 4], [1, 3, 5]]
partition([1, 3, 5, 2, 6], a => a > 3); //=> [[5, 6], [1, 3, 5]]
partition([0, 3, -2, 0, -6], a => a === 0) //=> [[0, 0], [3, -2, -6]]

The order of the elements in each return array pair is usually the same order as they were relative to the original array. Technically, it's equivalent to (xs, cmp) => [filter(xs, cmp), reject(xs, cmp)], but can be done in a single loop, making it literally twice as fast as the equivalent.

A way to implement it lazily with ES6 generators would be this (I will admit it is a little clunky):

var def = new (function() {});

function* makeLazy(list, len) {
  for (var i = 0; i < len; i++)
    yield list[i];
}

function* makeList() {
  var list = [];
  var len = 0;
  var value;
  while ((value = yield) !== def) {
    list.push(value);
    len++;
  }
  yield* makeLazy(list);
}

function* partition(xs, cmp) {
  var good = makeList();
  var bad = makeList();
  var entry;

  // fill generators
  while (!(entry = xs.next()).done) {
    (cmp(x) ? good : bad).next(entry);
  }

  // end loading
  good.next(def);
  bad.next(def);

  // return generator pair
  return [good, bad];
}

Does this explain it better?

[dtao]

@impinball Thanks, yeah that does explain it better. So the return value is [good, bad].

I will point out that this is indeed trivial to implement with groupBy, in almost the way I described in my previous comment:

function partition(array, fn) {
  var groups = Lazy(array).groupBy(fn).toObject();
  return [groups[true], groups[false]];
}

That said, I'm not opposed to adding it to Lazy. It's a trivial implementation of a special case; but if it's a useful and common abstraction then I think it's justified, in the same way compact is justified even though it's just a trivially-implemented special case of filter.

[dead-claudia]

Here's an example of where this could be useful (especially in ES6):

// Lazy.js with .partition()
let [lows, highs] = Lazy.generate(Math.random, 100).partition(x => x < 0.5);
console.log('Math.random 100x:');
console.log('  <  0.5: ' + low.size());
console.log('  >= 0.5: ' + high.size());

// In plain ES6
let lows = [];
let highs = [];
for (var i = 0; i < 100; i++) {
  let num = Math.random();
  (num < 0.5 ? low : high).push(num);
}
console.log('Math.random 100x:');
console.log('  <  0.5: ' + low);
console.log('  >= 0.5: ' + high);

[ShawnTalbert]

Coming from Scala I do miss partition()