I aligned the argument names in the code with those in the documentation and added assertions to make the functions more user‐friendly.

Seems like #342330 is bit of a duplicate of this. This PR also has some f to apply to the returned value. And there is a slight difference in the recursion flow.

If I understand correctly, one could implement the proposed collect' function based on mapAttrsToListRecursiveCond:

collect' = pred: set: mapAttrsToListRecursiveCond (path: set: !(pred path set)) (path: value: { inherit path value; }) set;

Using concatMap instead of a combination of concatLists + mapAttrsToList (which uses map internally) might however be more efficient.

I re‐implemented the function using concatMap instead of concatLists + mapAttrsToList, which should be more efficient according to the Nix reference manual.

To avoid repeating path ++ [ name ] and set.${name} I introduced a second function mapRecursive into the recursion, I am however not sure if that is considered good style. let bindings for the new path and value would be an alternative if call stack depth is of concern.

Hello, I'm the author of #342330. I don't really mind which one we go with, but it feels a bit wasteful to reach for an noop function to use collect' (although implementing mapAttrsToListRecursiveCond in terms of collect' is probably much more wasteful with regards to list allocation). I'd be happy to have this one merged first though, and then rather optimize later.

[...] which should be more efficient according to the Nix reference manual.

Just in case you didn't know, you can verify this by configuring nix with envvars such as NIX_SHOW_STATS=1 and NIX_COUNT_CALLS=1

Hello, I'm the author of #342330. I don't really mind which one we go with, but it feels a bit wasteful to reach for an noop function to use collect' (although implementing mapAttrsToListRecursiveCond in terms of collect' is probably much more wasteful with regards to list allocation). I'd be happy to have this one merged first though, and then rather optimize later.

Agreed. I also expect an implementation of collect' based on mapAttrsToListRecursiveCond to be more efficient than the other way around.

Perhaps we can just measure if an independent implementation of collect' is worth the few extra lines of code.

[...] which should be more efficient according to the Nix reference manual.

Just in case you didn't know, you can verify this by configuring nix with envvars such as NIX_SHOW_STATS=1 and NIX_COUNT_CALLS=1

Thank you. I didn’t know about the NIX_COUNT_CALLS env var.

@hsjobeki sorry for the ping, do you think you could take another look at this at some point?

We can always improve docs and tests later, so let's do it!

While testing out the new function, trying to use it as I had imagined using lib.collect', I found out they did actually work a bit differently. With lib.mapAttrsToListRecursiveCond does not seem possible to avoid catching the leaf attrs of the sets where the recursion did not stop early.

Like, imagine you wanted to do the following:

# input:
{
  a.b.c.i-want-this-one = { x = 1; y = 2; };
  x.y.z.i-want-this-one-too = { x = 1; y = 2; };
  m.n.o.i-dont-want-this-one = { a = 3; b = 4; };
}

# output:
[
  { path = [ "a" "b" "c" "i-want-this-one" ]; value = { x = 1; y = 2; }; }
  { path = [ "x" "y" "z" "i-want-this-one-too" ]; value = { x = 1; y = 2; }; }
]

You might try something like the following:

lib.mapAttrsToListRecursiveCond
  (path: _value: !(lib.elem (lib.last path) [ "i-want-this-one" "i-want-this-one-too" ]))
  (path: value: { inherit path value; })
  input

# output: 
[
  { path = [ "a" "b" "c" "i-want-this-one" ]; value = { x = 1; y = 2; }; }
  { path = [ "x" "y" "z" "i-want-this-one-too" ]; value = { x = 1; y = 2; }; }
  { path = [ "m" "n" "o" "i-dont-want-this-one" "a" ]; value = 3; }
  { path = [ "m" "n" "o" "i-dont-want-this-one" "b" ]; value = 4; }
]

It's not possible to rewrite the condition to exclude the extra leaf nodes, because the current implementation with unconditionally include everything that is not an attrset in the result.

I'm wondering if it would be better to change f : AttrSet -> Bool to f : a -> Bool, and then testing the leaf nodes for inclusion. Then you should be able to add !(isAttrs value) || to the condition to achieve the same result as what is done currently. Since it's merged so recently, maybe we could redo the implementation quickly before anyone starts using it? Although, I wonder if the map naming would be accurate anymore?

I'm wondering if it would be better to change f : AttrSet -> Bool to f : a -> Bool, and then testing the leaf nodes for inclusion. Then you should be able to add !(isAttrs value) || to the condition to achieve the same result as what is done currently. Since it's merged so recently, maybe we could redo the implementation quickly before anyone starts using it? Although, I wonder if the map naming would be accurate anymore?

I don't think we should change that, because this is how all the other xxxCond functions behave as well, right? This condition is just to decide whether to recurse into an attrset or not, by definition.

I don't think we should change that, because this is how all the other xxxCond functions behave as well, right? This condition is just to decide whether to recurse into an attrset or not, by definition.

Yes, that's why I'm wondering about renaming. I was under the impression that this PR would superseed #342330, but I'm not able to achieve what I'm trying to do with this implementation. Considering that making the change would still let you be able to achieve the normal map cond, I was hoping we could change it. Alternatively, implement mapAttrsToListRecursiveCond in terms of collect'.

I'd not change anything about this function, because it aligns with other functions that work the same way. If that means it does not replace #342330, then that PR should be continued.

Alternatively, implement mapAttrsToListRecursiveCond in terms of collect'.

This could be done later, if it turns out to be efficient enough, I'd say.

Yes, that's why I'm wondering about renaming. I was under the impression that this PR would superseed #342330, but I'm not able to achieve what I'm trying to do with this implementation. Considering that making the change would still let you be able to achieve the normal map cond, I was hoping we could change it.

You should be able to do:

lib.mapAttrsToListRecursiveCond
  (path: _value: !(lib.elem (lib.last path) [ "i-want-this-one" "i-want-this-one-too" "i-dont-want-this-one" ]))
  (path: value: { inherit path value; })
  input

Then do a second pass with filter, which is probably okay depending on the data.

This function seems to map any primitive leafs, independently of the pred.
Maybe we can still push collect' as an inverse of this function and try to unify them via #342330

Alternatively, implement mapAttrsToListRecursiveCond in terms of collect'.

This shouldn't be possible currently right? Because collect' doesn't have 2 independent functions for collecting and mapping and its pred doesn't take the path as argument. We should try to make them equal first.

While i think map is mostly for performance, so we don't need to make a second pass over the list.
We could also add another argument later filter that independently controls whether to include the leaf element, but its a tradeoff of having an extra argument, that might not be needed. (depends on your data probably)

With the status quo, after @wolfgangwalther did the merge, i would try to use it as is.
Though i am also not super happy with the name and would probably rather like to rename this in the future. That's always possible.

@h7x4 Could you probably try what is necessary to implement this in terms of collect' ?
I think that collect' (v: !isAttrs v || !pred v) attrs should be equivalent to mapAttrsToListRecursiveCond pred id attrs (without path) (correct me if i am wrong)

Going forward i would try to enhance #342330 and try to make it a superset of this function. I am not sure how both compare in performance (they need to be kind of comparable first) should we take a look at the stats and continue the discussion in the other PR? I would take an extra look at list allocations and then decide if its worth to unify one in the terms of another?

De Morgan style:
if isAttrs && pred then recurse else collect
:=
if ! isAttrs || ! pred then collect else recurse

So we can spot that we always collect if the value is not an attribute set, independently from the predicate.
Which can be problematic in non-homogenous attribute sets.

we might accept this as consistent to mapAttrsRecursiveCond which uses the same logic, and implement a less opinionated logic in #342330,
The problem is the static isAttrs which is needed for recursing, but also affect the opposite branch which is when to collect

According to the docs of mapAttrsRecursiveCond the following can be used to collect derivations but this would also collect any primitve value (or lists), due to this exact problem.

nix-repl> lib.mapAttrsRecursiveCond (as: ! lib.isDerivation as) (p: lib.id) { hello = pkgs.hello; a = 1; }
{
  a = 1;
  hello = «derivation /nix/store/5g60vyp4cbgwl12pav5apyi571smp62s-hello-2.12.2.drv»;
}

(Sorry for splitting my thoughts, i hope you could follow :) )