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