`builtins.mergeMapAttrs` (or `builtins.concatMapAttrs`)

[roberth]

Is your feature request related to a problem? Please describe.

Nixpkgs lib defines concatMapAttrs f attrs, which is a very versatile function. (To those it may concern: by virtue of being almost the monadic bind operation on attrsets. See here. Almost => no associativity due to attribute name collisions iirc)

Describe the solution you'd like

Add to builtins a primop that behaves like Nixpkgs' lib.concatMapAttrs. It could be builtins.concatMapAttrs or a different name, such as flatMap attrs or mergeMapAttrs. Its implementation will be slightly more efficient than that in lib, and lib may reuse it, so that it becomes a polyfill.
The added efficiency comes from having no intermediate Nix lists, and may build the attrset in one go.

The current implementation in lib has the following behaviors, which could be optimized away (in order of increasing implementation work):

1. performs more function calls (significant, since we're an interpreter, and our calls perform allocations)
2. creates and sorts intermediate attrsets after each f call (except the final one which is the return value)
3. creates and sorts intermediate attrsets returned by f

• (1) and (2) a trivially solved by implementing this in C++.

• (3) may feel unavoidable, but can be improved with Prototype: accumulate attrset updates, perform k-way merge #11290

  • or a variation that streams an insertion sort, "accumulating" individual attrs, rather than a bunch of attrsets.
  • this is a nice to have, because (1) and (2) are sufficient reason to implement the builtin.

If we pick a new name, we could make attribute name collisions an error, which iirc would make it a lawful monad in all the successful cases. Errors are better than buggy behavior somewhere deep down in some expression, because how would you find the bug.

Describe alternatives you've considered

• Perhaps make it flatMapAttrs or mergeMapAttrs. concat kinda works by extrapolating from lists, but I'm not super happy about that.

• mergeMapAttrsWith (name: values: merge name values) f attrs to handle the collisions.
  This is like zipAttrsWith (name: values: if length values == 1 then head values else m name values) but without allocating a whole bunch of singleton lists.

  • I feel like this isn't sufficiently distinct to warrant a separate builtin
  • => describe the connection in the docs instead.

Additional context

• lib/attrsets: add concatMapAttrs nixpkgs#201527

Priorities

Add 👍 to issues you find important.

[hsjobeki]

Could you give some example how a function call would look like?

Same as concatMapAttrs ?

mergeMapAttrs 
  (name: value: { ${name + "-mapped"} = value * 2 ; } )
  { foo = 1; bar =2; nested.foo = 3; }
=>
{
  { foo-mapped = 2; bar-mapped = 4; nested-mapped.foo = 6; }
}

Would it make sense to accept an optional merge function.

mergeMapAttrs {
  mapFn =  (name: value: { ${name + "-mapped"} = value * 2 ; } );
  mergeFn = (name: values: merge name values) # defaults to an error function? 
  } 
  { foo = 1; bar =2; nested.foo = 3; }
=>
{
  { foo-mapped = 2; bar-mapped = 4; nested-mapped.foo = 6; }
}

would taking an attribute set as arguments add some benefit? in this case: default behavior that can be customized.

[roberth]

@hsjobeki

Same as concatMapAttrs?

Yes. I've updated the description.

accept an optional merge function.

Perhaps, but it has a slight cost, and not much, but non-zero benefit. See the alternatives section.

would taking an attribute set as arguments add some benefit? in this case: default behavior that can be customized.

In the current evaluator implementation, "argument attrsets" aren't special or optimized, whereas curried function application of positional arguments to primops is optimized. I'd like this to make no difference, but optimizing those calls is non-trivial, because we don't have static knowledge of the function, given an application Expr.
So an attrset based call would have a slight overhead compared to entirely positional arguments.

[hsjobeki]

I have to admit i am a big fan of this Idea overall.

[edolstra]

Team meeting notes:

• Idea approved in principle, but needs implementation + benchmarking to see if the Nixpkgs speedup is worth it.

[nixos-discourse]

This issue has been mentioned on NixOS Discourse. There might be relevant details there:

https://discourse.nixos.org/t/2024-11-20-nix-team-meeting-minutes-196/56688/1