Decide on a recursive attribute set tree flattening function

[roberth]

Project description

All of the PRs below try to add a function that recurses into a tree of attrsets.
Clearly there's a need. What needs to be done is decide on the name and behavior of the function.
The name should fit the established naming conventions. The behavior should probably be biased towards keeping it simple and "composable".
Some discussion seems necessary, hence a new thread in this issue to discuss the new function's details.

• lib/attrsets: merge concatMapAttrs recursively #206965
• lib: Working with nested attrsets of packages #202517
• init: lib.{collect',flattenAttrs} #221608
• nixos/dconf: support generating from attrs #234615
• lib.attrsets: add flattenAttrs function #354874

Metadata

• homepage URL:
• source URL: ./lib
• license: mit
• platforms: nix

[figsoda]

maybe we can start with concatMapAttrsWith, something like this

[roberth]

maybe we can start with concatMapAttrsWith, something like this

Is that merge function (used in the linked definition) a recursive merge? Recursive merging without a conditional for identifying leaves will construct the weirdest Frankenstein-esque values if used incorrectly by accident, or used "correctly" on user inputs that can't be validated, which in my opinion is sufficient reason to discourage its indirect use through functions such as the one proposed in this issue.

EDIT: 🤦 skimmed over merge parameter declaration

[figsoda]

Is that merge function (used in the linked definition) a recursive merge?

It can be if you pass in a recursive merge function, is just a more generalized version of the concatMapAttrs in nixpkgs

concatMapAttrsWith (x: y: x // y) would be equivalent to concatMapAttrs, and concatMapAttrsWith recursiveUpdate would be recursive merge

[roberth]

We have rather many possible combinations of recursion, filtering, mapping, and ways to recombine information into a single attribute name.

Picking specific combinations of these strategies and giving a name to them isn't particularly helpful, especially if done in an ad hoc way (without much consideration for naming conventions that would effectively only serve to refer to those multiple strategies in ways that won't be as good as an actual programmatic decomposition of the problem). The Fairbairn threshold suggests that we wouldn't be making any progress towards making the library and programs more understandable that way (at best).

I think the problem can be decomposed at the call site, taking the following shape:

someTraversal
  maybeSomeParameter
  (callbackParams:
    {
      ${attributeName} = callbackParams.value;
    })

Now this pattern doesn't look great, but it does convey all the information in a systematic manner, and unlike an semi-incoherent set of names, this is more like a useful skill that I believe is easy to learn, and can be taught (e.g. in the docs) with a few examples.

What are the choices for each strategy?

• Choice of the traversal
  • non-recursive: concatMapAttrs, with callback parameters name: value:
  • recursive: concatMapAttrsRecursive, with callback parameters attrPath: value

Note: we may want to change concat to merge; see "alternatives" in NixOS/nix#11887

• Choice of filtering

  • non-recursive: concatMapAttrs with or without optionalAttrs in the callback
  • recursive: concatMapAttrsRecursive or concatMapAttrsRecursiveUntil (where maybeSomeParameter exists and determines which nodes qualify as value for the callback).

• Choice of naming (attributeName in the pattern)

  • last attrPath
  • concatStringsSep "." attrPath

• Bonus: you can return 0 to many attributes

Example: in the context of flakes, convert legacyPackages to a packages compatible flat attrset.

concatMapAttrsRecursiveUntil (_path: isDerivation) (attrPath: value: {
  ${concatStringsSep "." attrPath} = value;
})

Would flattenAttrsRecursiveWithSep "." isDerivation be better? Maybe, because I'm familiar with some of the other function names, but this creates a sprawl of functions that each have to be learned or looked up, whereas the example can be understood by knowing the basic functions. What's more, it will be easier to make most modifications, because you can edit right there how the attribute names are constructed, or how the values are filtered.

So I think a function like flattenAttrsRecursiveWithSep does not contribute to making the library easier to use.
Or maybe I'm wrong, but I think it would be prudent to start with a better primitive like concatMapAttrsRecursiveUntil, and only develop conveniences after that.

I'd happily accept a flattenLegacyPackages {} instead of a flattenAttrsRecursiveWithSep, because it is a proper abstraction that is named in its own terminology, and not a function that only seems to exists for the purpose of typing 10-20% fewer characters while obfuscating what really happens, despite all the good intentions.

tl;dr: start with concatMapAttrsRecursiveUntil and concatMapAttrsRecursive?

(btw the x + xUntil pattern is well established in this family of functions, so that's cheap; not all names should weigh equally when judging their cost/benefit. Having a good system reduces the cost a bit.)

Related:

• concatMapAttrs
• foldAttrs
• zipAttrsWith

[hsjobeki]

My personal liking is towards "collect"
Especially because it is short and memorizable.
(Say hello: fairbairn threshold)

I think the Initial implementation of collect wasnt generic enough.

All of the linked PRs can be acheived using collect' from one of the PRs and sometimes wrapping it with listToAttrs.

i think the Interface is good and Kind of Matches your Idea. I dislike that overly precise name (concatMapAttrsRecursiveUntil) because its to long and hard to type.

I will try and collect all functions from those categories and see how to apply intuitive names for them.

maybe we can also find a way that avoids creating an intermediate list for performance reasons.

[roberth]

overly precise name (concatMapAttrsRecursiveUntil)

I agree. Was trying to stick with the naming system, but that may not be necessary.

find a way that avoids creating an intermediate list

Achievable with concatMapAttrs, although the implementation isn't currently free of lists, but I propose to fix that:

• builtins.mergeMapAttrs (or builtins.concatMapAttrs) nix#11887
• perhaps no surprise considering even builtins.filterAttrs nix#11888 is yet to be done

[roberth]

concatMapAttrsRecursive

Transforming the leaves of a tree is not a particularly "recursive" computation from a user perspective.