diff options
| -rw-r--r-- | lib/attrsets.nix | 8 | ||||
| -rw-r--r-- | lib/lists.nix | 62 | ||||
| -rw-r--r-- | lib/tests/misc.nix | 36 | ||||
| -rw-r--r-- | nixos/doc/manual/release-notes/rl-2311.section.md | 5 |
4 files changed, 98 insertions, 13 deletions
diff --git a/lib/attrsets.nix b/lib/attrsets.nix index 77e36d3271f..b8960cf73f2 100644 --- a/lib/attrsets.nix +++ b/lib/attrsets.nix @@ -338,7 +338,7 @@ rec { ); /* - Like builtins.foldl' but for attribute sets. + Like [`lib.lists.foldl'`](#function-library-lib.lists.foldl-prime) but for attribute sets. Iterates over every name-value pair in the given attribute set. The result of the callback function is often called `acc` for accumulator. It is passed between callbacks from left to right and the final `acc` is the return value of `foldlAttrs`. @@ -372,9 +372,9 @@ rec { 123 foldlAttrs - (_: _: v: v) - (throw "initial accumulator not needed") - { z = 3; a = 2; }; + (acc: _: _: acc) + 3 + { z = throw "value not needed"; a = throw "value not needed"; }; -> 3 diff --git a/lib/lists.nix b/lib/lists.nix index 0800aeb6545..3835e3ba69c 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 diff --git a/lib/tests/misc.nix b/lib/tests/misc.nix index 80223dccb26..ec306acbb76 100644 --- a/lib/tests/misc.nix +++ b/lib/tests/misc.nix @@ -505,6 +505,38 @@ runTests { }; }; + testFoldl'Empty = { + expr = foldl' (acc: el: abort "operation not called") 0 [ ]; + expected = 0; + }; + + testFoldl'IntegerAdding = { + expr = foldl' (acc: el: acc + el) 0 [ 1 2 3 ]; + expected = 6; + }; + + # The accumulator isn't forced deeply + testFoldl'NonDeep = { + expr = take 3 (foldl' + (acc: el: [ el ] ++ acc) + [ (abort "unevaluated list entry") ] + [ 1 2 3 ]); + expected = [ 3 2 1 ]; + }; + + # Compared to builtins.foldl', lib.foldl' evaluates the first accumulator strictly too + testFoldl'StrictInitial = { + expr = (builtins.tryEval (foldl' (acc: el: el) (throw "hello") [])).success; + expected = false; + }; + + # Make sure we don't get a stack overflow for large lists + # This number of elements would notably cause a stack overflow if it was implemented without the `foldl'` builtin + testFoldl'Large = { + expr = foldl' (acc: el: acc + el) 0 (range 0 100000); + expected = 5000050000; + }; + testTake = testAllTrue [ ([] == (take 0 [ 1 2 3 ])) ([1] == (take 1 [ 1 2 3 ])) @@ -708,7 +740,7 @@ runTests { # should just return the initial value emptySet = foldlAttrs (throw "function not needed") 123 { }; # should just evaluate to the last value - accNotNeeded = foldlAttrs (_acc: _name: v: v) (throw "accumulator not needed") { z = 3; a = 2; }; + valuesNotNeeded = foldlAttrs (acc: _name: _v: acc) 3 { z = throw "value z not needed"; a = throw "value a not needed"; }; # the accumulator doesnt have to be an attrset it can be as trivial as being just a number or string trivialAcc = foldlAttrs (acc: _name: v: acc * 10 + v) 1 { z = 1; a = 2; }; }; @@ -718,7 +750,7 @@ runTests { names = [ "bar" "foo" ]; }; emptySet = 123; - accNotNeeded = 3; + valuesNotNeeded = 3; trivialAcc = 121; }; }; diff --git a/nixos/doc/manual/release-notes/rl-2311.section.md b/nixos/doc/manual/release-notes/rl-2311.section.md index 1ffaa0c0b5d..123242926e2 100644 --- a/nixos/doc/manual/release-notes/rl-2311.section.md +++ b/nixos/doc/manual/release-notes/rl-2311.section.md @@ -238,6 +238,11 @@ - `networking.networkmanager.firewallBackend` was removed as NixOS is now using iptables-nftables-compat even when using iptables, therefore Networkmanager now uses the nftables backend unconditionally. +- [`lib.lists.foldl'`](https://nixos.org/manual/nixpkgs/stable#function-library-lib.lists.foldl-prime) now always evaluates the initial accumulator argument first. + If you depend on the lazier behavior, consider using [`lib.lists.foldl`](https://nixos.org/manual/nixpkgs/stable#function-library-lib.lists.foldl) or [`builtins.foldl'`](https://nixos.org/manual/nix/stable/language/builtins.html#builtins-foldl') instead. + +- [`lib.attrsets.foldlAttrs`](https://nixos.org/manual/nixpkgs/stable#function-library-lib.attrsets.foldlAttrs) now always evaluates the initial accumulator argument first. + - `rome` was removed because it is no longer maintained and is succeeded by `biome`. - The `services.mtr-exporter.target` has been removed in favor of `services.mtr-exporter.jobs` which allows specifying multiple targets. |