What is the best way to implement a partition function for iterables?

Question

I am very fond of working on dart lists. Nevertheless, I often find myself in a situation where a “section” function is needed, where the list is divided into two parts in accordance with logical criteria. The value is the same as .where, but does not reject, false.

Obvious implementation:

Iterable partition(Iterable list, filter) {
  var matches    = [];
  var nonMatches = [];
  list.forEach((e) {
    if (filter(e)) {
      matches.add(e);
    } else {
      nonMatches.add(e);
    }
  });
  return [matches, nonMatches];
}

However, I also loved the lazy iterations returned where.

Another implementation is using sets:

Iterable partition(Iterable list, filter) {
  var matches    = list.where(filter);
  var nonMatches = list.toSet().difference(matches.toSet()).toList();
  return [matches, nonMatches];
}

I would be happy to see how an elegant lazy implementation can be accomplished (if it's easy). I believe that building a collection from a list is an operation O(n), so the two implementations should not be too different in efficiency. Comments required for this.

. , , nonMatches , matches.

Answer 1

:

Iterable partition(Iterable list, filter) {
  return [list.where((e) => filter(e)), list.where((e) => !filter(e))];
}

Answer 2

, UnmodifiableListView:

import "package:unittest/unittest.dart";
import "dart:collection";

class Tuple<A,B> {
  final A a;
  final B b;
  const Tuple(this.a, this.b);
  String toString() {
    return "(a: $a, b : $b)";
  }
}

abstract class  partitionMixin<RES, E>{
  Iterable<E> where(bool test(E element));
  Map<E, bool> _filterCache = new Map();
  Tuple<RES,RES> partition(bool filter(E e)) {
    bool cachedFilter(E e) {
      if (_filterCache.containsKey(e)) return _filterCache[e];
      else {
        bool filterRes = filter(e);
        _filterCache[e] = filterRes;
        return filterRes;
      }
    }
    return new Tuple(this.where(cachedFilter),
        this.where((E e) => !cachedFilter(e)));
  }
}


 class  ExtULV<E> = UnmodifiableListView<E> with
                              partitionMixin<ExtULV<E>,E>;

void main() {

  test('Split one iterable in two"', () {

    var foo = (e) => (e % 2) == 0;
    var fooA =  [2,4,6,8, 10, 12, 14];
    var fooB =  [1,3,5,7,9,11,13];
    var fooRes = new Tuple(fooA, fooB);

    var tested = new ExtULV([1,2,3,4,5,6,7,8,9,10,11,12,13,14]);
    var testRes = tested.partition(foo);
    print("fooRes : $fooRes\ntestRes: $testRes");
    expect(testRes.a.toList().toString() == fooRes.a.toString(), true);
    expect(testRes.b.toList().toString() == fooRes.b.toString(), true);

  });
}

Answer 3

If you generalize it, it will become easier

  Map groupedBy(f, list) {
    var grouped = {};
    for (var thing in list) {
      grouped.putIfAbsent(f(thing), () => []).add(thing);  
    }
   return grouped;
  }

although it’s not so easy to make lazy.