lib/lists.nix

   1 /* General list operations. */
   2 { lib }:
   3 let
   4   inherit (lib.strings) toInt;
   5   inherit (lib.trivial) compare min id;
   6   inherit (lib.attrsets) mapAttrs;
   7 in
   8 rec {
   9
  10   inherit (builtins) head tail length isList elemAt concatLists filter elem genList map;
  11
  12   /*  Create a list consisting of a single element.  `singleton x` is
  13       sometimes more convenient with respect to indentation than `[x]`
  14       when x spans multiple lines.
  15
  16       Type: singleton :: a -> [a]
  17
  18       Example:
  19         singleton "foo"
  20         => [ "foo" ]
  21   */
  22   singleton = x: [x];
  23
  24   /*  Apply the function to each element in the list. Same as `map`, but arguments
  25       flipped.
  26
  27       Type: forEach :: [a] -> (a -> b) -> [b]
  28
  29       Example:
  30         forEach [ 1 2 ] (x:
  31           toString x
  32         )
  33         => [ "1" "2" ]
  34   */
  35   forEach = xs: f: map f xs;
  36
  37   /* “right fold” a binary function `op` between successive elements of
  38      `list` with `nul` as the starting value, i.e.,
  39      `foldr op nul [x_1 x_2 ... x_n] == op x_1 (op x_2 ... (op x_n nul))`.
  40
  41      Type: foldr :: (a -> b -> b) -> b -> [a] -> b
  42
  43      Example:
  44        concat = foldr (a: b: a + b) "z"
  45        concat [ "a" "b" "c" ]
  46        => "abcz"
  47        # different types
  48        strange = foldr (int: str: toString (int + 1) + str) "a"
  49        strange [ 1 2 3 4 ]
  50        => "2345a"
  51   */
  52   foldr = op: nul: list:
  53     let
  54       len = length list;
  55       fold' = n:
  56         if n == len
  57         then nul
  58         else op (elemAt list n) (fold' (n + 1));
  59     in fold' 0;
  60
  61   /* `fold` is an alias of `foldr` for historic reasons */
  62   # FIXME(Profpatsch): deprecate?
  63   fold = foldr;
  64
  65
  66   /* “left fold”, like `foldr`, but from the left:
  67      `foldl op nul [x_1 x_2 ... x_n] == op (... (op (op nul x_1) x_2) ... x_n)`.
  68
  69      Type: foldl :: (b -> a -> b) -> b -> [a] -> b
  70
  71      Example:
  72        lconcat = foldl (a: b: a + b) "z"
  73        lconcat [ "a" "b" "c" ]
  74        => "zabc"
  75        # different types
  76        lstrange = foldl (str: int: str + toString (int + 1)) "a"
  77        lstrange [ 1 2 3 4 ]
  78        => "a2345"
  79   */
  80   foldl = op: nul: list:
  81     let
  82       foldl' = n:
  83         if n == -1
  84         then nul
  85         else op (foldl' (n - 1)) (elemAt list n);
  86     in foldl' (length list - 1);
  87
  88   /*
  89     Reduce a list by applying a binary operator from left to right,
  90     starting with an initial accumulator.
  91
  92     Before each application of the operator, the accumulator value is evaluated.
  93     This behavior makes this function stricter than [`foldl`](#function-library-lib.lists.foldl).
  94
  95     Unlike [`builtins.foldl'`](https://nixos.org/manual/nix/unstable/language/builtins.html#builtins-foldl'),
  96     the initial accumulator argument is evaluated before the first iteration.
  97
  98     A call like
  99
 100     ```nix
 101     foldl' op acc₀ [ x₀ x₁ x₂ ... xₙ₋₁ xₙ ]
 102     ```
 103
 104     is (denotationally) equivalent to the following,
 105     but with the added benefit that `foldl'` itself will never overflow the stack.
 106
 107     ```nix
 108     let
 109       acc₁   = builtins.seq acc₀   (op acc₀   x₀  );
 110       acc₂   = builtins.seq acc₁   (op acc₁   x₁  );
 111       acc₃   = builtins.seq acc₂   (op acc₂   x₂  );
 112       ...
 113       accₙ   = builtins.seq accₙ₋₁ (op accₙ₋₁ xₙ₋₁);
 114       accₙ₊₁ = builtins.seq accₙ   (op accₙ   xₙ  );
 115     in
 116     accₙ₊₁
 117
 118     # Or ignoring builtins.seq
 119     op (op (... (op (op (op acc₀ x₀) x₁) x₂) ...) xₙ₋₁) xₙ
 120     ```
 121
 122     Type: foldl' :: (acc -> x -> acc) -> acc -> [x] -> acc
 123
 124     Example:
 125       foldl' (acc: x: acc + x) 0 [1 2 3]
 126       => 6
 127   */
 128   foldl' =
 129     /* The binary operation to run, where the two arguments are:
 130
 131     1. `acc`: The current accumulator value: Either the initial one for the first iteration, or the result of the previous iteration
 132     2. `x`: The corresponding list element for this iteration
 133     */
 134     op:
 135     # The initial accumulator value
 136     acc:
 137     # The list to fold
 138     list:
 139
 140     # The builtin `foldl'` is a bit lazier than one might expect.
 141     # See https://github.com/NixOS/nix/pull/7158.
 142     # In particular, the initial accumulator value is not forced before the first iteration starts.
 143     builtins.seq acc
 144       (builtins.foldl' op acc list);
 145
 146   /* Map with index starting from 0
 147
 148      Type: imap0 :: (int -> a -> b) -> [a] -> [b]
 149
 150      Example:
 151        imap0 (i: v: "${v}-${toString i}") ["a" "b"]
 152        => [ "a-0" "b-1" ]
 153   */
 154   imap0 = f: list: genList (n: f n (elemAt list n)) (length list);
 155
 156   /* Map with index starting from 1
 157
 158      Type: imap1 :: (int -> a -> b) -> [a] -> [b]
 159
 160      Example:
 161        imap1 (i: v: "${v}-${toString i}") ["a" "b"]
 162        => [ "a-1" "b-2" ]
 163   */
 164   imap1 = f: list: genList (n: f (n + 1) (elemAt list n)) (length list);
 165
 166   /* Map and concatenate the result.
 167
 168      Type: concatMap :: (a -> [b]) -> [a] -> [b]
 169
 170      Example:
 171        concatMap (x: [x] ++ ["z"]) ["a" "b"]
 172        => [ "a" "z" "b" "z" ]
 173   */
 174   concatMap = builtins.concatMap or (f: list: concatLists (map f list));
 175
 176   /* Flatten the argument into a single list; that is, nested lists are
 177      spliced into the top-level lists.
 178
 179      Example:
 180        flatten [1 [2 [3] 4] 5]
 181        => [1 2 3 4 5]
 182        flatten 1
 183        => [1]
 184   */
 185   flatten = x:
 186     if isList x
 187     then concatMap (y: flatten y) x
 188     else [x];
 189
 190   /* Remove elements equal to 'e' from a list.  Useful for buildInputs.
 191
 192      Type: remove :: a -> [a] -> [a]
 193
 194      Example:
 195        remove 3 [ 1 3 4 3 ]
 196        => [ 1 4 ]
 197   */
 198   remove =
 199     # Element to remove from the list
 200     e: filter (x: x != e);
 201
 202   /* Find the sole element in the list matching the specified
 203      predicate, returns `default` if no such element exists, or
 204      `multiple` if there are multiple matching elements.
 205
 206      Type: findSingle :: (a -> bool) -> a -> a -> [a] -> a
 207
 208      Example:
 209        findSingle (x: x == 3) "none" "multiple" [ 1 3 3 ]
 210        => "multiple"
 211        findSingle (x: x == 3) "none" "multiple" [ 1 3 ]
 212        => 3
 213        findSingle (x: x == 3) "none" "multiple" [ 1 9 ]
 214        => "none"
 215   */
 216   findSingle =
 217     # Predicate
 218     pred:
 219     # Default value to return if element was not found.
 220     default:
 221     # Default value to return if more than one element was found
 222     multiple:
 223     # Input list
 224     list:
 225     let found = filter pred list; len = length found;
 226     in if len == 0 then default
 227       else if len != 1 then multiple
 228       else head found;
 229
 230   /* Find the first index in the list matching the specified
 231      predicate or return `default` if no such element exists.
 232
 233      Type: findFirstIndex :: (a -> Bool) -> b -> [a] -> (Int | b)
 234
 235      Example:
 236        findFirstIndex (x: x > 3) null [ 0 6 4 ]
 237        => 1
 238        findFirstIndex (x: x > 9) null [ 0 6 4 ]
 239        => null
 240   */
 241   findFirstIndex =
 242     # Predicate
 243     pred:
 244     # Default value to return
 245     default:
 246     # Input list
 247     list:
 248     let
 249       # A naive recursive implementation would be much simpler, but
 250       # would also overflow the evaluator stack. We use `foldl'` as a workaround
 251       # because it reuses the same stack space, evaluating the function for one
 252       # element after another. We can't return early, so this means that we
 253       # sacrifice early cutoff, but that appears to be an acceptable cost. A
 254       # clever scheme with "exponential search" is possible, but appears over-
 255       # engineered for now. See https://github.com/NixOS/nixpkgs/pull/235267
 256
 257       # Invariant:
 258       # - if index < 0 then el == elemAt list (- index - 1) and all elements before el didn't satisfy pred
 259       # - if index >= 0 then pred (elemAt list index) and all elements before (elemAt list index) didn't satisfy pred
 260       #
 261       # We start with index -1 and the 0'th element of the list, which satisfies the invariant
 262       resultIndex = foldl' (index: el:
 263         if index < 0 then
 264           # No match yet before the current index, we need to check the element
 265           if pred el then
 266             # We have a match! Turn it into the actual index to prevent future iterations from modifying it
 267             - index - 1
 268           else
 269             # Still no match, update the index to the next element (we're counting down, so minus one)
 270             index - 1
 271         else
 272           # There's already a match, propagate the index without evaluating anything
 273           index
 274       ) (-1) list;
 275     in
 276     if resultIndex < 0 then
 277       default
 278     else
 279       resultIndex;
 280
 281   /* Find the first element in the list matching the specified
 282      predicate or return `default` if no such element exists.
 283
 284      Type: findFirst :: (a -> bool) -> a -> [a] -> a
 285
 286      Example:
 287        findFirst (x: x > 3) 7 [ 1 6 4 ]
 288        => 6
 289        findFirst (x: x > 9) 7 [ 1 6 4 ]
 290        => 7
 291   */
 292   findFirst =
 293     # Predicate
 294     pred:
 295     # Default value to return
 296     default:
 297     # Input list
 298     list:
 299     let
 300       index = findFirstIndex pred null list;
 301     in
 302     if index == null then
 303       default
 304     else
 305       elemAt list index;
 306
 307   /* Return true if function `pred` returns true for at least one
 308      element of `list`.
 309
 310      Type: any :: (a -> bool) -> [a] -> bool
 311
 312      Example:
 313        any isString [ 1 "a" { } ]
 314        => true
 315        any isString [ 1 { } ]
 316        => false
 317   */
 318   any = builtins.any or (pred: foldr (x: y: if pred x then true else y) false);
 319
 320   /* Return true if function `pred` returns true for all elements of
 321      `list`.
 322
 323      Type: all :: (a -> bool) -> [a] -> bool
 324
 325      Example:
 326        all (x: x < 3) [ 1 2 ]
 327        => true
 328        all (x: x < 3) [ 1 2 3 ]
 329        => false
 330   */
 331   all = builtins.all or (pred: foldr (x: y: if pred x then y else false) true);
 332
 333   /* Count how many elements of `list` match the supplied predicate
 334      function.
 335
 336      Type: count :: (a -> bool) -> [a] -> int
 337
 338      Example:
 339        count (x: x == 3) [ 3 2 3 4 6 ]
 340        => 2
 341   */
 342   count =
 343     # Predicate
 344     pred: foldl' (c: x: if pred x then c + 1 else c) 0;
 345
 346   /* Return a singleton list or an empty list, depending on a boolean
 347      value.  Useful when building lists with optional elements
 348      (e.g. `++ optional (system == "i686-linux") firefox`).
 349
 350      Type: optional :: bool -> a -> [a]
 351
 352      Example:
 353        optional true "foo"
 354        => [ "foo" ]
 355        optional false "foo"
 356        => [ ]
 357   */
 358   optional = cond: elem: if cond then [elem] else [];
 359
 360   /* Return a list or an empty list, depending on a boolean value.
 361
 362      Type: optionals :: bool -> [a] -> [a]
 363
 364      Example:
 365        optionals true [ 2 3 ]
 366        => [ 2 3 ]
 367        optionals false [ 2 3 ]
 368        => [ ]
 369   */
 370   optionals =
 371     # Condition
 372     cond:
 373     # List to return if condition is true
 374     elems: if cond then elems else [];
 375
 376
 377   /* If argument is a list, return it; else, wrap it in a singleton
 378      list.  If you're using this, you should almost certainly
 379      reconsider if there isn't a more "well-typed" approach.
 380
 381      Example:
 382        toList [ 1 2 ]
 383        => [ 1 2 ]
 384        toList "hi"
 385        => [ "hi "]
 386   */
 387   toList = x: if isList x then x else [x];
 388
 389   /* Return a list of integers from `first` up to and including `last`.
 390
 391      Type: range :: int -> int -> [int]
 392
 393      Example:
 394        range 2 4
 395        => [ 2 3 4 ]
 396        range 3 2
 397        => [ ]
 398   */
 399   range =
 400     # First integer in the range
 401     first:
 402     # Last integer in the range
 403     last:
 404     if first > last then
 405       []
 406     else
 407       genList (n: first + n) (last - first + 1);
 408
 409   /* Return a list with `n` copies of an element.
 410
 411     Type: replicate :: int -> a -> [a]
 412
 413     Example:
 414       replicate 3 "a"
 415       => [ "a" "a" "a" ]
 416       replicate 2 true
 417       => [ true true ]
 418   */
 419   replicate = n: elem: genList (_: elem) n;
 420
 421   /* Splits the elements of a list in two lists, `right` and
 422      `wrong`, depending on the evaluation of a predicate.
 423
 424      Type: (a -> bool) -> [a] -> { right :: [a]; wrong :: [a]; }
 425
 426      Example:
 427        partition (x: x > 2) [ 5 1 2 3 4 ]
 428        => { right = [ 5 3 4 ]; wrong = [ 1 2 ]; }
 429   */
 430   partition = builtins.partition or (pred:
 431     foldr (h: t:
 432       if pred h
 433       then { right = [h] ++ t.right; wrong = t.wrong; }
 434       else { right = t.right; wrong = [h] ++ t.wrong; }
 435     ) { right = []; wrong = []; });
 436
 437   /* Splits the elements of a list into many lists, using the return value of a predicate.
 438      Predicate should return a string which becomes keys of attrset `groupBy` returns.
 439
 440      `groupBy'` allows to customise the combining function and initial value
 441
 442      Example:
 443        groupBy (x: boolToString (x > 2)) [ 5 1 2 3 4 ]
 444        => { true = [ 5 3 4 ]; false = [ 1 2 ]; }
 445        groupBy (x: x.name) [ {name = "icewm"; script = "icewm &";}
 446                              {name = "xfce";  script = "xfce4-session &";}
 447                              {name = "icewm"; script = "icewmbg &";}
 448                              {name = "mate";  script = "gnome-session &";}
 449                            ]
 450        => { icewm = [ { name = "icewm"; script = "icewm &"; }
 451                       { name = "icewm"; script = "icewmbg &"; } ];
 452             mate  = [ { name = "mate";  script = "gnome-session &"; } ];
 453             xfce  = [ { name = "xfce";  script = "xfce4-session &"; } ];
 454           }
 455
 456        groupBy' builtins.add 0 (x: boolToString (x > 2)) [ 5 1 2 3 4 ]
 457        => { true = 12; false = 3; }
 458   */
 459   groupBy' = op: nul: pred: lst: mapAttrs (name: foldl op nul) (groupBy pred lst);
 460
 461   groupBy = builtins.groupBy or (
 462     pred: foldl' (r: e:
 463        let
 464          key = pred e;
 465        in
 466          r // { ${key} = (r.${key} or []) ++ [e]; }
 467     ) {});
 468
 469   /* Merges two lists of the same size together. If the sizes aren't the same
 470      the merging stops at the shortest. How both lists are merged is defined
 471      by the first argument.
 472
 473      Type: zipListsWith :: (a -> b -> c) -> [a] -> [b] -> [c]
 474
 475      Example:
 476        zipListsWith (a: b: a + b) ["h" "l"] ["e" "o"]
 477        => ["he" "lo"]
 478   */
 479   zipListsWith =
 480     # Function to zip elements of both lists
 481     f:
 482     # First list
 483     fst:
 484     # Second list
 485     snd:
 486     genList
 487       (n: f (elemAt fst n) (elemAt snd n)) (min (length fst) (length snd));
 488
 489   /* Merges two lists of the same size together. If the sizes aren't the same
 490      the merging stops at the shortest.
 491
 492      Type: zipLists :: [a] -> [b] -> [{ fst :: a; snd :: b; }]
 493
 494      Example:
 495        zipLists [ 1 2 ] [ "a" "b" ]
 496        => [ { fst = 1; snd = "a"; } { fst = 2; snd = "b"; } ]
 497   */
 498   zipLists = zipListsWith (fst: snd: { inherit fst snd; });
 499
 500   /* Reverse the order of the elements of a list.
 501
 502      Type: reverseList :: [a] -> [a]
 503
 504      Example:
 505
 506        reverseList [ "b" "o" "j" ]
 507        => [ "j" "o" "b" ]
 508   */
 509   reverseList = xs:
 510     let l = length xs; in genList (n: elemAt xs (l - n - 1)) l;
 511
 512   /* Depth-First Search (DFS) for lists `list != []`.
 513
 514      `before a b == true` means that `b` depends on `a` (there's an
 515      edge from `b` to `a`).
 516
 517      Example:
 518          listDfs true hasPrefix [ "/home/user" "other" "/" "/home" ]
 519            == { minimal = "/";                  # minimal element
 520                 visited = [ "/home/user" ];     # seen elements (in reverse order)
 521                 rest    = [ "/home" "other" ];  # everything else
 522               }
 523
 524          listDfs true hasPrefix [ "/home/user" "other" "/" "/home" "/" ]
 525            == { cycle   = "/";                  # cycle encountered at this element
 526                 loops   = [ "/" ];              # and continues to these elements
 527                 visited = [ "/" "/home/user" ]; # elements leading to the cycle (in reverse order)
 528                 rest    = [ "/home" "other" ];  # everything else
 529
 530    */
 531   listDfs = stopOnCycles: before: list:
 532     let
 533       dfs' = us: visited: rest:
 534         let
 535           c = filter (x: before x us) visited;
 536           b = partition (x: before x us) rest;
 537         in if stopOnCycles && (length c > 0)
 538            then { cycle = us; loops = c; inherit visited rest; }
 539            else if length b.right == 0
 540                 then # nothing is before us
 541                      { minimal = us; inherit visited rest; }
 542                 else # grab the first one before us and continue
 543                      dfs' (head b.right)
 544                           ([ us ] ++ visited)
 545                           (tail b.right ++ b.wrong);
 546     in dfs' (head list) [] (tail list);
 547
 548   /* Sort a list based on a partial ordering using DFS. This
 549      implementation is O(N^2), if your ordering is linear, use `sort`
 550      instead.
 551
 552      `before a b == true` means that `b` should be after `a`
 553      in the result.
 554
 555      Example:
 556
 557          toposort hasPrefix [ "/home/user" "other" "/" "/home" ]
 558            == { result = [ "/" "/home" "/home/user" "other" ]; }
 559
 560          toposort hasPrefix [ "/home/user" "other" "/" "/home" "/" ]
 561            == { cycle = [ "/home/user" "/" "/" ]; # path leading to a cycle
 562                 loops = [ "/" ]; }                # loops back to these elements
 563
 564          toposort hasPrefix [ "other" "/home/user" "/home" "/" ]
 565            == { result = [ "other" "/" "/home" "/home/user" ]; }
 566
 567          toposort (a: b: a < b) [ 3 2 1 ] == { result = [ 1 2 3 ]; }
 568
 569    */
 570   toposort = before: list:
 571     let
 572       dfsthis = listDfs true before list;
 573       toporest = toposort before (dfsthis.visited ++ dfsthis.rest);
 574     in
 575       if length list < 2
 576       then # finish
 577            { result =  list; }
 578       else if dfsthis ? cycle
 579            then # there's a cycle, starting from the current vertex, return it
 580                 { cycle = reverseList ([ dfsthis.cycle ] ++ dfsthis.visited);
 581                   inherit (dfsthis) loops; }
 582            else if toporest ? cycle
 583                 then # there's a cycle somewhere else in the graph, return it
 584                      toporest
 585                 # Slow, but short. Can be made a bit faster with an explicit stack.
 586                 else # there are no cycles
 587                      { result = [ dfsthis.minimal ] ++ toporest.result; };
 588
 589   /* Sort a list based on a comparator function which compares two
 590      elements and returns true if the first argument is strictly below
 591      the second argument.  The returned list is sorted in an increasing
 592      order.  The implementation does a quick-sort.
 593
 594      Example:
 595        sort (a: b: a < b) [ 5 3 7 ]
 596        => [ 3 5 7 ]
 597   */
 598   sort = builtins.sort or (
 599     strictLess: list:
 600     let
 601       len = length list;
 602       first = head list;
 603       pivot' = n: acc@{ left, right }: let el = elemAt list n; next = pivot' (n + 1); in
 604         if n == len
 605           then acc
 606         else if strictLess first el
 607           then next { inherit left; right = [ el ] ++ right; }
 608         else
 609           next { left = [ el ] ++ left; inherit right; };
 610       pivot = pivot' 1 { left = []; right = []; };
 611     in
 612       if len < 2 then list
 613       else (sort strictLess pivot.left) ++  [ first ] ++  (sort strictLess pivot.right));
 614
 615   /* Compare two lists element-by-element.
 616
 617      Example:
 618        compareLists compare [] []
 619        => 0
 620        compareLists compare [] [ "a" ]
 621        => -1
 622        compareLists compare [ "a" ] []
 623        => 1
 624        compareLists compare [ "a" "b" ] [ "a" "c" ]
 625        => -1
 626   */
 627   compareLists = cmp: a: b:
 628     if a == []
 629     then if b == []
 630          then 0
 631          else -1
 632     else if b == []
 633          then 1
 634          else let rel = cmp (head a) (head b); in
 635               if rel == 0
 636               then compareLists cmp (tail a) (tail b)
 637               else rel;
 638
 639   /* Sort list using "Natural sorting".
 640      Numeric portions of strings are sorted in numeric order.
 641
 642      Example:
 643        naturalSort ["disk11" "disk8" "disk100" "disk9"]
 644        => ["disk8" "disk9" "disk11" "disk100"]
 645        naturalSort ["10.46.133.149" "10.5.16.62" "10.54.16.25"]
 646        => ["10.5.16.62" "10.46.133.149" "10.54.16.25"]
 647        naturalSort ["v0.2" "v0.15" "v0.0.9"]
 648        => [ "v0.0.9" "v0.2" "v0.15" ]
 649   */
 650   naturalSort = lst:
 651     let
 652       vectorise = s: map (x: if isList x then toInt (head x) else x) (builtins.split "(0|[1-9][0-9]*)" s);
 653       prepared = map (x: [ (vectorise x) x ]) lst; # remember vectorised version for O(n) regex splits
 654       less = a: b: (compareLists compare (head a) (head b)) < 0;
 655     in
 656       map (x: elemAt x 1) (sort less prepared);
 657
 658   /* Return the first (at most) N elements of a list.
 659
 660      Type: take :: int -> [a] -> [a]
 661
 662      Example:
 663        take 2 [ "a" "b" "c" "d" ]
 664        => [ "a" "b" ]
 665        take 2 [ ]
 666        => [ ]
 667   */
 668   take =
 669     # Number of elements to take
 670     count: sublist 0 count;
 671
 672   /* Remove the first (at most) N elements of a list.
 673
 674      Type: drop :: int -> [a] -> [a]
 675
 676      Example:
 677        drop 2 [ "a" "b" "c" "d" ]
 678        => [ "c" "d" ]
 679        drop 2 [ ]
 680        => [ ]
 681   */
 682   drop =
 683     # Number of elements to drop
 684     count:
 685     # Input list
 686     list: sublist count (length list) list;
 687
 688   /* Whether the first list is a prefix of the second list.
 689
 690   Type: hasPrefix :: [a] -> [a] -> bool
 691
 692   Example:
 693     hasPrefix [ 1 2 ] [ 1 2 3 4 ]
 694     => true
 695     hasPrefix [ 0 1 ] [ 1 2 3 4 ]
 696     => false
 697   */
 698   hasPrefix =
 699     list1:
 700     list2:
 701     take (length list1) list2 == list1;
 702
 703   /* Remove the first list as a prefix from the second list.
 704   Error if the first list isn't a prefix of the second list.
 705
 706   Type: removePrefix :: [a] -> [a] -> [a]
 707
 708   Example:
 709     removePrefix [ 1 2 ] [ 1 2 3 4 ]
 710     => [ 3 4 ]
 711     removePrefix [ 0 1 ] [ 1 2 3 4 ]
 712     => <error>
 713   */
 714   removePrefix =
 715     list1:
 716     list2:
 717     if hasPrefix list1 list2 then
 718       drop (length list1) list2
 719     else
 720       throw "lib.lists.removePrefix: First argument is not a list prefix of the second argument";
 721
 722   /* Return a list consisting of at most `count` elements of `list`,
 723      starting at index `start`.
 724
 725      Type: sublist :: int -> int -> [a] -> [a]
 726
 727      Example:
 728        sublist 1 3 [ "a" "b" "c" "d" "e" ]
 729        => [ "b" "c" "d" ]
 730        sublist 1 3 [ ]
 731        => [ ]
 732   */
 733   sublist =
 734     # Index at which to start the sublist
 735     start:
 736     # Number of elements to take
 737     count:
 738     # Input list
 739     list:
 740     let len = length list; in
 741     genList
 742       (n: elemAt list (n + start))
 743       (if start >= len then 0
 744        else if start + count > len then len - start
 745        else count);
 746
 747   /* The common prefix of two lists.
 748
 749   Type: commonPrefix :: [a] -> [a] -> [a]
 750
 751   Example:
 752     commonPrefix [ 1 2 3 4 5 6 ] [ 1 2 4 8 ]
 753     => [ 1 2 ]
 754     commonPrefix [ 1 2 3 ] [ 1 2 3 4 5 ]
 755     => [ 1 2 3 ]
 756     commonPrefix [ 1 2 3 ] [ 4 5 6 ]
 757     => [ ]
 758   */
 759   commonPrefix =
 760     list1:
 761     list2:
 762     let
 763       # Zip the lists together into a list of booleans whether each element matches
 764       matchings = zipListsWith (fst: snd: fst != snd) list1 list2;
 765       # Find the first index where the elements don't match,
 766       # which will then also be the length of the common prefix.
 767       # If all elements match, we fall back to the length of the zipped list,
 768       # which is the same as the length of the smaller list.
 769       commonPrefixLength = findFirstIndex id (length matchings) matchings;
 770     in
 771     take commonPrefixLength list1;
 772
 773   /* Return the last element of a list.
 774
 775      This function throws an error if the list is empty.
 776
 777      Type: last :: [a] -> a
 778
 779      Example:
 780        last [ 1 2 3 ]
 781        => 3
 782   */
 783   last = list:
 784     assert lib.assertMsg (list != []) "lists.last: list must not be empty!";
 785     elemAt list (length list - 1);
 786
 787   /* Return all elements but the last.
 788
 789      This function throws an error if the list is empty.
 790
 791      Type: init :: [a] -> [a]
 792
 793      Example:
 794        init [ 1 2 3 ]
 795        => [ 1 2 ]
 796   */
 797   init = list:
 798     assert lib.assertMsg (list != []) "lists.init: list must not be empty!";
 799     take (length list - 1) list;
 800
 801
 802   /* Return the image of the cross product of some lists by a function.
 803
 804     Example:
 805       crossLists (x:y: "${toString x}${toString y}") [[1 2] [3 4]]
 806       => [ "13" "14" "23" "24" ]
 807   */
 808   crossLists = builtins.trace
 809     "lib.crossLists is deprecated, use lib.cartesianProductOfSets instead"
 810     (f: foldl (fs: args: concatMap (f: map f args) fs) [f]);
 811
 812
 813   /* Remove duplicate elements from the list. O(n^2) complexity.
 814
 815      Type: unique :: [a] -> [a]
 816
 817      Example:
 818        unique [ 3 2 3 4 ]
 819        => [ 3 2 4 ]
 820    */
 821   unique = foldl' (acc: e: if elem e acc then acc else acc ++ [ e ]) [];
 822
 823   /* Check if list contains only unique elements. O(n^2) complexity.
 824
 825      Type: allUnique :: [a] -> bool
 826
 827      Example:
 828        allUnique [ 3 2 3 4 ]
 829        => false
 830        allUnique [ 3 2 4 1 ]
 831        => true
 832    */
 833   allUnique = list: (length (unique list) == length list);
 834
 835
 836   /* Intersects list 'e' and another list. O(nm) complexity.
 837
 838      Example:
 839        intersectLists [ 1 2 3 ] [ 6 3 2 ]
 840        => [ 3 2 ]
 841   */
 842   intersectLists = e: filter (x: elem x e);
 843
 844   /* Subtracts list 'e' from another list. O(nm) complexity.
 845
 846      Example:
 847        subtractLists [ 3 2 ] [ 1 2 3 4 5 3 ]
 848        => [ 1 4 5 ]
 849   */
 850   subtractLists = e: filter (x: !(elem x e));
 851
 852   /* Test if two lists have no common element.
 853      It should be slightly more efficient than (intersectLists a b == [])
 854   */
 855   mutuallyExclusive = a: b: length a == 0 || !(any (x: elem x a) b);
 856
 857 }