lib/lists.nix

   1 /**
   2   General list operations.
   3 */
   4 { lib }:
   5 let
   6   inherit (lib.strings) toInt;
   7   inherit (lib.trivial) compare min id warn pipe;
   8   inherit (lib.attrsets) mapAttrs;
   9 in
  10 rec {
  11
  12   inherit (builtins) head tail length isList elemAt concatLists filter elem genList map;
  13
  14   /**
  15     Create a list consisting of a single element. `singleton x` is
  16     sometimes more convenient with respect to indentation than `[x]`
  17     when x spans multiple lines.
  18
  19     # Inputs
  20
  21     `x`
  22
  23     : 1\. Function argument
  24
  25     # Type
  26
  27     ```
  28     singleton :: a -> [a]
  29     ```
  30
  31     # Examples
  32     :::{.example}
  33     ## `lib.lists.singleton` usage example
  34
  35     ```nix
  36     singleton "foo"
  37     => [ "foo" ]
  38     ```
  39
  40     :::
  41   */
  42   singleton = x: [x];
  43
  44   /**
  45     Apply the function to each element in the list.
  46     Same as `map`, but arguments flipped.
  47
  48     # Inputs
  49
  50     `xs`
  51
  52     : 1\. Function argument
  53
  54     `f`
  55
  56     : 2\. Function argument
  57
  58     # Type
  59
  60     ```
  61     forEach :: [a] -> (a -> b) -> [b]
  62     ```
  63
  64     # Examples
  65     :::{.example}
  66     ## `lib.lists.forEach` usage example
  67
  68     ```nix
  69     forEach [ 1 2 ] (x:
  70       toString x
  71     )
  72     => [ "1" "2" ]
  73     ```
  74
  75     :::
  76   */
  77   forEach = xs: f: map f xs;
  78
  79   /**
  80     “right fold” a binary function `op` between successive elements of
  81     `list` with `nul` as the starting value, i.e.,
  82     `foldr op nul [x_1 x_2 ... x_n] == op x_1 (op x_2 ... (op x_n nul))`.
  83
  84
  85     # Inputs
  86
  87     `op`
  88
  89     : 1\. Function argument
  90
  91     `nul`
  92
  93     : 2\. Function argument
  94
  95     `list`
  96
  97     : 3\. Function argument
  98
  99     # Type
 100
 101     ```
 102     foldr :: (a -> b -> b) -> b -> [a] -> b
 103     ```
 104
 105     # Examples
 106     :::{.example}
 107     ## `lib.lists.foldr` usage example
 108
 109     ```nix
 110     concat = foldr (a: b: a + b) "z"
 111     concat [ "a" "b" "c" ]
 112     => "abcz"
 113     # different types
 114     strange = foldr (int: str: toString (int + 1) + str) "a"
 115     strange [ 1 2 3 4 ]
 116     => "2345a"
 117     ```
 118
 119     :::
 120   */
 121   foldr = op: nul: list:
 122     let
 123       len = length list;
 124       fold' = n:
 125         if n == len
 126         then nul
 127         else op (elemAt list n) (fold' (n + 1));
 128     in fold' 0;
 129
 130   /**
 131     `fold` is an alias of `foldr` for historic reasons
 132   */
 133   # FIXME(Profpatsch): deprecate?
 134   fold = foldr;
 135
 136
 137   /**
 138     “left fold”, like `foldr`, but from the left:
 139
 140     `foldl op nul [x_1 x_2 ... x_n] == op (... (op (op nul x_1) x_2) ... x_n)`.
 141
 142     # Inputs
 143
 144     `op`
 145
 146     : 1\. Function argument
 147
 148     `nul`
 149
 150     : 2\. Function argument
 151
 152     `list`
 153
 154     : 3\. Function argument
 155
 156     # Type
 157
 158     ```
 159     foldl :: (b -> a -> b) -> b -> [a] -> b
 160     ```
 161
 162     # Examples
 163     :::{.example}
 164     ## `lib.lists.foldl` usage example
 165
 166     ```nix
 167     lconcat = foldl (a: b: a + b) "z"
 168     lconcat [ "a" "b" "c" ]
 169     => "zabc"
 170     # different types
 171     lstrange = foldl (str: int: str + toString (int + 1)) "a"
 172     lstrange [ 1 2 3 4 ]
 173     => "a2345"
 174     ```
 175
 176     :::
 177   */
 178   foldl = op: nul: list:
 179     let
 180       foldl' = n:
 181         if n == -1
 182         then nul
 183         else op (foldl' (n - 1)) (elemAt list n);
 184     in foldl' (length list - 1);
 185
 186   /**
 187     Reduce a list by applying a binary operator from left to right,
 188     starting with an initial accumulator.
 189
 190     Before each application of the operator, the accumulator value is evaluated.
 191     This behavior makes this function stricter than [`foldl`](#function-library-lib.lists.foldl).
 192
 193     Unlike [`builtins.foldl'`](https://nixos.org/manual/nix/unstable/language/builtins.html#builtins-foldl'),
 194     the initial accumulator argument is evaluated before the first iteration.
 195
 196     A call like
 197
 198     ```nix
 199     foldl' op acc₀ [ x₀ x₁ x₂ ... xₙ₋₁ xₙ ]
 200     ```
 201
 202     is (denotationally) equivalent to the following,
 203     but with the added benefit that `foldl'` itself will never overflow the stack.
 204
 205     ```nix
 206     let
 207       acc₁   = builtins.seq acc₀   (op acc₀   x₀  );
 208       acc₂   = builtins.seq acc₁   (op acc₁   x₁  );
 209       acc₃   = builtins.seq acc₂   (op acc₂   x₂  );
 210       ...
 211       accₙ   = builtins.seq accₙ₋₁ (op accₙ₋₁ xₙ₋₁);
 212       accₙ₊₁ = builtins.seq accₙ   (op accₙ   xₙ  );
 213     in
 214     accₙ₊₁
 215
 216     # Or ignoring builtins.seq
 217     op (op (... (op (op (op acc₀ x₀) x₁) x₂) ...) xₙ₋₁) xₙ
 218     ```
 219
 220     # Inputs
 221
 222     `op`
 223
 224     : The binary operation to run, where the two arguments are:
 225
 226     1. `acc`: The current accumulator value: Either the initial one for the first iteration, or the result of the previous iteration
 227     2. `x`: The corresponding list element for this iteration
 228
 229     `acc`
 230
 231     : The initial accumulator value.
 232
 233       The accumulator value is evaluated in any case before the first iteration starts.
 234
 235       To avoid evaluation even before the `list` argument is given an eta expansion can be used:
 236
 237       ```nix
 238       list: lib.foldl' op acc list
 239       ```
 240
 241     `list`
 242
 243     : The list to fold
 244
 245     # Type
 246
 247     ```
 248     foldl' :: (acc -> x -> acc) -> acc -> [x] -> acc
 249     ```
 250
 251     # Examples
 252     :::{.example}
 253     ## `lib.lists.foldl'` usage example
 254
 255     ```nix
 256     foldl' (acc: x: acc + x) 0 [1 2 3]
 257     => 6
 258     ```
 259
 260     :::
 261   */
 262   foldl' =
 263     op:
 264     acc:
 265     # The builtin `foldl'` is a bit lazier than one might expect.
 266     # See https://github.com/NixOS/nix/pull/7158.
 267     # In particular, the initial accumulator value is not forced before the first iteration starts.
 268     builtins.seq acc
 269       (builtins.foldl' op acc);
 270
 271   /**
 272     Map with index starting from 0
 273
 274     # Inputs
 275
 276     `f`
 277
 278     : 1\. Function argument
 279
 280     `list`
 281
 282     : 2\. Function argument
 283
 284     # Type
 285
 286     ```
 287     imap0 :: (int -> a -> b) -> [a] -> [b]
 288     ```
 289
 290     # Examples
 291     :::{.example}
 292     ## `lib.lists.imap0` usage example
 293
 294     ```nix
 295     imap0 (i: v: "${v}-${toString i}") ["a" "b"]
 296     => [ "a-0" "b-1" ]
 297     ```
 298
 299     :::
 300   */
 301   imap0 = f: list: genList (n: f n (elemAt list n)) (length list);
 302
 303   /**
 304     Map with index starting from 1
 305
 306
 307     # Inputs
 308
 309     `f`
 310
 311     : 1\. Function argument
 312
 313     `list`
 314
 315     : 2\. Function argument
 316
 317     # Type
 318
 319     ```
 320     imap1 :: (int -> a -> b) -> [a] -> [b]
 321     ```
 322
 323     # Examples
 324     :::{.example}
 325     ## `lib.lists.imap1` usage example
 326
 327     ```nix
 328     imap1 (i: v: "${v}-${toString i}") ["a" "b"]
 329     => [ "a-1" "b-2" ]
 330     ```
 331
 332     :::
 333   */
 334   imap1 = f: list: genList (n: f (n + 1) (elemAt list n)) (length list);
 335
 336   /**
 337     Filter a list for elements that satisfy a predicate function.
 338     The predicate function is called with both the index and value for each element.
 339     It must return `true`/`false` to include/exclude a given element in the result.
 340     This function is strict in the result of the predicate function for each element.
 341     This function has O(n) complexity.
 342
 343     Also see [`builtins.filter`](https://nixos.org/manual/nix/stable/language/builtins.html#builtins-filter) (available as `lib.lists.filter`),
 344     which can be used instead when the index isn't needed.
 345
 346     # Inputs
 347
 348     `ipred`
 349
 350     : The predicate function, it takes two arguments:
 351       - 1. (int): the index of the element.
 352       - 2. (a): the value of the element.
 353
 354       It must return `true`/`false` to include/exclude a given element from the result.
 355
 356     `list`
 357
 358     : The list to filter using the predicate.
 359
 360     # Type
 361     ```
 362     ifilter0 :: (int -> a -> bool) -> [a] -> [a]
 363     ```
 364
 365     # Examples
 366     :::{.example}
 367     ## `lib.lists.ifilter0` usage example
 368
 369     ```nix
 370     ifilter0 (i: v: i == 0 || v > 2) [ 1 2 3 ]
 371     => [ 1 3 ]
 372     ```
 373     :::
 374   */
 375   ifilter0 =
 376     ipred:
 377     input:
 378     map (idx: elemAt input idx) (
 379       filter (idx: ipred idx (elemAt input idx)) (
 380         genList (x: x) (length input)
 381       )
 382     );
 383
 384   /**
 385     Map and concatenate the result.
 386
 387     # Type
 388
 389     ```
 390     concatMap :: (a -> [b]) -> [a] -> [b]
 391     ```
 392
 393     # Examples
 394     :::{.example}
 395     ## `lib.lists.concatMap` usage example
 396
 397     ```nix
 398     concatMap (x: [x] ++ ["z"]) ["a" "b"]
 399     => [ "a" "z" "b" "z" ]
 400     ```
 401
 402     :::
 403   */
 404   concatMap = builtins.concatMap;
 405
 406   /**
 407     Flatten the argument into a single list; that is, nested lists are
 408     spliced into the top-level lists.
 409
 410
 411     # Inputs
 412
 413     `x`
 414
 415     : 1\. Function argument
 416
 417
 418     # Examples
 419     :::{.example}
 420     ## `lib.lists.flatten` usage example
 421
 422     ```nix
 423     flatten [1 [2 [3] 4] 5]
 424     => [1 2 3 4 5]
 425     flatten 1
 426     => [1]
 427     ```
 428
 429     :::
 430   */
 431   flatten = x:
 432     if isList x
 433     then concatMap (y: flatten y) x
 434     else [x];
 435
 436   /**
 437     Remove elements equal to 'e' from a list.  Useful for buildInputs.
 438
 439
 440     # Inputs
 441
 442     `e`
 443
 444     : Element to remove from `list`
 445
 446     `list`
 447
 448     : The list
 449
 450     # Type
 451
 452     ```
 453     remove :: a -> [a] -> [a]
 454     ```
 455
 456     # Examples
 457     :::{.example}
 458     ## `lib.lists.remove` usage example
 459
 460     ```nix
 461     remove 3 [ 1 3 4 3 ]
 462     => [ 1 4 ]
 463     ```
 464
 465     :::
 466   */
 467   remove =
 468     e: filter (x: x != e);
 469
 470   /**
 471     Find the sole element in the list matching the specified
 472     predicate.
 473
 474     Returns `default` if no such element exists, or
 475     `multiple` if there are multiple matching elements.
 476
 477
 478     # Inputs
 479
 480     `pred`
 481
 482     : Predicate
 483
 484     `default`
 485
 486     : Default value to return if element was not found.
 487
 488     `multiple`
 489
 490     : Default value to return if more than one element was found
 491
 492     `list`
 493
 494     : Input list
 495
 496     # Type
 497
 498     ```
 499     findSingle :: (a -> bool) -> a -> a -> [a] -> a
 500     ```
 501
 502     # Examples
 503     :::{.example}
 504     ## `lib.lists.findSingle` usage example
 505
 506     ```nix
 507     findSingle (x: x == 3) "none" "multiple" [ 1 3 3 ]
 508     => "multiple"
 509     findSingle (x: x == 3) "none" "multiple" [ 1 3 ]
 510     => 3
 511     findSingle (x: x == 3) "none" "multiple" [ 1 9 ]
 512     => "none"
 513     ```
 514
 515     :::
 516   */
 517   findSingle =
 518     pred:
 519     default:
 520     multiple:
 521     list:
 522     let found = filter pred list; len = length found;
 523     in if len == 0 then default
 524       else if len != 1 then multiple
 525       else head found;
 526
 527   /**
 528     Find the first index in the list matching the specified
 529     predicate or return `default` if no such element exists.
 530
 531     # Inputs
 532
 533     `pred`
 534
 535     : Predicate
 536
 537     `default`
 538
 539     : Default value to return
 540
 541     `list`
 542
 543     : Input list
 544
 545     # Type
 546
 547     ```
 548     findFirstIndex :: (a -> Bool) -> b -> [a] -> (Int | b)
 549     ```
 550
 551     # Examples
 552     :::{.example}
 553     ## `lib.lists.findFirstIndex` usage example
 554
 555     ```nix
 556     findFirstIndex (x: x > 3) null [ 0 6 4 ]
 557     => 1
 558     findFirstIndex (x: x > 9) null [ 0 6 4 ]
 559     => null
 560     ```
 561
 562     :::
 563   */
 564   findFirstIndex =
 565     pred:
 566     default:
 567     list:
 568     let
 569       # A naive recursive implementation would be much simpler, but
 570       # would also overflow the evaluator stack. We use `foldl'` as a workaround
 571       # because it reuses the same stack space, evaluating the function for one
 572       # element after another. We can't return early, so this means that we
 573       # sacrifice early cutoff, but that appears to be an acceptable cost. A
 574       # clever scheme with "exponential search" is possible, but appears over-
 575       # engineered for now. See https://github.com/NixOS/nixpkgs/pull/235267
 576
 577       # Invariant:
 578       # - if index < 0 then el == elemAt list (- index - 1) and all elements before el didn't satisfy pred
 579       # - if index >= 0 then pred (elemAt list index) and all elements before (elemAt list index) didn't satisfy pred
 580       #
 581       # We start with index -1 and the 0'th element of the list, which satisfies the invariant
 582       resultIndex = foldl' (index: el:
 583         if index < 0 then
 584           # No match yet before the current index, we need to check the element
 585           if pred el then
 586             # We have a match! Turn it into the actual index to prevent future iterations from modifying it
 587             - index - 1
 588           else
 589             # Still no match, update the index to the next element (we're counting down, so minus one)
 590             index - 1
 591         else
 592           # There's already a match, propagate the index without evaluating anything
 593           index
 594       ) (-1) list;
 595     in
 596     if resultIndex < 0 then
 597       default
 598     else
 599       resultIndex;
 600
 601   /**
 602     Find the first element in the list matching the specified
 603     predicate or return `default` if no such element exists.
 604
 605     # Inputs
 606
 607     `pred`
 608
 609     : Predicate
 610
 611     `default`
 612
 613     : Default value to return
 614
 615     `list`
 616
 617     : Input list
 618
 619     # Type
 620
 621     ```
 622     findFirst :: (a -> bool) -> a -> [a] -> a
 623     ```
 624
 625     # Examples
 626     :::{.example}
 627     ## `lib.lists.findFirst` usage example
 628
 629     ```nix
 630     findFirst (x: x > 3) 7 [ 1 6 4 ]
 631     => 6
 632     findFirst (x: x > 9) 7 [ 1 6 4 ]
 633     => 7
 634     ```
 635
 636     :::
 637   */
 638   findFirst =
 639     pred:
 640     default:
 641     list:
 642     let
 643       index = findFirstIndex pred null list;
 644     in
 645     if index == null then
 646       default
 647     else
 648       elemAt list index;
 649
 650   /**
 651     Return true if function `pred` returns true for at least one
 652     element of `list`.
 653
 654     # Inputs
 655
 656     `pred`
 657
 658     : Predicate
 659
 660     `list`
 661
 662     : Input list
 663
 664     # Type
 665
 666     ```
 667     any :: (a -> bool) -> [a] -> bool
 668     ```
 669
 670     # Examples
 671     :::{.example}
 672     ## `lib.lists.any` usage example
 673
 674     ```nix
 675     any isString [ 1 "a" { } ]
 676     => true
 677     any isString [ 1 { } ]
 678     => false
 679     ```
 680
 681     :::
 682   */
 683   any = builtins.any;
 684
 685   /**
 686     Return true if function `pred` returns true for all elements of
 687     `list`.
 688
 689     # Inputs
 690
 691     `pred`
 692
 693     : Predicate
 694
 695     `list`
 696
 697     : Input list
 698
 699     # Type
 700
 701     ```
 702     all :: (a -> bool) -> [a] -> bool
 703     ```
 704
 705     # Examples
 706     :::{.example}
 707     ## `lib.lists.all` usage example
 708
 709     ```nix
 710     all (x: x < 3) [ 1 2 ]
 711     => true
 712     all (x: x < 3) [ 1 2 3 ]
 713     => false
 714     ```
 715
 716     :::
 717   */
 718   all = builtins.all;
 719
 720   /**
 721     Count how many elements of `list` match the supplied predicate
 722     function.
 723
 724     # Inputs
 725
 726     `pred`
 727
 728     : Predicate
 729
 730     # Type
 731
 732     ```
 733     count :: (a -> bool) -> [a] -> int
 734     ```
 735
 736     # Examples
 737     :::{.example}
 738     ## `lib.lists.count` usage example
 739
 740     ```nix
 741     count (x: x == 3) [ 3 2 3 4 6 ]
 742     => 2
 743     ```
 744
 745     :::
 746   */
 747   count =
 748     pred: foldl' (c: x: if pred x then c + 1 else c) 0;
 749
 750   /**
 751     Return a singleton list or an empty list, depending on a boolean
 752     value.  Useful when building lists with optional elements
 753     (e.g. `++ optional (system == "i686-linux") firefox`).
 754
 755     # Inputs
 756
 757     `cond`
 758
 759     : 1\. Function argument
 760
 761     `elem`
 762
 763     : 2\. Function argument
 764
 765     # Type
 766
 767     ```
 768     optional :: bool -> a -> [a]
 769     ```
 770
 771     # Examples
 772     :::{.example}
 773     ## `lib.lists.optional` usage example
 774
 775     ```nix
 776     optional true "foo"
 777     => [ "foo" ]
 778     optional false "foo"
 779     => [ ]
 780     ```
 781
 782     :::
 783   */
 784   optional = cond: elem: if cond then [elem] else [];
 785
 786   /**
 787     Return a list or an empty list, depending on a boolean value.
 788
 789     # Inputs
 790
 791     `cond`
 792
 793     : Condition
 794
 795     `elems`
 796
 797     : List to return if condition is true
 798
 799     # Type
 800
 801     ```
 802     optionals :: bool -> [a] -> [a]
 803     ```
 804
 805     # Examples
 806     :::{.example}
 807     ## `lib.lists.optionals` usage example
 808
 809     ```nix
 810     optionals true [ 2 3 ]
 811     => [ 2 3 ]
 812     optionals false [ 2 3 ]
 813     => [ ]
 814     ```
 815
 816     :::
 817   */
 818   optionals =
 819     cond:
 820     elems: if cond then elems else [];
 821
 822
 823   /**
 824     If argument is a list, return it; else, wrap it in a singleton
 825     list. If you're using this, you should almost certainly
 826     reconsider if there isn't a more "well-typed" approach.
 827
 828     # Inputs
 829
 830     `x`
 831
 832     : 1\. Function argument
 833
 834     # Examples
 835     :::{.example}
 836     ## `lib.lists.toList` usage example
 837
 838     ```nix
 839     toList [ 1 2 ]
 840     => [ 1 2 ]
 841     toList "hi"
 842     => [ "hi "]
 843     ```
 844
 845     :::
 846   */
 847   toList = x: if isList x then x else [x];
 848
 849   /**
 850     Return a list of integers from `first` up to and including `last`.
 851
 852     # Inputs
 853
 854     `first`
 855
 856     : First integer in the range
 857
 858     `last`
 859
 860     : Last integer in the range
 861
 862     # Type
 863
 864     ```
 865     range :: int -> int -> [int]
 866     ```
 867
 868     # Examples
 869     :::{.example}
 870     ## `lib.lists.range` usage example
 871
 872     ```nix
 873     range 2 4
 874     => [ 2 3 4 ]
 875     range 3 2
 876     => [ ]
 877     ```
 878
 879     :::
 880   */
 881   range =
 882     first:
 883     last:
 884     if first > last then
 885       []
 886     else
 887       genList (n: first + n) (last - first + 1);
 888
 889   /**
 890     Return a list with `n` copies of an element.
 891
 892     # Inputs
 893
 894     `n`
 895
 896     : 1\. Function argument
 897
 898     `elem`
 899
 900     : 2\. Function argument
 901
 902     # Type
 903
 904     ```
 905     replicate :: int -> a -> [a]
 906     ```
 907
 908     # Examples
 909     :::{.example}
 910     ## `lib.lists.replicate` usage example
 911
 912     ```nix
 913     replicate 3 "a"
 914     => [ "a" "a" "a" ]
 915     replicate 2 true
 916     => [ true true ]
 917     ```
 918
 919     :::
 920   */
 921   replicate = n: elem: genList (_: elem) n;
 922
 923   /**
 924     Splits the elements of a list in two lists, `right` and
 925     `wrong`, depending on the evaluation of a predicate.
 926
 927     # Inputs
 928
 929     `pred`
 930
 931     : Predicate
 932
 933     `list`
 934
 935     : Input list
 936
 937     # Type
 938
 939     ```
 940     (a -> bool) -> [a] -> { right :: [a]; wrong :: [a]; }
 941     ```
 942
 943     # Examples
 944     :::{.example}
 945     ## `lib.lists.partition` usage example
 946
 947     ```nix
 948     partition (x: x > 2) [ 5 1 2 3 4 ]
 949     => { right = [ 5 3 4 ]; wrong = [ 1 2 ]; }
 950     ```
 951
 952     :::
 953   */
 954   partition = builtins.partition;
 955
 956   /**
 957     Splits the elements of a list into many lists, using the return value of a predicate.
 958     Predicate should return a string which becomes keys of attrset `groupBy` returns.
 959     `groupBy'` allows to customise the combining function and initial value
 960
 961     # Inputs
 962
 963     `op`
 964
 965     : 1\. Function argument
 966
 967     `nul`
 968
 969     : 2\. Function argument
 970
 971     `pred`
 972
 973     : 3\. Function argument
 974
 975     `lst`
 976
 977     : 4\. Function argument
 978
 979
 980     # Examples
 981     :::{.example}
 982     ## `lib.lists.groupBy'` usage example
 983
 984     ```nix
 985     groupBy (x: boolToString (x > 2)) [ 5 1 2 3 4 ]
 986     => { true = [ 5 3 4 ]; false = [ 1 2 ]; }
 987     groupBy (x: x.name) [ {name = "icewm"; script = "icewm &";}
 988                           {name = "xfce";  script = "xfce4-session &";}
 989                           {name = "icewm"; script = "icewmbg &";}
 990                           {name = "mate";  script = "gnome-session &";}
 991                         ]
 992     => { icewm = [ { name = "icewm"; script = "icewm &"; }
 993                    { name = "icewm"; script = "icewmbg &"; } ];
 994          mate  = [ { name = "mate";  script = "gnome-session &"; } ];
 995          xfce  = [ { name = "xfce";  script = "xfce4-session &"; } ];
 996        }
 997
 998     groupBy' builtins.add 0 (x: boolToString (x > 2)) [ 5 1 2 3 4 ]
 999     => { true = 12; false = 3; }
1000     ```
1001
1002     :::
1003   */
1004   groupBy' = op: nul: pred: lst: mapAttrs (name: foldl op nul) (groupBy pred lst);
1005
1006   groupBy = builtins.groupBy or (
1007     pred: foldl' (r: e:
1008        let
1009          key = pred e;
1010        in
1011          r // { ${key} = (r.${key} or []) ++ [e]; }
1012     ) {});
1013
1014   /**
1015     Merges two lists of the same size together. If the sizes aren't the same
1016     the merging stops at the shortest. How both lists are merged is defined
1017     by the first argument.
1018
1019     # Inputs
1020
1021     `f`
1022
1023     : Function to zip elements of both lists
1024
1025     `fst`
1026
1027     : First list
1028
1029     `snd`
1030
1031     : Second list
1032
1033     # Type
1034
1035     ```
1036     zipListsWith :: (a -> b -> c) -> [a] -> [b] -> [c]
1037     ```
1038
1039     # Examples
1040     :::{.example}
1041     ## `lib.lists.zipListsWith` usage example
1042
1043     ```nix
1044     zipListsWith (a: b: a + b) ["h" "l"] ["e" "o"]
1045     => ["he" "lo"]
1046     ```
1047
1048     :::
1049   */
1050   zipListsWith =
1051     f:
1052     fst:
1053     snd:
1054     genList
1055       (n: f (elemAt fst n) (elemAt snd n)) (min (length fst) (length snd));
1056
1057   /**
1058     Merges two lists of the same size together. If the sizes aren't the same
1059     the merging stops at the shortest.
1060
1061     # Inputs
1062
1063     `fst`
1064
1065     : First list
1066
1067     `snd`
1068
1069     : Second list
1070
1071     # Type
1072
1073     ```
1074     zipLists :: [a] -> [b] -> [{ fst :: a; snd :: b; }]
1075     ```
1076
1077     # Examples
1078     :::{.example}
1079     ## `lib.lists.zipLists` usage example
1080
1081     ```nix
1082     zipLists [ 1 2 ] [ "a" "b" ]
1083     => [ { fst = 1; snd = "a"; } { fst = 2; snd = "b"; } ]
1084     ```
1085
1086     :::
1087   */
1088   zipLists = zipListsWith (fst: snd: { inherit fst snd; });
1089
1090   /**
1091     Reverse the order of the elements of a list.
1092
1093     # Inputs
1094
1095     `xs`
1096
1097     : 1\. Function argument
1098
1099     # Type
1100
1101     ```
1102     reverseList :: [a] -> [a]
1103     ```
1104
1105     # Examples
1106     :::{.example}
1107     ## `lib.lists.reverseList` usage example
1108
1109     ```nix
1110     reverseList [ "b" "o" "j" ]
1111     => [ "j" "o" "b" ]
1112     ```
1113
1114     :::
1115   */
1116   reverseList = xs:
1117     let l = length xs; in genList (n: elemAt xs (l - n - 1)) l;
1118
1119   /**
1120     Depth-First Search (DFS) for lists `list != []`.
1121
1122     `before a b == true` means that `b` depends on `a` (there's an
1123     edge from `b` to `a`).
1124
1125
1126     # Inputs
1127
1128     `stopOnCycles`
1129
1130     : 1\. Function argument
1131
1132     `before`
1133
1134     : 2\. Function argument
1135
1136     `list`
1137
1138     : 3\. Function argument
1139
1140
1141     # Examples
1142     :::{.example}
1143     ## `lib.lists.listDfs` usage example
1144
1145     ```nix
1146     listDfs true hasPrefix [ "/home/user" "other" "/" "/home" ]
1147       == { minimal = "/";                  # minimal element
1148            visited = [ "/home/user" ];     # seen elements (in reverse order)
1149            rest    = [ "/home" "other" ];  # everything else
1150          }
1151
1152     listDfs true hasPrefix [ "/home/user" "other" "/" "/home" "/" ]
1153       == { cycle   = "/";                  # cycle encountered at this element
1154            loops   = [ "/" ];              # and continues to these elements
1155            visited = [ "/" "/home/user" ]; # elements leading to the cycle (in reverse order)
1156            rest    = [ "/home" "other" ];  # everything else
1157     ```
1158
1159     :::
1160   */
1161   listDfs = stopOnCycles: before: list:
1162     let
1163       dfs' = us: visited: rest:
1164         let
1165           c = filter (x: before x us) visited;
1166           b = partition (x: before x us) rest;
1167         in if stopOnCycles && (length c > 0)
1168            then { cycle = us; loops = c; inherit visited rest; }
1169            else if length b.right == 0
1170                 then # nothing is before us
1171                      { minimal = us; inherit visited rest; }
1172                 else # grab the first one before us and continue
1173                      dfs' (head b.right)
1174                           ([ us ] ++ visited)
1175                           (tail b.right ++ b.wrong);
1176     in dfs' (head list) [] (tail list);
1177
1178   /**
1179     Sort a list based on a partial ordering using DFS. This
1180     implementation is O(N^2), if your ordering is linear, use `sort`
1181     instead.
1182
1183     `before a b == true` means that `b` should be after `a`
1184     in the result.
1185
1186
1187     # Inputs
1188
1189     `before`
1190
1191     : 1\. Function argument
1192
1193     `list`
1194
1195     : 2\. Function argument
1196
1197
1198     # Examples
1199     :::{.example}
1200     ## `lib.lists.toposort` usage example
1201
1202     ```nix
1203     toposort hasPrefix [ "/home/user" "other" "/" "/home" ]
1204       == { result = [ "/" "/home" "/home/user" "other" ]; }
1205
1206     toposort hasPrefix [ "/home/user" "other" "/" "/home" "/" ]
1207       == { cycle = [ "/home/user" "/" "/" ]; # path leading to a cycle
1208            loops = [ "/" ]; }                # loops back to these elements
1209
1210     toposort hasPrefix [ "other" "/home/user" "/home" "/" ]
1211       == { result = [ "other" "/" "/home" "/home/user" ]; }
1212
1213     toposort (a: b: a < b) [ 3 2 1 ] == { result = [ 1 2 3 ]; }
1214     ```
1215
1216     :::
1217   */
1218   toposort = before: list:
1219     let
1220       dfsthis = listDfs true before list;
1221       toporest = toposort before (dfsthis.visited ++ dfsthis.rest);
1222     in
1223       if length list < 2
1224       then # finish
1225            { result =  list; }
1226       else if dfsthis ? cycle
1227            then # there's a cycle, starting from the current vertex, return it
1228                 { cycle = reverseList ([ dfsthis.cycle ] ++ dfsthis.visited);
1229                   inherit (dfsthis) loops; }
1230            else if toporest ? cycle
1231                 then # there's a cycle somewhere else in the graph, return it
1232                      toporest
1233                 # Slow, but short. Can be made a bit faster with an explicit stack.
1234                 else # there are no cycles
1235                      { result = [ dfsthis.minimal ] ++ toporest.result; };
1236
1237   /**
1238     Sort a list based on a comparator function which compares two
1239     elements and returns true if the first argument is strictly below
1240     the second argument.  The returned list is sorted in an increasing
1241     order.  The implementation does a quick-sort.
1242
1243     See also [`sortOn`](#function-library-lib.lists.sortOn), which applies the
1244     default comparison on a function-derived property, and may be more efficient.
1245
1246     # Inputs
1247
1248     `comparator`
1249
1250     : 1\. Function argument
1251
1252     `list`
1253
1254     : 2\. Function argument
1255
1256     # Type
1257
1258     ```
1259     sort :: (a -> a -> Bool) -> [a] -> [a]
1260     ```
1261
1262     # Examples
1263     :::{.example}
1264     ## `lib.lists.sort` usage example
1265
1266     ```nix
1267     sort (p: q: p < q) [ 5 3 7 ]
1268     => [ 3 5 7 ]
1269     ```
1270
1271     :::
1272   */
1273   sort = builtins.sort;
1274
1275   /**
1276     Sort a list based on the default comparison of a derived property `b`.
1277
1278     The items are returned in `b`-increasing order.
1279
1280     **Performance**:
1281
1282     The passed function `f` is only evaluated once per item,
1283     unlike an unprepared [`sort`](#function-library-lib.lists.sort) using
1284     `f p < f q`.
1285
1286     **Laws**:
1287     ```nix
1288     sortOn f == sort (p: q: f p < f q)
1289     ```
1290
1291
1292     # Inputs
1293
1294     `f`
1295
1296     : 1\. Function argument
1297
1298     `list`
1299
1300     : 2\. Function argument
1301
1302     # Type
1303
1304     ```
1305     sortOn :: (a -> b) -> [a] -> [a], for comparable b
1306     ```
1307
1308     # Examples
1309     :::{.example}
1310     ## `lib.lists.sortOn` usage example
1311
1312     ```nix
1313     sortOn stringLength [ "aa" "b" "cccc" ]
1314     => [ "b" "aa" "cccc" ]
1315     ```
1316
1317     :::
1318   */
1319   sortOn = f: list:
1320     let
1321       # Heterogenous list as pair may be ugly, but requires minimal allocations.
1322       pairs = map (x: [(f x) x]) list;
1323     in
1324       map
1325         (x: builtins.elemAt x 1)
1326         (sort
1327           # Compare the first element of the pairs
1328           # Do not factor out the `<`, to avoid calls in hot code; duplicate instead.
1329           (a: b: head a < head b)
1330           pairs);
1331
1332   /**
1333     Compare two lists element-by-element.
1334
1335     # Inputs
1336
1337     `cmp`
1338
1339     : 1\. Function argument
1340
1341     `a`
1342
1343     : 2\. Function argument
1344
1345     `b`
1346
1347     : 3\. Function argument
1348
1349
1350     # Examples
1351     :::{.example}
1352     ## `lib.lists.compareLists` usage example
1353
1354     ```nix
1355     compareLists compare [] []
1356     => 0
1357     compareLists compare [] [ "a" ]
1358     => -1
1359     compareLists compare [ "a" ] []
1360     => 1
1361     compareLists compare [ "a" "b" ] [ "a" "c" ]
1362     => -1
1363     ```
1364
1365     :::
1366   */
1367   compareLists = cmp: a: b:
1368     if a == []
1369     then if b == []
1370          then 0
1371          else -1
1372     else if b == []
1373          then 1
1374          else let rel = cmp (head a) (head b); in
1375               if rel == 0
1376               then compareLists cmp (tail a) (tail b)
1377               else rel;
1378
1379   /**
1380     Sort list using "Natural sorting".
1381     Numeric portions of strings are sorted in numeric order.
1382
1383
1384     # Inputs
1385
1386     `lst`
1387
1388     : 1\. Function argument
1389
1390
1391     # Examples
1392     :::{.example}
1393     ## `lib.lists.naturalSort` usage example
1394
1395     ```nix
1396     naturalSort ["disk11" "disk8" "disk100" "disk9"]
1397     => ["disk8" "disk9" "disk11" "disk100"]
1398     naturalSort ["10.46.133.149" "10.5.16.62" "10.54.16.25"]
1399     => ["10.5.16.62" "10.46.133.149" "10.54.16.25"]
1400     naturalSort ["v0.2" "v0.15" "v0.0.9"]
1401     => [ "v0.0.9" "v0.2" "v0.15" ]
1402     ```
1403
1404     :::
1405   */
1406   naturalSort = lst:
1407     let
1408       vectorise = s: map (x: if isList x then toInt (head x) else x) (builtins.split "(0|[1-9][0-9]*)" s);
1409       prepared = map (x: [ (vectorise x) x ]) lst; # remember vectorised version for O(n) regex splits
1410       less = a: b: (compareLists compare (head a) (head b)) < 0;
1411     in
1412       map (x: elemAt x 1) (sort less prepared);
1413
1414   /**
1415     Return the first (at most) N elements of a list.
1416
1417
1418     # Inputs
1419
1420     `count`
1421
1422     : Number of elements to take
1423
1424     `list`
1425
1426     : Input list
1427
1428     # Type
1429
1430     ```
1431     take :: int -> [a] -> [a]
1432     ```
1433
1434     # Examples
1435     :::{.example}
1436     ## `lib.lists.take` usage example
1437
1438     ```nix
1439     take 2 [ "a" "b" "c" "d" ]
1440     => [ "a" "b" ]
1441     take 2 [ ]
1442     => [ ]
1443     ```
1444
1445     :::
1446   */
1447   take =
1448     count: sublist 0 count;
1449
1450   /**
1451     Remove the first (at most) N elements of a list.
1452
1453
1454     # Inputs
1455
1456     `count`
1457
1458     : Number of elements to drop
1459
1460     `list`
1461
1462     : Input list
1463
1464     # Type
1465
1466     ```
1467     drop :: int -> [a] -> [a]
1468     ```
1469
1470     # Examples
1471     :::{.example}
1472     ## `lib.lists.drop` usage example
1473
1474     ```nix
1475     drop 2 [ "a" "b" "c" "d" ]
1476     => [ "c" "d" ]
1477     drop 2 [ ]
1478     => [ ]
1479     ```
1480
1481     :::
1482   */
1483   drop =
1484     count:
1485     list: sublist count (length list) list;
1486
1487   /**
1488     Whether the first list is a prefix of the second list.
1489
1490
1491     # Inputs
1492
1493     `list1`
1494
1495     : 1\. Function argument
1496
1497     `list2`
1498
1499     : 2\. Function argument
1500
1501     # Type
1502
1503     ```
1504     hasPrefix :: [a] -> [a] -> bool
1505     ```
1506
1507     # Examples
1508     :::{.example}
1509     ## `lib.lists.hasPrefix` usage example
1510
1511     ```nix
1512     hasPrefix [ 1 2 ] [ 1 2 3 4 ]
1513     => true
1514     hasPrefix [ 0 1 ] [ 1 2 3 4 ]
1515     => false
1516     ```
1517
1518     :::
1519   */
1520   hasPrefix =
1521     list1:
1522     list2:
1523     take (length list1) list2 == list1;
1524
1525   /**
1526     Remove the first list as a prefix from the second list.
1527     Error if the first list isn't a prefix of the second list.
1528
1529     # Inputs
1530
1531     `list1`
1532
1533     : 1\. Function argument
1534
1535     `list2`
1536
1537     : 2\. Function argument
1538
1539     # Type
1540
1541     ```
1542     removePrefix :: [a] -> [a] -> [a]
1543     ```
1544
1545     # Examples
1546     :::{.example}
1547     ## `lib.lists.removePrefix` usage example
1548
1549     ```nix
1550     removePrefix [ 1 2 ] [ 1 2 3 4 ]
1551     => [ 3 4 ]
1552     removePrefix [ 0 1 ] [ 1 2 3 4 ]
1553     => <error>
1554     ```
1555
1556     :::
1557   */
1558   removePrefix =
1559     list1:
1560     list2:
1561     if hasPrefix list1 list2 then
1562       drop (length list1) list2
1563     else
1564       throw "lib.lists.removePrefix: First argument is not a list prefix of the second argument";
1565
1566   /**
1567     Return a list consisting of at most `count` elements of `list`,
1568     starting at index `start`.
1569
1570     # Inputs
1571
1572     `start`
1573
1574     : Index at which to start the sublist
1575
1576     `count`
1577
1578     : Number of elements to take
1579
1580     `list`
1581
1582     : Input list
1583
1584     # Type
1585
1586     ```
1587     sublist :: int -> int -> [a] -> [a]
1588     ```
1589
1590     # Examples
1591     :::{.example}
1592     ## `lib.lists.sublist` usage example
1593
1594     ```nix
1595     sublist 1 3 [ "a" "b" "c" "d" "e" ]
1596     => [ "b" "c" "d" ]
1597     sublist 1 3 [ ]
1598     => [ ]
1599     ```
1600
1601     :::
1602   */
1603   sublist =
1604     start:
1605     count:
1606     list:
1607     let len = length list; in
1608     genList
1609       (n: elemAt list (n + start))
1610       (if start >= len then 0
1611        else if start + count > len then len - start
1612        else count);
1613
1614   /**
1615     The common prefix of two lists.
1616
1617
1618     # Inputs
1619
1620     `list1`
1621
1622     : 1\. Function argument
1623
1624     `list2`
1625
1626     : 2\. Function argument
1627
1628     # Type
1629
1630     ```
1631     commonPrefix :: [a] -> [a] -> [a]
1632     ```
1633
1634     # Examples
1635     :::{.example}
1636     ## `lib.lists.commonPrefix` usage example
1637
1638     ```nix
1639     commonPrefix [ 1 2 3 4 5 6 ] [ 1 2 4 8 ]
1640     => [ 1 2 ]
1641     commonPrefix [ 1 2 3 ] [ 1 2 3 4 5 ]
1642     => [ 1 2 3 ]
1643     commonPrefix [ 1 2 3 ] [ 4 5 6 ]
1644     => [ ]
1645     ```
1646
1647     :::
1648   */
1649   commonPrefix =
1650     list1:
1651     list2:
1652     let
1653       # Zip the lists together into a list of booleans whether each element matches
1654       matchings = zipListsWith (fst: snd: fst != snd) list1 list2;
1655       # Find the first index where the elements don't match,
1656       # which will then also be the length of the common prefix.
1657       # If all elements match, we fall back to the length of the zipped list,
1658       # which is the same as the length of the smaller list.
1659       commonPrefixLength = findFirstIndex id (length matchings) matchings;
1660     in
1661     take commonPrefixLength list1;
1662
1663   /**
1664     Return the last element of a list.
1665
1666     This function throws an error if the list is empty.
1667
1668
1669     # Inputs
1670
1671     `list`
1672
1673     : 1\. Function argument
1674
1675     # Type
1676
1677     ```
1678     last :: [a] -> a
1679     ```
1680
1681     # Examples
1682     :::{.example}
1683     ## `lib.lists.last` usage example
1684
1685     ```nix
1686     last [ 1 2 3 ]
1687     => 3
1688     ```
1689
1690     :::
1691   */
1692   last = list:
1693     assert lib.assertMsg (list != []) "lists.last: list must not be empty!";
1694     elemAt list (length list - 1);
1695
1696   /**
1697     Return all elements but the last.
1698
1699     This function throws an error if the list is empty.
1700
1701
1702     # Inputs
1703
1704     `list`
1705
1706     : 1\. Function argument
1707
1708     # Type
1709
1710     ```
1711     init :: [a] -> [a]
1712     ```
1713
1714     # Examples
1715     :::{.example}
1716     ## `lib.lists.init` usage example
1717
1718     ```nix
1719     init [ 1 2 3 ]
1720     => [ 1 2 ]
1721     ```
1722
1723     :::
1724   */
1725   init = list:
1726     assert lib.assertMsg (list != []) "lists.init: list must not be empty!";
1727     take (length list - 1) list;
1728
1729
1730   /**
1731     Return the image of the cross product of some lists by a function.
1732
1733
1734     # Examples
1735     :::{.example}
1736     ## `lib.lists.crossLists` usage example
1737
1738     ```nix
1739     crossLists (x: y: "${toString x}${toString y}") [[1 2] [3 4]]
1740     => [ "13" "14" "23" "24" ]
1741     ```
1742
1743     The following function call is equivalent to the one deprecated above:
1744
1745     ```nix
1746     mapCartesianProduct (x: "${toString x.a}${toString x.b}") { a = [1 2]; b = [3 4]; }
1747     => [ "13" "14" "23" "24" ]
1748     ```
1749     :::
1750   */
1751   crossLists = warn
1752     ''lib.crossLists is deprecated, use lib.mapCartesianProduct instead.
1753
1754     For example, the following function call:
1755
1756     nix-repl> lib.crossLists (x: y: x+y) [[1 2] [3 4]]
1757     [ 4 5 5 6 ]
1758
1759     Can now be replaced by the following one:
1760
1761     nix-repl> lib.mapCartesianProduct ({x,y}: x+y) { x = [1 2]; y = [3 4]; }
1762     [ 4 5 5 6 ]
1763     ''
1764     (f: foldl (fs: args: concatMap (f: map f args) fs) [f]);
1765
1766   /**
1767     Remove duplicate elements from the `list`. O(n^2) complexity.
1768
1769
1770     # Inputs
1771
1772     `list`
1773
1774     : Input list
1775
1776     # Type
1777
1778     ```
1779     unique :: [a] -> [a]
1780     ```
1781
1782     # Examples
1783     :::{.example}
1784     ## `lib.lists.unique` usage example
1785
1786     ```nix
1787     unique [ 3 2 3 4 ]
1788     => [ 3 2 4 ]
1789     ```
1790
1791     :::
1792   */
1793   unique = foldl' (acc: e: if elem e acc then acc else acc ++ [ e ]) [];
1794
1795   /**
1796     Check if list contains only unique elements. O(n^2) complexity.
1797
1798
1799     # Inputs
1800
1801     `list`
1802
1803     : 1\. Function argument
1804
1805     # Type
1806
1807     ```
1808     allUnique :: [a] -> bool
1809     ```
1810
1811     # Examples
1812     :::{.example}
1813     ## `lib.lists.allUnique` usage example
1814
1815     ```nix
1816     allUnique [ 3 2 3 4 ]
1817     => false
1818     allUnique [ 3 2 4 1 ]
1819     => true
1820     ```
1821
1822     :::
1823   */
1824   allUnique = list: (length (unique list) == length list);
1825
1826
1827   /**
1828     Intersects list 'list1' and another list (`list2`).
1829
1830     O(nm) complexity.
1831
1832     # Inputs
1833
1834     `list1`
1835
1836     : First list
1837
1838     `list2`
1839
1840     : Second list
1841
1842
1843     # Examples
1844     :::{.example}
1845     ## `lib.lists.intersectLists` usage example
1846
1847     ```nix
1848     intersectLists [ 1 2 3 ] [ 6 3 2 ]
1849     => [ 3 2 ]
1850     ```
1851
1852     :::
1853   */
1854   intersectLists = e: filter (x: elem x e);
1855
1856   /**
1857     Subtracts list 'e' from another list (`list2`).
1858
1859     O(nm) complexity.
1860
1861     # Inputs
1862
1863     `e`
1864
1865     : First list
1866
1867     `list2`
1868
1869     : Second list
1870
1871
1872     # Examples
1873     :::{.example}
1874     ## `lib.lists.subtractLists` usage example
1875
1876     ```nix
1877     subtractLists [ 3 2 ] [ 1 2 3 4 5 3 ]
1878     => [ 1 4 5 ]
1879     ```
1880
1881     :::
1882   */
1883   subtractLists = e: filter (x: !(elem x e));
1884
1885   /**
1886     Test if two lists have no common element.
1887     It should be slightly more efficient than (intersectLists a b == [])
1888
1889     # Inputs
1890
1891     `a`
1892
1893     : 1\. Function argument
1894
1895     `b`
1896
1897     : 2\. Function argument
1898   */
1899   mutuallyExclusive = a: b: length a == 0 || !(any (x: elem x a) b);
1900
1901 }