query
On this page

lib.foldl' (Prime)

Inputs

Type

Examples

lib.lists.foldl' usage example

foldl'

lib.foldl'

Docs pulled from | This Revision | 15 minutes ago

Nixpkgs manual

Reduce a list by applying a binary operator from left to right, starting with an initial accumulator.

Before each application of the operator, the accumulator value is evaluated. This behavior makes this function stricter than foldl.

Unlike builtins.foldl', the initial accumulator argument is evaluated before the first iteration.

A call like

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.

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ₙ

Inputs

op

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
acc

The initial accumulator value.

The accumulator value is evaluated in any case before the first iteration starts.

To avoid evaluation even before the list argument is given an eta expansion can be used:

list: lib.foldl' op acc list
list

The list to fold

Type

foldl' :: (a -> b -> a) -> a -> [b] -> a

Examples

lib.lists.foldl' usage example

foldl' (acc: x: acc + x) 0 [1 2 3]
=> 6
(lib.lists.foldl')

Nix manual

Reduce a list by applying a binary operator, from left to right, e.g.

foldl' op nul [ x0 x1 x2 ]
  =
    let
      strictly = f: a: builtins.seq a (f a);
      y0 = op nul x0;
      y1 = strictly op y0 x1;
      y2 = strictly op y1 x2;
    in
      y2

  # and, ignoring strictness/laziness
  ==
    op (op (op nul x0) x1) x2

For example, foldl' (acc: elem: acc + elem) 0 [1 2 3] evaluates to 6 and foldl' (acc: elem: { "${elem}" = elem; } // acc) {} ["a" "b"] evaluates to { a = "a"; b = "b"; }.

The first argument of op is the accumulator whereas the second argument is the current element being processed.

The return value of each application of op is evaluated immediately, even for intermediate values. This way, foldl' can operate in constant stack space, allowing it to operate on large lists, regardless of max-call-depth.

Conventionally, a fold function without the ' ("prime") preserves laziness, but lacks these benefits. See also Nixpkgs lib.foldl.

Has linear time complexity in the size of the list.

Noogle detected

Aliases

Implementation

The following is the current implementation of this function.

op: acc:
    # 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.
    seq acc (foldl' op acc)