filter

lib.lists.filter

Primop

Docs pulled from | This Revision | about 23 hours ago

Nix manual

Takes 2 arguments

f, list

Return a list consisting of the elements of list for which the function f returns true.

Time Complexity

O(n * T_f) (eager; predicate is forced) where:

n = list length T_f = predicate evaluation time

Noogle detected

Aliases

Detected Type

filter :: (a -> Bool) -> [a] -> [a]

Implementation

This function is implemented in c++ and is part of the native nix runtime.

src/libexpr/primops.cc:3856

static void prim_filter(EvalState & state, const PosIdx pos, Value ** args, Value & v)
{
    state.forceList(*args[1], pos, "while evaluating the second argument passed to builtins.filter");

    if (args[1]->listSize() == 0) {
        v = *args[1];
        return;
    }

    state.forceFunction(*args[0], pos, "while evaluating the first argument passed to builtins.filter");

    auto len = args[1]->listSize();
    SmallValueVector<nonRecursiveStackReservation> vs(len);
    size_t k = 0;

    bool same = true;
    for (size_t n = 0; n < len; ++n) {
        Value res;
        state.callFunction(*args[0], *args[1]->listView()[n], res, noPos);
        if (state.forceBool(
                res, pos, "while evaluating the return value of the filtering function passed to builtins.filter"))
            vs[k++] = args[1]->listView()[n];
        else
            same = false;
    }

    if (same)
        v = *args[1];
    else {
        auto list = state.buildList(k);
        for (const auto & [n, v] : enumerate(list))
            v = vs[n];
        v.mkList(list);
    }
}