Repository: sanctuary-js/sanctuary
Pull request #371 (2017-04-03 12:56:26)

groupBy as in Haskell
Should work as in Haskell!

Some notes:

- This can be do in many different ways! Please give feedback
  so it can be improved \o/

Please review 🙏🙇

Closes: #351

sadasant: Tests failed because of Karma, the browsers couldn't start apparently.
sadasant: @davidchambers thank for the reviews!!!
davidchambers: Let's also define `groupBy_` with the following type:

```haskell
groupBy_ :: ((a, a) -> Boolean) -> Array a -> Array (Array a)
```

I suggest using the same approach we used for `encase2` and `encase2_`:

1.  Change the name of the implementation function from `groupBy` to `groupBy_`, and update it to take an uncurried binary function.

2.  Define `S.groupBy_` with `groupBy_` as its implementation function.

3.  Add a new `groupBy` implementation function:

    ```javascript
    function groupBy(f, xs) {
      return groupBy_(uncurry2(f), xs);
    }
    ```

davidchambers: > groupBy for [[]] returns [[[]]], but in haskell it causes an error.

It doesn't for me:

```haskell
> groupBy (==) [[]]
[[[]]]
```

sadasant: @davidchambers nice! I was trying with > or <, so perhaps it was that? thanks!
sadasant: (Exactly `+100 −0`! r/oddlysatisfying)
davidchambers: I'm sorry for letting this pull request languish, @sadasant! Please fix the typo I just spotted, squash your commits, `git rebase master`, update this pull request, and leave a comment to let me know that you've done so. I'll then merge these additions. :)

sadasant: Thanks! I will let you know when it's done ✌

Patch:
diff --git a/index.js b/index.js
index adebd8d..b2b3537 100644
--- a/index.js
+++ b/index.js
@@ -3282,6 +3282,57 @@
   S.range =
   def('range', {}, [$.Integer, $.Integer, $.Array($.Integer)], range);
 
+  //# groupBy :: (a -> a -> Boolean) -> Array a -> Array (Array a)
+  //.
+  //. Splits its array argument into an array of arrays of equal,
+  //. adjacent elements. Equality is determined by the function
+  //. provided as the first argument. Its behaviour can be surprising
+  //. for functions that aren't reflexive, transitive, and symmetric
+  //. (see [equivalence][] relation).
+  //.
+  //. See also [`groupBy_`](#groupBy_).
+  //.
+  //. Properties:
+  //.
+  //.   - `forall f :: a -> a -> Boolean, xs :: Array a.
+  //.      S.join(S.groupBy(f, xs)) = xs`
+  //.
+  //. ```javascript
+  //. > S.groupBy(S.equals, [1, 1, 2, 1, 1])
+  //. [[1, 1], [2], [1, 1]]
+  //.
+  //. > S.groupBy(x => y => x + y === 0, [2, -3, 3, 3, 3, 4, -4, 4])
+  //. [[2], [-3, 3, 3, 3], [4, -4], [4]]
+  //. ```
+  function groupBy(f, xs) {
+    return groupBy_(uncurry2(f), xs);
+  }
+  S.groupBy =
+  def('groupBy',
+      {},
+      [Fn(a, Fn(a, $.Boolean)), $.Array(a), $.Array($.Array(a))],
+      groupBy);
+
+  //# groupBy_ :: ((a, a) -> Boolean) -> Array a -> Array (Array a)
+  //.
+  //. Variant of [`groupBy`](#groupBy) which takes an uncurried function.
+  function groupBy_(f, xs) {
+    if (xs.length === 0) return [];
+    var x0 = xs[0];         // :: a
+    var active = [x0];      // :: Array a
+    var result = [active];  // :: Array (Array a)
+    for (var idx = 1; idx < xs.length; idx += 1) {
+      var x = xs[idx];
+      if (f(x0, x)) active.push(x); else result.push(active = [x0 = x]);
+    }
+    return result;
+  }
+  S.groupBy_ =
+  def('groupBy_',
+      {},
+      [$.Function([a, a, $.Boolean]), $.Array(a), $.Array($.Array(a))],
+      groupBy_);
+
   //. ### Object
 
   //# prop :: Accessible a => String -> a -> b
@@ -4180,6 +4231,7 @@
 //. [`Z.traverse`]:     v:sanctuary-js/sanctuary-type-classes#traverse
 //. [`Z.zero`]:         v:sanctuary-js/sanctuary-type-classes#zero
 //. [`of`]:             v:fantasyland/fantasy-land#of-method
+//. [equivalence]:      https://en.wikipedia.org/wiki/Equivalence_relation
 //. [parseInt]:         https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/parseInt
 //. [sanctuary-def]:    v:sanctuary-js/sanctuary-def
 //. [thrush]:           https://github.com/raganwald-deprecated/homoiconic/blob/master/2008-10-30/thrush.markdown


Test patch:
diff --git a/test/groupBy.js b/test/groupBy.js
new file mode 100644
index 0000000..0633081
--- /dev/null
+++ b/test/groupBy.js
@@ -0,0 +1,37 @@
+'use strict';
+
+var jsc = require('jsverify');
+
+var S = require('..');
+
+var eq = require('./internal/eq');
+
+
+test('groupBy', function() {
+
+  eq(typeof S.groupBy, 'function');
+  eq(S.groupBy.length, 2);
+  eq(S.groupBy.toString(), 'groupBy :: (a -> a -> Boolean) -> Array a -> Array (Array a)');
+
+  function productsOf3(x) {
+    return function(y) {
+      return x * y % 3 === 0;
+    };
+  }
+
+  function zeroSum(x) {
+    return function(y) {
+      return x + y === 0;
+    };
+  }
+
+  eq(S.groupBy(productsOf3, []), []);
+  eq(S.groupBy(productsOf3, [1, 2, 3, 4, 5, 6, 7, 8, 9]), [[1], [2, 3], [4], [5, 6], [7], [8, 9]]);
+  eq(S.groupBy(S.equals, [1, 1, 2, 1, 1]), [[1, 1], [2], [1, 1]]);
+  eq(S.groupBy(zeroSum, [2, -3, 3, 3, 3, 4, -4, 4]), [[2], [-3, 3, 3, 3], [4, -4], [4]]);
+
+  jsc.assert(jsc.forall('nat -> nat -> bool', 'array nat', function(f, xs) {
+    return S.equals(S.join(S.groupBy(f, xs)), xs);
+  }), {tests: 100});
+
+});
diff --git a/test/groupBy_.js b/test/groupBy_.js
new file mode 100644
index 0000000..a886c2a
--- /dev/null
+++ b/test/groupBy_.js
@@ -0,0 +1,35 @@
+'use strict';
+
+var jsc = require('jsverify');
+
+var S = require('..');
+
+var eq = require('./internal/eq');
+
+
+test('groupBy_', function() {
+
+  eq(typeof S.groupBy_, 'function');
+  eq(S.groupBy_.length, 2);
+  eq(S.groupBy_.toString(), 'groupBy_ :: ((a, a) -> Boolean) -> Array a -> Array (Array a)');
+
+  function productsOf3(a, b) {
+    return a * b % 3 === 0;
+  }
+
+  function zeroSum(x, y) {
+    return x + y === 0;
+  }
+
+  eq(S.groupBy_(productsOf3)([]), []);
+  eq(S.groupBy_(productsOf3)([1, 2, 3, 4, 5, 6, 7, 8, 9]), [[1], [2, 3], [4], [5, 6], [7], [8, 9]]);
+  eq(S.groupBy_(S.equals, [1, 1, 2, 1, 1]), [[1, 1], [2], [1, 1]]);
+  eq(S.groupBy_(zeroSum)([2, -3, 3, 3, 3, 4, -4, 4]), [[2], [-3, 3, 3, 3], [4, -4], [4]]);
+
+  jsc.assert(jsc.forall('nat -> nat -> bool', 'array nat', function(f, xs) {
+    return S.equals(S.join(S.groupBy_(function(x, y) {
+      return f(x)(y);
+    }, xs)), xs);
+  }), {tests: 100});
+
+});