lib.sortOn: init

A more efficient sort in some cases, and often convenient.

This exposes `lib.lists.sortOn` immediately on `lib`, because it is
a sibling of `sort`, which is already present there.
Omitting it would lead to more confusion, and worse outcomes.
There's no confusion about the types `sort` or `sortOn` operate on.

Haskell agrees about the type for `sortOn`, and it is in its `base`.

1 files changed, 22 insertions, 0 deletions

diff --git a/lib/tests/misc.nix b/lib/tests/misc.nix
index 9f1fee2ba2341..608af656d02c0 100644
--- a/lib/tests/misc.nix
+++ b/lib/tests/misc.nix
@@ -650,6 +650,28 @@ runTests {
     expected = [2 30 40 42];
   };
 
+  testSortOn = {
+    expr = sortOn stringLength [ "aa" "b" "cccc" ];
+    expected = [ "b" "aa" "cccc" ];
+  };
+
+  testSortOnEmpty = {
+    expr = sortOn (throw "nope") [ ];
+    expected = [ ];
+  };
+
+  testSortOnIncomparable = {
+    expr =
+      map
+        (x: x.f x.ok)
+        (sortOn (x: x.ok) [
+          { ok = 1; f = x: x; }
+          { ok = 3; f = x: x + 3; }
+          { ok = 2; f = x: x; }
+        ]);
+    expected = [ 1 2 6 ];
+  };
+
   testReplicate = {
     expr = replicate 3 "a";
     expected = ["a" "a" "a"];