lib/lists.nix

   1 # General list operations.
   2
   3 { lib }:
   4 let
   5   inherit (lib.strings) toInt;
   6   inherit (lib.trivial) compare min;
   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   /* Strict version of `foldl`.
  90
  91      The difference is that evaluation is forced upon access. Usually used
  92      with small whole results (in contrast with lazily-generated list or large
  93      lists where only a part is consumed.)
  94
  95      Type: foldl' :: (b -> a -> b) -> b -> [a] -> b
  96   */
  97   foldl' = builtins.foldl' or foldl;
  98
  99   /* Map with index starting from 0
 100
 101      Type: imap0 :: (int -> a -> b) -> [a] -> [b]
 102
 103      Example:
 104        imap0 (i: v: "${v}-${toString i}") ["a" "b"]
 105        => [ "a-0" "b-1" ]
 106   */
 107   imap0 = f: list: genList (n: f n (elemAt list n)) (length list);
 108
 109   /* Map with index starting from 1
 110
 111      Type: imap1 :: (int -> a -> b) -> [a] -> [b]
 112
 113      Example:
 114        imap1 (i: v: "${v}-${toString i}") ["a" "b"]
 115        => [ "a-1" "b-2" ]
 116   */
 117   imap1 = f: list: genList (n: f (n + 1) (elemAt list n)) (length list);
 118
 119   /* Map and concatenate the result.
 120
 121      Type: concatMap :: (a -> [b]) -> [a] -> [b]
 122
 123      Example:
 124        concatMap (x: [x] ++ ["z"]) ["a" "b"]
 125        => [ "a" "z" "b" "z" ]
 126   */
 127   concatMap = builtins.concatMap or (f: list: concatLists (map f list));
 128
 129   /* Flatten the argument into a single list; that is, nested lists are
 130      spliced into the top-level lists.
 131
 132      Example:
 133        flatten [1 [2 [3] 4] 5]
 134        => [1 2 3 4 5]
 135        flatten 1
 136        => [1]
 137   */
 138   flatten = x:
 139     if isList x
 140     then concatMap (y: flatten y) x
 141     else [x];
 142
 143   /* Remove elements equal to 'e' from a list.  Useful for buildInputs.
 144
 145      Type: remove :: a -> [a] -> [a]
 146
 147      Example:
 148        remove 3 [ 1 3 4 3 ]
 149        => [ 1 4 ]
 150   */
 151   remove =
 152     # Element to remove from the list
 153     e: filter (x: x != e);
 154
 155   /* Find the sole element in the list matching the specified
 156      predicate, returns `default` if no such element exists, or
 157      `multiple` if there are multiple matching elements.
 158
 159      Type: findSingle :: (a -> bool) -> a -> a -> [a] -> a
 160
 161      Example:
 162        findSingle (x: x == 3) "none" "multiple" [ 1 3 3 ]
 163        => "multiple"
 164        findSingle (x: x == 3) "none" "multiple" [ 1 3 ]
 165        => 3
 166        findSingle (x: x == 3) "none" "multiple" [ 1 9 ]
 167        => "none"
 168   */
 169   findSingle =
 170     # Predicate
 171     pred:
 172     # Default value to return if element was not found.
 173     default:
 174     # Default value to return if more than one element was found
 175     multiple:
 176     # Input list
 177     list:
 178     let found = filter pred list; len = length found;
 179     in if len == 0 then default
 180       else if len != 1 then multiple
 181       else head found;
 182
 183   /* Find the first element in the list matching the specified
 184      predicate or return `default` if no such element exists.
 185
 186      Type: findFirst :: (a -> bool) -> a -> [a] -> a
 187
 188      Example:
 189        findFirst (x: x > 3) 7 [ 1 6 4 ]
 190        => 6
 191        findFirst (x: x > 9) 7 [ 1 6 4 ]
 192        => 7
 193   */
 194   findFirst =
 195     # Predicate
 196     pred:
 197     # Default value to return
 198     default:
 199     # Input list
 200     list:
 201     let found = filter pred list;
 202     in if found == [] then default else head found;
 203
 204   /* Return true if function `pred` returns true for at least one
 205      element of `list`.
 206
 207      Type: any :: (a -> bool) -> [a] -> bool
 208
 209      Example:
 210        any isString [ 1 "a" { } ]
 211        => true
 212        any isString [ 1 { } ]
 213        => false
 214   */
 215   any = builtins.any or (pred: foldr (x: y: if pred x then true else y) false);
 216
 217   /* Return true if function `pred` returns true for all elements of
 218      `list`.
 219
 220      Type: all :: (a -> bool) -> [a] -> bool
 221
 222      Example:
 223        all (x: x < 3) [ 1 2 ]
 224        => true
 225        all (x: x < 3) [ 1 2 3 ]
 226        => false
 227   */
 228   all = builtins.all or (pred: foldr (x: y: if pred x then y else false) true);
 229
 230   /* Count how many elements of `list` match the supplied predicate
 231      function.
 232
 233      Type: count :: (a -> bool) -> [a] -> int
 234
 235      Example:
 236        count (x: x == 3) [ 3 2 3 4 6 ]
 237        => 2
 238   */
 239   count =
 240     # Predicate
 241     pred: foldl' (c: x: if pred x then c + 1 else c) 0;
 242
 243   /* Return a singleton list or an empty list, depending on a boolean
 244      value.  Useful when building lists with optional elements
 245      (e.g. `++ optional (system == "i686-linux") firefox').
 246
 247      Type: optional :: bool -> a -> [a]
 248
 249      Example:
 250        optional true "foo"
 251        => [ "foo" ]
 252        optional false "foo"
 253        => [ ]
 254   */
 255   optional = cond: elem: if cond then [elem] else [];
 256
 257   /* Return a list or an empty list, depending on a boolean value.
 258
 259      Type: optionals :: bool -> [a] -> [a]
 260
 261      Example:
 262        optionals true [ 2 3 ]
 263        => [ 2 3 ]
 264        optionals false [ 2 3 ]
 265        => [ ]
 266   */
 267   optionals =
 268     # Condition
 269     cond:
 270     # List to return if condition is true
 271     elems: if cond then elems else [];
 272
 273
 274   /* If argument is a list, return it; else, wrap it in a singleton
 275      list.  If you're using this, you should almost certainly
 276      reconsider if there isn't a more "well-typed" approach.
 277
 278      Example:
 279        toList [ 1 2 ]
 280        => [ 1 2 ]
 281        toList "hi"
 282        => [ "hi "]
 283   */
 284   toList = x: if isList x then x else [x];
 285
 286   /* Return a list of integers from `first' up to and including `last'.
 287
 288      Type: range :: int -> int -> [int]
 289
 290      Example:
 291        range 2 4
 292        => [ 2 3 4 ]
 293        range 3 2
 294        => [ ]
 295   */
 296   range =
 297     # First integer in the range
 298     first:
 299     # Last integer in the range
 300     last:
 301     if first > last then
 302       []
 303     else
 304       genList (n: first + n) (last - first + 1);
 305
 306   /* Splits the elements of a list in two lists, `right` and
 307      `wrong`, depending on the evaluation of a predicate.
 308
 309      Type: (a -> bool) -> [a] -> { right :: [a], wrong :: [a] }
 310
 311      Example:
 312        partition (x: x > 2) [ 5 1 2 3 4 ]
 313        => { right = [ 5 3 4 ]; wrong = [ 1 2 ]; }
 314   */
 315   partition = builtins.partition or (pred:
 316     foldr (h: t:
 317       if pred h
 318       then { right = [h] ++ t.right; wrong = t.wrong; }
 319       else { right = t.right; wrong = [h] ++ t.wrong; }
 320     ) { right = []; wrong = []; });
 321
 322   /* Splits the elements of a list into many lists, using the return value of a predicate.
 323      Predicate should return a string which becomes keys of attrset `groupBy' returns.
 324
 325      `groupBy'` allows to customise the combining function and initial value
 326
 327      Example:
 328        groupBy (x: boolToString (x > 2)) [ 5 1 2 3 4 ]
 329        => { true = [ 5 3 4 ]; false = [ 1 2 ]; }
 330        groupBy (x: x.name) [ {name = "icewm"; script = "icewm &";}
 331                              {name = "xfce";  script = "xfce4-session &";}
 332                              {name = "icewm"; script = "icewmbg &";}
 333                              {name = "mate";  script = "gnome-session &";}
 334                            ]
 335        => { icewm = [ { name = "icewm"; script = "icewm &"; }
 336                       { name = "icewm"; script = "icewmbg &"; } ];
 337             mate  = [ { name = "mate";  script = "gnome-session &"; } ];
 338             xfce  = [ { name = "xfce";  script = "xfce4-session &"; } ];
 339           }
 340
 341        groupBy' builtins.add 0 (x: boolToString (x > 2)) [ 5 1 2 3 4 ]
 342        => { true = 12; false = 3; }
 343   */
 344   groupBy' = op: nul: pred: lst: mapAttrs (name: foldl op nul) (groupBy pred lst);
 345
 346   groupBy = builtins.groupBy or (
 347     pred: foldl' (r: e:
 348        let
 349          key = pred e;
 350        in
 351          r // { ${key} = (r.${key} or []) ++ [e]; }
 352     ) {});
 353
 354   /* Merges two lists of the same size together. If the sizes aren't the same
 355      the merging stops at the shortest. How both lists are merged is defined
 356      by the first argument.
 357
 358      Type: zipListsWith :: (a -> b -> c) -> [a] -> [b] -> [c]
 359
 360      Example:
 361        zipListsWith (a: b: a + b) ["h" "l"] ["e" "o"]
 362        => ["he" "lo"]
 363   */
 364   zipListsWith =
 365     # Function to zip elements of both lists
 366     f:
 367     # First list
 368     fst:
 369     # Second list
 370     snd:
 371     genList
 372       (n: f (elemAt fst n) (elemAt snd n)) (min (length fst) (length snd));
 373
 374   /* Merges two lists of the same size together. If the sizes aren't the same
 375      the merging stops at the shortest.
 376
 377      Type: zipLists :: [a] -> [b] -> [{ fst :: a, snd :: b}]
 378
 379      Example:
 380        zipLists [ 1 2 ] [ "a" "b" ]
 381        => [ { fst = 1; snd = "a"; } { fst = 2; snd = "b"; } ]
 382   */
 383   zipLists = zipListsWith (fst: snd: { inherit fst snd; });
 384
 385   /* Reverse the order of the elements of a list.
 386
 387      Type: reverseList :: [a] -> [a]
 388
 389      Example:
 390
 391        reverseList [ "b" "o" "j" ]
 392        => [ "j" "o" "b" ]
 393   */
 394   reverseList = xs:
 395     let l = length xs; in genList (n: elemAt xs (l - n - 1)) l;
 396
 397   /* Depth-First Search (DFS) for lists `list != []`.
 398
 399      `before a b == true` means that `b` depends on `a` (there's an
 400      edge from `b` to `a`).
 401
 402      Example:
 403          listDfs true hasPrefix [ "/home/user" "other" "/" "/home" ]
 404            == { minimal = "/";                  # minimal element
 405                 visited = [ "/home/user" ];     # seen elements (in reverse order)
 406                 rest    = [ "/home" "other" ];  # everything else
 407               }
 408
 409          listDfs true hasPrefix [ "/home/user" "other" "/" "/home" "/" ]
 410            == { cycle   = "/";                  # cycle encountered at this element
 411                 loops   = [ "/" ];              # and continues to these elements
 412                 visited = [ "/" "/home/user" ]; # elements leading to the cycle (in reverse order)
 413                 rest    = [ "/home" "other" ];  # everything else
 414
 415    */
 416   listDfs = stopOnCycles: before: list:
 417     let
 418       dfs' = us: visited: rest:
 419         let
 420           c = filter (x: before x us) visited;
 421           b = partition (x: before x us) rest;
 422         in if stopOnCycles && (length c > 0)
 423            then { cycle = us; loops = c; inherit visited rest; }
 424            else if length b.right == 0
 425                 then # nothing is before us
 426                      { minimal = us; inherit visited rest; }
 427                 else # grab the first one before us and continue
 428                      dfs' (head b.right)
 429                           ([ us ] ++ visited)
 430                           (tail b.right ++ b.wrong);
 431     in dfs' (head list) [] (tail list);
 432
 433   /* Sort a list based on a partial ordering using DFS. This
 434      implementation is O(N^2), if your ordering is linear, use `sort`
 435      instead.
 436
 437      `before a b == true` means that `b` should be after `a`
 438      in the result.
 439
 440      Example:
 441
 442          toposort hasPrefix [ "/home/user" "other" "/" "/home" ]
 443            == { result = [ "/" "/home" "/home/user" "other" ]; }
 444
 445          toposort hasPrefix [ "/home/user" "other" "/" "/home" "/" ]
 446            == { cycle = [ "/home/user" "/" "/" ]; # path leading to a cycle
 447                 loops = [ "/" ]; }                # loops back to these elements
 448
 449          toposort hasPrefix [ "other" "/home/user" "/home" "/" ]
 450            == { result = [ "other" "/" "/home" "/home/user" ]; }
 451
 452          toposort (a: b: a < b) [ 3 2 1 ] == { result = [ 1 2 3 ]; }
 453
 454    */
 455   toposort = before: list:
 456     let
 457       dfsthis = listDfs true before list;
 458       toporest = toposort before (dfsthis.visited ++ dfsthis.rest);
 459     in
 460       if length list < 2
 461       then # finish
 462            { result =  list; }
 463       else if dfsthis ? cycle
 464            then # there's a cycle, starting from the current vertex, return it
 465                 { cycle = reverseList ([ dfsthis.cycle ] ++ dfsthis.visited);
 466                   inherit (dfsthis) loops; }
 467            else if toporest ? cycle
 468                 then # there's a cycle somewhere else in the graph, return it
 469                      toporest
 470                 # Slow, but short. Can be made a bit faster with an explicit stack.
 471                 else # there are no cycles
 472                      { result = [ dfsthis.minimal ] ++ toporest.result; };
 473
 474   /* Sort a list based on a comparator function which compares two
 475      elements and returns true if the first argument is strictly below
 476      the second argument.  The returned list is sorted in an increasing
 477      order.  The implementation does a quick-sort.
 478
 479      Example:
 480        sort (a: b: a < b) [ 5 3 7 ]
 481        => [ 3 5 7 ]
 482   */
 483   sort = builtins.sort or (
 484     strictLess: list:
 485     let
 486       len = length list;
 487       first = head list;
 488       pivot' = n: acc@{ left, right }: let el = elemAt list n; next = pivot' (n + 1); in
 489         if n == len
 490           then acc
 491         else if strictLess first el
 492           then next { inherit left; right = [ el ] ++ right; }
 493         else
 494           next { left = [ el ] ++ left; inherit right; };
 495       pivot = pivot' 1 { left = []; right = []; };
 496     in
 497       if len < 2 then list
 498       else (sort strictLess pivot.left) ++  [ first ] ++  (sort strictLess pivot.right));
 499
 500   /* Compare two lists element-by-element.
 501
 502      Example:
 503        compareLists compare [] []
 504        => 0
 505        compareLists compare [] [ "a" ]
 506        => -1
 507        compareLists compare [ "a" ] []
 508        => 1
 509        compareLists compare [ "a" "b" ] [ "a" "c" ]
 510        => -1
 511   */
 512   compareLists = cmp: a: b:
 513     if a == []
 514     then if b == []
 515          then 0
 516          else -1
 517     else if b == []
 518          then 1
 519          else let rel = cmp (head a) (head b); in
 520               if rel == 0
 521               then compareLists cmp (tail a) (tail b)
 522               else rel;
 523
 524   /* Sort list using "Natural sorting".
 525      Numeric portions of strings are sorted in numeric order.
 526
 527      Example:
 528        naturalSort ["disk11" "disk8" "disk100" "disk9"]
 529        => ["disk8" "disk9" "disk11" "disk100"]
 530        naturalSort ["10.46.133.149" "10.5.16.62" "10.54.16.25"]
 531        => ["10.5.16.62" "10.46.133.149" "10.54.16.25"]
 532        naturalSort ["v0.2" "v0.15" "v0.0.9"]
 533        => [ "v0.0.9" "v0.2" "v0.15" ]
 534   */
 535   naturalSort = lst:
 536     let
 537       vectorise = s: map (x: if isList x then toInt (head x) else x) (builtins.split "(0|[1-9][0-9]*)" s);
 538       prepared = map (x: [ (vectorise x) x ]) lst; # remember vectorised version for O(n) regex splits
 539       less = a: b: (compareLists compare (head a) (head b)) < 0;
 540     in
 541       map (x: elemAt x 1) (sort less prepared);
 542
 543   /* Return the first (at most) N elements of a list.
 544
 545      Type: take :: int -> [a] -> [a]
 546
 547      Example:
 548        take 2 [ "a" "b" "c" "d" ]
 549        => [ "a" "b" ]
 550        take 2 [ ]
 551        => [ ]
 552   */
 553   take =
 554     # Number of elements to take
 555     count: sublist 0 count;
 556
 557   /* Remove the first (at most) N elements of a list.
 558
 559      Type: drop :: int -> [a] -> [a]
 560
 561      Example:
 562        drop 2 [ "a" "b" "c" "d" ]
 563        => [ "c" "d" ]
 564        drop 2 [ ]
 565        => [ ]
 566   */
 567   drop =
 568     # Number of elements to drop
 569     count:
 570     # Input list
 571     list: sublist count (length list) list;
 572
 573   /* Return a list consisting of at most `count` elements of `list`,
 574      starting at index `start`.
 575
 576      Type: sublist :: int -> int -> [a] -> [a]
 577
 578      Example:
 579        sublist 1 3 [ "a" "b" "c" "d" "e" ]
 580        => [ "b" "c" "d" ]
 581        sublist 1 3 [ ]
 582        => [ ]
 583   */
 584   sublist =
 585     # Index at which to start the sublist
 586     start:
 587     # Number of elements to take
 588     count:
 589     # Input list
 590     list:
 591     let len = length list; in
 592     genList
 593       (n: elemAt list (n + start))
 594       (if start >= len then 0
 595        else if start + count > len then len - start
 596        else count);
 597
 598   /* Return the last element of a list.
 599
 600      This function throws an error if the list is empty.
 601
 602      Type: last :: [a] -> a
 603
 604      Example:
 605        last [ 1 2 3 ]
 606        => 3
 607   */
 608   last = list:
 609     assert lib.assertMsg (list != []) "lists.last: list must not be empty!";
 610     elemAt list (length list - 1);
 611
 612   /* Return all elements but the last.
 613
 614      This function throws an error if the list is empty.
 615
 616      Type: init :: [a] -> [a]
 617
 618      Example:
 619        init [ 1 2 3 ]
 620        => [ 1 2 ]
 621   */
 622   init = list:
 623     assert lib.assertMsg (list != []) "lists.init: list must not be empty!";
 624     take (length list - 1) list;
 625
 626
 627   /* Return the image of the cross product of some lists by a function.
 628
 629     Example:
 630       crossLists (x:y: "${toString x}${toString y}") [[1 2] [3 4]]
 631       => [ "13" "14" "23" "24" ]
 632   */
 633   crossLists = builtins.trace
 634     "lib.crossLists is deprecated, use lib.cartesianProductOfSets instead"
 635     (f: foldl (fs: args: concatMap (f: map f args) fs) [f]);
 636
 637
 638   /* Remove duplicate elements from the list. O(n^2) complexity.
 639
 640      Type: unique :: [a] -> [a]
 641
 642      Example:
 643        unique [ 3 2 3 4 ]
 644        => [ 3 2 4 ]
 645    */
 646   unique = foldl' (acc: e: if elem e acc then acc else acc ++ [ e ]) [];
 647
 648   /* Intersects list 'e' and another list. O(nm) complexity.
 649
 650      Example:
 651        intersectLists [ 1 2 3 ] [ 6 3 2 ]
 652        => [ 3 2 ]
 653   */
 654   intersectLists = e: filter (x: elem x e);
 655
 656   /* Subtracts list 'e' from another list. O(nm) complexity.
 657
 658      Example:
 659        subtractLists [ 3 2 ] [ 1 2 3 4 5 3 ]
 660        => [ 1 4 5 ]
 661   */
 662   subtractLists = e: filter (x: !(elem x e));
 663
 664   /* Test if two lists have no common element.
 665      It should be slightly more efficient than (intersectLists a b == [])
 666   */
 667   mutuallyExclusive = a: b: length a == 0 || !(any (x: elem x a) b);
 668
 669 }