A primop (or two) for canonicalizing a value

[copumpkin]

I think it's fairly common for us to know that the order of elements in a list (or even possible duplicates) don't affect the semantics of an operation. Nonetheless, they do affect the hash of a derivation they get fed into. I'd normally be inclined to just call lib.sort in nixpkgs against the list, but that's kind of slow, and adding uniq on top of that is even slower.

It seems like it would make sense to make a couple of native-code primops to canonicalize a list before using it. One would sort, the other would sort and uniq. Does that make sense?

@pikajude also appeared to care on IRC

[pikajude]

So like a Set type?

[copumpkin]

Set and multiset, yep. If we can assume an attribute set has a canonical key ordering, going to and from would work and probably be fairly fast, but my sense was that attribute sets weren't ordered.

[stale]

I marked this as stale due to inactivity. → More info

[tomberek]

Possible to implement something close to this with builtins.genericClosure? https://github.com/NixOS/nix/pull/6305/files

Close?