lib/lists.nix

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