1 files changed, 68 insertions, 7 deletions
diff --git a/lib/lists.nix b/lib/lists.nix
index 0800aeb6545..15047f488f4 100644
--- a/lib/lists.nix
+++ b/lib/lists.nix
@@ -86,15 +86,63 @@ rec {
         else op (foldl' (n - 1)) (elemAt list n);
     in foldl' (length list - 1);
 
-  /* Strict version of `foldl`.
+  /*
+    Reduce a list by applying a binary operator from left to right,
+    starting with an initial accumulator.
 
-     The difference is that evaluation is forced upon access. Usually used
-     with small whole results (in contrast with lazily-generated list or large
-     lists where only a part is consumed.)
+    Before each application of the operator, the accumulator value is evaluated.
+    This behavior makes this function stricter than [`foldl`](#function-library-lib.lists.foldl).
 
-     Type: foldl' :: (b -> a -> b) -> b -> [a] -> b
-  */
-  foldl' = builtins.foldl' or foldl;
+    Unlike [`builtins.foldl'`](https://nixos.org/manual/nix/unstable/language/builtins.html#builtins-foldl'),
+    the initial accumulator argument is evaluated before the first iteration.
+
+    A call like
+
+    ```nix
+    foldl' op acc₀ [ x₀ x₁ x₂ ... xₙ₋₁ xₙ ]
+    ```
+
+    is (denotationally) equivalent to the following,
+    but with the added benefit that `foldl'` itself will never overflow the stack.
+
+    ```nix
+    let
+      acc₁   = builtins.seq acc₀   (op acc₀   x₀  );
+      acc₂   = builtins.seq acc₁   (op acc₁   x₁  );
+      acc₃   = builtins.seq acc₂   (op acc₂   x₂  );
+      ...
+      accₙ   = builtins.seq accₙ₋₁ (op accₙ₋₁ xₙ₋₁);
+      accₙ₊₁ = builtins.seq accₙ   (op accₙ   xₙ  );
+    in
+    accₙ₊₁
+
+    # Or ignoring builtins.seq
+    op (op (... (op (op (op acc₀ x₀) x₁) x₂) ...) xₙ₋₁) xₙ
+    ```
+
+    Type: foldl' :: (acc -> x -> acc) -> acc -> [x] -> acc
+
+    Example:
+      foldl' (acc: x: acc + x) 0 [1 2 3]
+      => 6
+  */
+  foldl' =
+    /* The binary operation to run, where the two arguments are:
+
+    1. `acc`: The current accumulator value: Either the initial one for the first iteration, or the result of the previous iteration
+    2. `x`: The corresponding list element for this iteration
+    */
+    op:
+    # The initial accumulator value
+    acc:
+    # The list to fold
+    list:
+
+    # The builtin `foldl'` is a bit lazier than one might expect.
+    # See https://github.com/NixOS/nix/pull/7158.
+    # In particular, the initial accumulator value is not forced before the first iteration starts.
+    builtins.seq acc
+      (builtins.foldl' op acc list);
 
   /* Map with index starting from 0
 
@@ -773,6 +821,19 @@ rec {
    */
   unique = foldl' (acc: e: if elem e acc then acc else acc ++ [ e ]) [];
 
+  /* Check if list contains only unique elements. O(n^2) complexity.
+
+     Type: allUnique :: [a] -> bool
+
+     Example:
+       allUnique [ 3 2 3 4 ]
+       => false
+       allUnique [ 3 2 4 1 ]
+       => true
+   */
+  allUnique = list: (length (unique list) == length list);
+
+
   /* Intersects list 'e' and another list. O(nm) complexity.
 
      Example: