Merge pull request #23929 from Profpatsch/lib-lists-doc

Improve lib/trivial and lib/lists docs

3 files changed, 90 insertions, 19 deletions

diff --git a/lib/lists.nix b/lib/lists.nix
index 5e224921de81..82d5ba0124cb 100644
--- a/lib/lists.nix
+++ b/lib/lists.nix
@@ -16,17 +16,22 @@ rec {
   */
   singleton = x: [x];
 
-  /* "Fold" a binary function `op' between successive elements of
-     `list' with `nul' as the starting value, i.e., `fold op nul [x_1
-     x_2 ... x_n] == op x_1 (op x_2 ... (op x_n nul))'.  (This is
-     Haskell's foldr).
+  /* “right fold” a binary function `op' between successive elements of
+     `list' with `nul' as the starting value, i.e.,
+     `foldr op nul [x_1 x_2 ... x_n] == op x_1 (op x_2 ... (op x_n nul))'.
+     Type:
+       foldr :: (a -> b -> b) -> b -> [a] -> b
 
      Example:
-       concat = fold (a: b: a + b) "z"
+       concat = foldr (a: b: a + b) "z"
        concat [ "a" "b" "c" ]
        => "abcz"
+       # different types
+       strange = foldr (int: str: toString (int + 1) + str) "a"
+       strange [ 1 2 3 4 ]
+       => "2345a"
   */
-  fold = op: nul: list:
+  foldr = op: nul: list:
     let
       len = length list;
       fold' = n:
@@ -35,13 +40,25 @@ rec {
         else op (elemAt list n) (fold' (n + 1));
     in fold' 0;
 
-  /* Left fold: `fold op nul [x_1 x_2 ... x_n] == op (... (op (op nul
-     x_1) x_2) ... x_n)'.
+  /* `fold' is an alias of `foldr' for historic reasons */
+  # FIXME(Profpatsch): deprecate?
+  fold = foldr;
+
+
+  /* “left fold”, like `foldr', but from the left:
+     `foldl op nul [x_1 x_2 ... x_n] == op (... (op (op nul x_1) x_2) ... x_n)`.
+
+     Type:
+       foldl :: (b -> a -> b) -> b -> [a] -> b
 
      Example:
        lconcat = foldl (a: b: a + b) "z"
        lconcat [ "a" "b" "c" ]
        => "zabc"
+       # different types
+       lstrange = foldl (str: int: str + toString (int + 1)) ""
+       strange [ 1 2 3 4 ]
+       => "a2345"
   */
   foldl = op: nul: list:
     let
@@ -52,7 +69,7 @@ rec {
         else op (foldl' (n - 1)) (elemAt list n);
     in foldl' (length list - 1);
 
-  /* Strict version of foldl.
+  /* Strict version of `foldl'.
 
      The difference is that evaluation is forced upon access. Usually used
      with small whole results (in contract with lazily-generated list or large
@@ -140,7 +157,7 @@ rec {
        any isString [ 1 { } ]
        => false
   */
-  any = builtins.any or (pred: fold (x: y: if pred x then true else y) false);
+  any = builtins.any or (pred: foldr (x: y: if pred x then true else y) false);
 
   /* Return true iff function `pred' returns true for all elements of
      `list'.
@@ -151,7 +168,7 @@ rec {
        all (x: x < 3) [ 1 2 3 ]
        => false
   */
-  all = builtins.all or (pred: fold (x: y: if pred x then y else false) true);
+  all = builtins.all or (pred: foldr (x: y: if pred x then y else false) true);
 
   /* Count how many times function `pred' returns true for the elements
      of `list'.
@@ -219,7 +236,7 @@ rec {
        => { right = [ 5 3 4 ]; wrong = [ 1 2 ]; }
   */
   partition = builtins.partition or (pred:
-    fold (h: t:
+    foldr (h: t:
       if pred h
       then { right = [h] ++ t.right; wrong = t.wrong; }
       else { right = t.right; wrong = [h] ++ t.wrong; }
diff --git a/lib/tests.nix b/lib/tests.nix
index bef9cdee696d..1a9a5accd1c0 100644
--- a/lib/tests.nix
+++ b/lib/tests.nix
@@ -1,3 +1,6 @@
+# to run these tests:
+# nix-instantiate --eval --strict nixpkgs/lib/tests.nix
+# if the resulting list is empty, all tests passed
 let inherit (builtins) add; in
 with import ./default.nix;
 
@@ -45,10 +48,34 @@ runTests {
     expected = ["b" "c"];
   };
 
-  testFold = {
-    expr = fold (builtins.add) 0 (range 0 100);
-    expected = 5050;
-  };
+  testFold =
+    let
+      f = op: fold: fold op 0 (range 0 100);
+      # fold with associative operator
+      assoc = f builtins.add;
+      # fold with non-associative operator
+      nonAssoc = f builtins.sub;
+    in {
+      expr = {
+        assocRight = assoc foldr;
+        # right fold with assoc operator is same as left fold
+        assocRightIsLeft = assoc foldr == assoc foldl;
+        nonAssocRight = nonAssoc foldr;
+        nonAssocLeft = nonAssoc foldl;
+        # with non-assoc operator the fold results are not the same
+        nonAssocRightIsNotLeft = nonAssoc foldl != nonAssoc foldr;
+        # fold is an alias for foldr
+        foldIsRight = nonAssoc fold == nonAssoc foldr;
+      };
+      expected = {
+        assocRight = 5050;
+        assocRightIsLeft = true;
+        nonAssocRight = 50;
+        nonAssocLeft = (-5050);
+        nonAssocRightIsNotLeft = true;
+        foldIsRight = true;
+      };
+    };
 
   testTake = testAllTrue [
     ([] == (take 0 [  1 2 3 ]))
diff --git a/lib/trivial.nix b/lib/trivial.nix
index abe5a16c67d6..40499b2b5092 100644
--- a/lib/trivial.nix
+++ b/lib/trivial.nix
@@ -1,17 +1,44 @@
 rec {
 
-  # Identity function.
+  /* The identity function
+     For when you need a function that does “nothing”.
+
+     Type: id :: a -> a
+  */
   id = x: x;
 
-  # Constant function.
+  /* The constant function
+     Ignores the second argument.
+     Or: Construct a function that always returns a static value.
+
+     Type: const :: a -> b -> a
+     Example:
+       let f = const 5; in f 10
+       => 5
+  */
   const = x: y: x;
 
-  # Named versions corresponding to some builtin operators.
+
+  ## Named versions corresponding to some builtin operators.
+
+  /* Concat two strings */
   concat = x: y: x ++ y;
+
+  /* boolean “or” */
   or = x: y: x || y;
+
+  /* boolean “and” */
   and = x: y: x && y;
+
+  /* Merge two attribute sets shallowly, right side trumps left
+
+     Example:
+       mergeAttrs { a = 1; b = 2; } // { b = 3; c = 4; }
+       => { a = 1; b = 3; c = 4; }
+  */
   mergeAttrs = x: y: x // y;
 
+
   # Compute the fixed point of the given function `f`, which is usually an
   # attribute set that expects its final, non-recursive representation as an
   # argument: