lib.lists.foldl': Redo documentation

Co-Authored-By: Robert Hensing <robert@roberthensing.nl>

1 files changed, 48 insertions, 7 deletions

diff --git a/lib/lists.nix b/lib/lists.nix
index 4a13550ca9e..8c5099084bb 100644
--- a/lib/lists.nix
+++ b/lib/lists.nix
@@ -86,15 +86,56 @@ 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.)
+    After each application of the operator, the resulting 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';
+    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₁   =                      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:
+
+    builtins.foldl' op acc list;
 
   /* Map with index starting from 0