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