Repository: sanctuary-js/sanctuary (js)

Issue:
Add S.sort and S.sortBy
Add Sanctuary version of [R.sort](http://ramdajs.com/0.23.0/docs/#sort) and [R.sortBy](http://ramdajs.com/0.23.0/docs/#sort).

Pull request description:
array: add S.sort and S.sortBy
Closes #353

This takes the `sortBy` implementation from <https://github.com/sanctuary-js/sanctuary/pull/365#issuecomment-298272599>, applies @safareli's improvements from <https://github.com/sanctuary-js/sanctuary/pull/365#issuecomment-300780512>, and further improves the algorithm by using binary search.

`sort` is trivially derived via `sortBy(I)`.


Patch:
diff --git a/bower.json b/bower.json
index e23447a..b52e81c 100644
--- a/bower.json
+++ b/bower.json
@@ -22,7 +22,7 @@
     "types"
   ],
   "dependencies": {
-    "sanctuary-def": "0.11.0",
+    "sanctuary-def": "0.11.1",
     "sanctuary-type-classes": "5.2.0",
     "sanctuary-type-identifiers": "2.0.1"
   },
diff --git a/index.js b/index.js
index a1c1f8a..acb78c3 100644
--- a/index.js
+++ b/index.js
@@ -3606,6 +3606,94 @@
       [$.Function([a, a, $.Boolean]), $.Array(a), $.Array($.Array(a))],
       groupBy_);
 
+  //# sort :: (Ord a, Applicative m, Foldable m, Monoid (m a)) => m a -> m a
+  //.
+  //. Performs a [stable sort][] of the elements of the given structure, using
+  //. [`Z.lte`][] for comparisons.
+  //.
+  //. Properties:
+  //.
+  //.   - `S.sort(S.sort(m)) = S.sort(m)` (idempotence)
+  //.
+  //. See also [`sortBy`](#sortBy).
+  //.
+  //. ```javascript
+  //. > S.sort(['foo', 'bar', 'baz'])
+  //. ['bar', 'baz', 'foo']
+  //.
+  //. > S.sort([S.Left(4), S.Right(3), S.Left(2), S.Right(1)])
+  //. [Left(2), Left(4), Right(1), Right(3)]
+  //. ```
+  function sort(m) {
+    return sortBy(I, m);
+  }
+  S.sort =
+  def('sort',
+      {a: [Z.Ord], m: [Z.Applicative, Z.Foldable, Z.Monoid]},
+      [m(a), m(a)],
+      sort);
+
+  //# sortBy :: (Ord b, Applicative m, Foldable m, Monoid (m a)) => (a -> b) -> m a -> m a
+  //.
+  //. Performs a [stable sort][] of the elements of the given structure, using
+  //. [`Z.lte`][] to compare the values produced by applying the given function
+  //. to each element of the structure.
+  //.
+  //. Properties:
+  //.
+  //.   - `S.sortBy(f, S.sortBy(f, m)) = S.sortBy(f, m)` (idempotence)
+  //.
+  //. See also [`sort`](#sort).
+  //.
+  //. ```javascript
+  //. > S.sortBy(S.prop('rank'), [
+  //. .   {rank: 7, suit: 'spades'},
+  //. .   {rank: 5, suit: 'hearts'},
+  //. .   {rank: 2, suit: 'hearts'},
+  //. .   {rank: 5, suit: 'spades'},
+  //. . ])
+  //. [ {rank: 2, suit: 'hearts'},
+  //. . {rank: 5, suit: 'hearts'},
+  //. . {rank: 5, suit: 'spades'},
+  //. . {rank: 7, suit: 'spades'} ]
+  //.
+  //. > S.sortBy(S.prop('suit'), [
+  //. .   {rank: 7, suit: 'spades'},
+  //. .   {rank: 5, suit: 'hearts'},
+  //. .   {rank: 2, suit: 'hearts'},
+  //. .   {rank: 5, suit: 'spades'},
+  //. . ])
+  //. [ {rank: 5, suit: 'hearts'},
+  //. . {rank: 2, suit: 'hearts'},
+  //. . {rank: 7, suit: 'spades'},
+  //. . {rank: 5, suit: 'spades'} ]
+  //. ```
+  function sortBy(f, m) {
+    var rs = Z.reduce(function(xs, x) {
+      var fx = f(x);
+      var lower = 0;
+      var upper = xs.length;
+      while (lower < upper) {
+        var idx = Math.floor((lower + upper) / 2);
+        if (Z.lte(xs[idx].fx, fx)) lower = idx + 1; else upper = idx;
+      }
+      xs.splice(lower, 0, {x: x, fx: fx});
+      return xs;
+    }, [], m);
+
+    var M = m.constructor;
+    var result = Z.empty(M);
+    for (var idx = 0; idx < rs.length; idx += 1) {
+      result = Z.concat(result, Z.of(M, rs[idx].x));
+    }
+    return result;
+  }
+  S.sortBy =
+  def('sortBy',
+      {b: [Z.Ord], m: [Z.Applicative, Z.Foldable, Z.Monoid]},
+      [Fn(a, b), m(a), m(a)],
+      sortBy);
+
   //. ### Object
 
   //# prop :: Accessible a => String -> a -> b
@@ -4501,6 +4589,7 @@
 //. [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
+//. [stable sort]:      https://en.wikipedia.org/wiki/Sorting_algorithm#Stability
 //. [thrush]:           https://github.com/raganwald-deprecated/homoiconic/blob/master/2008-10-30/thrush.markdown
 //. [type identifier]:  v:sanctuary-js/sanctuary-type-identifiers
 //.
diff --git a/package.json b/package.json
index 7574535..dc7782c 100644
--- a/package.json
+++ b/package.json
@@ -11,7 +11,7 @@
     "test": "make lint test"
   },
   "dependencies": {
-    "sanctuary-def": "0.11.0",
+    "sanctuary-def": "0.11.1",
     "sanctuary-type-classes": "5.2.0",
     "sanctuary-type-identifiers": "2.0.1"
   },


Test patch:
diff --git a/test/sort.js b/test/sort.js
new file mode 100644
index 0000000..4d78853
--- /dev/null
+++ b/test/sort.js
@@ -0,0 +1,21 @@
+'use strict';
+
+var S = require('..');
+
+var eq = require('./internal/eq');
+
+
+test('sort', function() {
+
+  eq(typeof S.sort, 'function');
+  eq(S.sort.length, 1);
+  eq(S.sort.toString(), 'sort :: (Ord a, Applicative m, Foldable m, Monoid m) => m a -> m a');
+
+  eq(S.sort([]), []);
+  eq(S.sort(['foo', 'bar', 'baz']), ['bar', 'baz', 'foo']);
+  eq(S.sort([S.Left(4), S.Right(3), S.Left(2), S.Right(1)]), [S.Left(2), S.Left(4), S.Right(1), S.Right(3)]);
+
+  eq(S.sort(S.range(0, 100)), S.range(0, 100));
+  eq(S.sort(S.reverse(S.range(0, 100))), S.range(0, 100));
+
+});
diff --git a/test/sortBy.js b/test/sortBy.js
new file mode 100644
index 0000000..f635871
--- /dev/null
+++ b/test/sortBy.js
@@ -0,0 +1,29 @@
+'use strict';
+
+var S = require('..');
+
+var eq = require('./internal/eq');
+
+
+test('sortBy', function() {
+
+  eq(typeof S.sortBy, 'function');
+  eq(S.sortBy.length, 2);
+  eq(S.sortBy.toString(), 'sortBy :: (Ord b, Applicative m, Foldable m, Monoid m) => (a -> b) -> m a -> m a');
+
+  eq(S.sortBy(S.I, []), []);
+  eq(S.sortBy(S.I, ['five']), ['five']);
+  eq(S.sortBy(S.I, ['five', 'six']), ['five', 'six']);
+  eq(S.sortBy(S.I, ['five', 'six', 'seven']), ['five', 'seven', 'six']);
+  eq(S.sortBy(S.prop('length'), ['five', 'six', 'seven']), ['six', 'five', 'seven']);
+
+  var _7s = {rank: 7, suit: 's'};
+  var _5h = {rank: 5, suit: 'h'};
+  var _2h = {rank: 2, suit: 'h'};
+  var _5s = {rank: 5, suit: 's'};
+  eq(S.sortBy(S.prop('rank'), [_7s, _5h, _2h, _5s]), [_2h, _5h, _5s, _7s]);
+  eq(S.sortBy(S.prop('rank'), [_7s, _5s, _2h, _5h]), [_2h, _5s, _5h, _7s]);
+  eq(S.sortBy(S.prop('suit'), [_7s, _5h, _2h, _5s]), [_5h, _2h, _7s, _5s]);
+  eq(S.sortBy(S.prop('suit'), [_5s, _2h, _5h, _7s]), [_2h, _5h, _5s, _7s]);
+
+});