mergeAttrsRecursiveList.nix

1 
2 
3 
4 
5 
6 
7 
8 
9 
10 
11 
12 
13 
14 
15 
16 
17 
18 
19 
20 
21 
22 
23 
24 
25 
26 
27 
28 
29 
30 
31 
{
  lib,
  ...
}:

{

  mergeAttrsRecursiveList =
    list:
    let
      # `binaryMerge start end` merges the elements at indices `index` of `list` such that `start <= index < end`
      # Type: Int -> Int -> AttrSet
      binaryMerge =
        start: end:
        # assert start < end; # Invariant
        if end - start >= 2 then
          # If there's at least 2 elements, split the range in two, recurse on each part and merge the result
          # The invariant is satisfied because each half will have at least 1 element
          lib.recursiveUpdate (binaryMerge start (start + (end - start) / 2)) (
            binaryMerge (start + (end - start) / 2) end
          )
        else
          # Otherwise there will be exactly 1 element due to the invariant, in which case we just return it directly
          lib.elemAt list start;
    in
    if list == [ ] then
      # Calling binaryMerge as below would not satisfy its invariant
      { }
    else
      binaryMerge 0 (builtins.length list);
}