groupBy

lib.lists.groupBy

Primop

Docs pulled from | This Revision | 27 minutes ago

Nix manual

Takes 2 arguments

f, list

Groups elements of list together by the string returned from the function f called on each element. It returns an attribute set where each attribute value contains the elements of list that are mapped to the same corresponding attribute name returned by f.

For example,

builtins.groupBy (builtins.substring 0 1) ["foo" "bar" "baz"]

evaluates to

{ b = [ "bar" "baz" ]; f = [ "foo" ]; }

Time Complexity

O(N * T_f + N * log k) where:

N = number of list elements T_f = f call evaluation time k = number of unique groups

Noogle detected

Aliases

Detected Type

groupBy :: (a -> String) -> [ a ] -> { [String] :: [a] }

Implementation

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

src/libexpr/primops.cc:4342

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

    ValueVectorMap attrs;

    for (auto vElem : args[1]->listView()) {
        Value res;
        state.callFunction(*args[0], *vElem, res, pos);
        auto name = state.forceStringNoCtx(
            res, pos, "while evaluating the return value of the grouping function passed to builtins.groupBy");
        auto sym = state.symbols.create(name);
        auto vector = attrs.try_emplace<ValueVector>(sym, {}).first;
        vector->second.push_back(vElem);
    }

    auto attrs2 = state.buildBindings(attrs.size());

    for (auto & i : attrs) {
        auto size = i.second.size();
        auto list = state.buildList(size);
        memcpy(list.elems, i.second.data(), sizeof(Value *) * size);
        attrs2.alloc(i.first).mkList(list);
    }

    v.mkAttrs(attrs2.alreadySorted());
}

Implementation

The following is the current implementation of this function.

groupBy =
    builtins.groupBy or (
      pred:
      foldl' (
        r: e:
        let
          key = pred e;
        in
        r // { ${key} = (r.${key} or [ ]) ++ [ e ]; }
      ) { }
    );