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