foldl'
builtins.foldl'
Nix manual
Takes 3 arguments
op, nul, list
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.
Time Complexity
O(n * T_op) where:
n = list length
T_op = op call evaluation time
Noogle detected
foldl' :: (a -> b -> a) -> a -> [b] -> a
Implementation
This function is implemented in c++ and is part of the native nix runtime.
static void prim_foldlStrict(EvalState & state, const PosIdx pos, Value ** args, Value & v)
{
state.forceFunction(*args[0], pos, "while evaluating the first argument passed to builtins.foldlStrict");
state.forceList(*args[2], pos, "while evaluating the third argument passed to builtins.foldlStrict");
if (args[2]->listSize()) {
Value * vCur = args[1];
auto listView = args[2]->listView();
for (auto [n, elem] : enumerate(listView)) {
Value * vs[]{vCur, elem};
vCur = n == args[2]->listSize() - 1 ? &v : state.allocValue();
state.callFunction(*args[0], vs, *vCur, pos);
}
state.forceValue(v, pos);
} else {
state.forceValue(*args[1], pos);
v = *args[1];
}
}