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