partition
lib.partition
Primop
Docs pulled from | This Revision | 18 minutes ago
Nixpkgs manual
Splits the elements of a list in two lists, right and
wrong, depending on the evaluation of a predicate.
Inputs
pred-
Predicate
list-
Input list
Type
partition :: (a -> Bool) -> [a] -> { right :: [a]; wrong :: [a]; }
Examples
lib.lists.partition usage example
partition (x: x > 2) [ 5 1 2 3 4 ]
=> { right = [ 5 3 4 ]; wrong = [ 1 2 ]; }
Nix manual
Takes 2 arguments
pred, list
Given a predicate function pred, this function returns an
attrset containing a list named right, containing the elements
in list for which pred returned true, and a list named
wrong, containing the elements for which it returned
false. For example,
builtins.partition (x: x > 10) [1 23 9 3 42]
evaluates to
{ right = [ 23 42 ]; wrong = [ 1 9 3 ]; }
Time Complexity
O(n * T_pred) where:
n = list length
T_pred = pred call evaluation time
Noogle detected
Implementation
This function is implemented in c++ and is part of the native nix runtime.
static void prim_partition(EvalState & state, const PosIdx pos, Value ** args, Value & v)
{
state.forceFunction(*args[0], pos, "while evaluating the first argument passed to builtins.partition");
state.forceList(*args[1], pos, "while evaluating the second argument passed to builtins.partition");
auto len = args[1]->listSize();
ValueVector right, wrong;
for (size_t n = 0; n < len; ++n) {
auto vElem = args[1]->listView()[n];
state.forceValue(*vElem, pos);
Value res;
state.callFunction(*args[0], *vElem, res, pos);
if (state.forceBool(
res, pos, "while evaluating the return value of the partition function passed to builtins.partition"))
right.push_back(vElem);
else
wrong.push_back(vElem);
}
auto attrs = state.buildBindings(2);
auto rsize = right.size();
auto rlist = state.buildList(rsize);
if (rsize)
memcpy(rlist.elems, right.data(), sizeof(Value *) * rsize);
attrs.alloc(state.s.right).mkList(rlist);
auto wsize = wrong.size();
auto wlist = state.buildList(wsize);
if (wsize)
memcpy(wlist.elems, wrong.data(), sizeof(Value *) * wsize);
attrs.alloc(state.s.wrong).mkList(wlist);
v.mkAttrs(attrs);
}