dfinity / motoko-base

The Motoko base library
Apache License 2.0
483 stars 99 forks source link

sequence-like collections should have a `group` operation that lumps together equal subsequences #601

Open ggreif opened 11 months ago

ggreif commented 11 months ago

Like Haskell's group.

Her is one implementation for arrays, that I came up with:

type Comp = { #less; #equal; #greater };
func group<A>(arr : [A], ca : (A, A) -> Comp) : [[A]] =
      switch (arr.size()) {
        case 0 [];
        case 1 [arr];
        case _ {
          let (outer, inner) = (Buffer.Buffer<[A]> 10, Buffer.Buffer<A> 5);
          let iter = arr.vals();
          let ?front = iter.next() else panic "BAD!";
          inner.add front;
          var cur = front;
          for (e in iter) {
            if (ca(cur, e) == #equal)
              inner.add e
            else {
              outer.add(inner.toArray());
              inner.clear();
              inner.add e;
              cur := e
            }
          };
          outer.add(inner.toArray());
          outer.toArray()
        }
    };

It should be easy to do the same for List.

This is also tracked as https://dfinity.atlassian.net/browse/LANG-331.