tjh.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 /* Return a list with `n` copies of an element.
307
308 Type: replicate :: int -> a -> [a]
309
310 Example:
311 replicate 3 "a"
312 => [ "a" "a" "a" ]
313 replicate 2 true
314 => [ true true ]
315 */
316 replicate = n: elem: genList (_: elem) n;
317
318 /* Splits the elements of a list in two lists, `right` and
319 `wrong`, depending on the evaluation of a predicate.
320
321 Type: (a -> bool) -> [a] -> { right :: [a]; wrong :: [a]; }
322
323 Example:
324 partition (x: x > 2) [ 5 1 2 3 4 ]
325 => { right = [ 5 3 4 ]; wrong = [ 1 2 ]; }
326 */
327 partition = builtins.partition or (pred:
328 foldr (h: t:
329 if pred h
330 then { right = [h] ++ t.right; wrong = t.wrong; }
331 else { right = t.right; wrong = [h] ++ t.wrong; }
332 ) { right = []; wrong = []; });
333
334 /* Splits the elements of a list into many lists, using the return value of a predicate.
335 Predicate should return a string which becomes keys of attrset `groupBy` returns.
336
337 `groupBy'` allows to customise the combining function and initial value
338
339 Example:
340 groupBy (x: boolToString (x > 2)) [ 5 1 2 3 4 ]
341 => { true = [ 5 3 4 ]; false = [ 1 2 ]; }
342 groupBy (x: x.name) [ {name = "icewm"; script = "icewm &";}
343 {name = "xfce"; script = "xfce4-session &";}
344 {name = "icewm"; script = "icewmbg &";}
345 {name = "mate"; script = "gnome-session &";}
346 ]
347 => { icewm = [ { name = "icewm"; script = "icewm &"; }
348 { name = "icewm"; script = "icewmbg &"; } ];
349 mate = [ { name = "mate"; script = "gnome-session &"; } ];
350 xfce = [ { name = "xfce"; script = "xfce4-session &"; } ];
351 }
352
353 groupBy' builtins.add 0 (x: boolToString (x > 2)) [ 5 1 2 3 4 ]
354 => { true = 12; false = 3; }
355 */
356 groupBy' = op: nul: pred: lst: mapAttrs (name: foldl op nul) (groupBy pred lst);
357
358 groupBy = builtins.groupBy or (
359 pred: foldl' (r: e:
360 let
361 key = pred e;
362 in
363 r // { ${key} = (r.${key} or []) ++ [e]; }
364 ) {});
365
366 /* Merges two lists of the same size together. If the sizes aren't the same
367 the merging stops at the shortest. How both lists are merged is defined
368 by the first argument.
369
370 Type: zipListsWith :: (a -> b -> c) -> [a] -> [b] -> [c]
371
372 Example:
373 zipListsWith (a: b: a + b) ["h" "l"] ["e" "o"]
374 => ["he" "lo"]
375 */
376 zipListsWith =
377 # Function to zip elements of both lists
378 f:
379 # First list
380 fst:
381 # Second list
382 snd:
383 genList
384 (n: f (elemAt fst n) (elemAt snd n)) (min (length fst) (length snd));
385
386 /* Merges two lists of the same size together. If the sizes aren't the same
387 the merging stops at the shortest.
388
389 Type: zipLists :: [a] -> [b] -> [{ fst :: a; snd :: b; }]
390
391 Example:
392 zipLists [ 1 2 ] [ "a" "b" ]
393 => [ { fst = 1; snd = "a"; } { fst = 2; snd = "b"; } ]
394 */
395 zipLists = zipListsWith (fst: snd: { inherit fst snd; });
396
397 /* Reverse the order of the elements of a list.
398
399 Type: reverseList :: [a] -> [a]
400
401 Example:
402
403 reverseList [ "b" "o" "j" ]
404 => [ "j" "o" "b" ]
405 */
406 reverseList = xs:
407 let l = length xs; in genList (n: elemAt xs (l - n - 1)) l;
408
409 /* Depth-First Search (DFS) for lists `list != []`.
410
411 `before a b == true` means that `b` depends on `a` (there's an
412 edge from `b` to `a`).
413
414 Example:
415 listDfs true hasPrefix [ "/home/user" "other" "/" "/home" ]
416 == { minimal = "/"; # minimal element
417 visited = [ "/home/user" ]; # seen elements (in reverse order)
418 rest = [ "/home" "other" ]; # everything else
419 }
420
421 listDfs true hasPrefix [ "/home/user" "other" "/" "/home" "/" ]
422 == { cycle = "/"; # cycle encountered at this element
423 loops = [ "/" ]; # and continues to these elements
424 visited = [ "/" "/home/user" ]; # elements leading to the cycle (in reverse order)
425 rest = [ "/home" "other" ]; # everything else
426
427 */
428 listDfs = stopOnCycles: before: list:
429 let
430 dfs' = us: visited: rest:
431 let
432 c = filter (x: before x us) visited;
433 b = partition (x: before x us) rest;
434 in if stopOnCycles && (length c > 0)
435 then { cycle = us; loops = c; inherit visited rest; }
436 else if length b.right == 0
437 then # nothing is before us
438 { minimal = us; inherit visited rest; }
439 else # grab the first one before us and continue
440 dfs' (head b.right)
441 ([ us ] ++ visited)
442 (tail b.right ++ b.wrong);
443 in dfs' (head list) [] (tail list);
444
445 /* Sort a list based on a partial ordering using DFS. This
446 implementation is O(N^2), if your ordering is linear, use `sort`
447 instead.
448
449 `before a b == true` means that `b` should be after `a`
450 in the result.
451
452 Example:
453
454 toposort hasPrefix [ "/home/user" "other" "/" "/home" ]
455 == { result = [ "/" "/home" "/home/user" "other" ]; }
456
457 toposort hasPrefix [ "/home/user" "other" "/" "/home" "/" ]
458 == { cycle = [ "/home/user" "/" "/" ]; # path leading to a cycle
459 loops = [ "/" ]; } # loops back to these elements
460
461 toposort hasPrefix [ "other" "/home/user" "/home" "/" ]
462 == { result = [ "other" "/" "/home" "/home/user" ]; }
463
464 toposort (a: b: a < b) [ 3 2 1 ] == { result = [ 1 2 3 ]; }
465
466 */
467 toposort = before: list:
468 let
469 dfsthis = listDfs true before list;
470 toporest = toposort before (dfsthis.visited ++ dfsthis.rest);
471 in
472 if length list < 2
473 then # finish
474 { result = list; }
475 else if dfsthis ? cycle
476 then # there's a cycle, starting from the current vertex, return it
477 { cycle = reverseList ([ dfsthis.cycle ] ++ dfsthis.visited);
478 inherit (dfsthis) loops; }
479 else if toporest ? cycle
480 then # there's a cycle somewhere else in the graph, return it
481 toporest
482 # Slow, but short. Can be made a bit faster with an explicit stack.
483 else # there are no cycles
484 { result = [ dfsthis.minimal ] ++ toporest.result; };
485
486 /* Sort a list based on a comparator function which compares two
487 elements and returns true if the first argument is strictly below
488 the second argument. The returned list is sorted in an increasing
489 order. The implementation does a quick-sort.
490
491 Example:
492 sort (a: b: a < b) [ 5 3 7 ]
493 => [ 3 5 7 ]
494 */
495 sort = builtins.sort or (
496 strictLess: list:
497 let
498 len = length list;
499 first = head list;
500 pivot' = n: acc@{ left, right }: let el = elemAt list n; next = pivot' (n + 1); in
501 if n == len
502 then acc
503 else if strictLess first el
504 then next { inherit left; right = [ el ] ++ right; }
505 else
506 next { left = [ el ] ++ left; inherit right; };
507 pivot = pivot' 1 { left = []; right = []; };
508 in
509 if len < 2 then list
510 else (sort strictLess pivot.left) ++ [ first ] ++ (sort strictLess pivot.right));
511
512 /* Compare two lists element-by-element.
513
514 Example:
515 compareLists compare [] []
516 => 0
517 compareLists compare [] [ "a" ]
518 => -1
519 compareLists compare [ "a" ] []
520 => 1
521 compareLists compare [ "a" "b" ] [ "a" "c" ]
522 => -1
523 */
524 compareLists = cmp: a: b:
525 if a == []
526 then if b == []
527 then 0
528 else -1
529 else if b == []
530 then 1
531 else let rel = cmp (head a) (head b); in
532 if rel == 0
533 then compareLists cmp (tail a) (tail b)
534 else rel;
535
536 /* Sort list using "Natural sorting".
537 Numeric portions of strings are sorted in numeric order.
538
539 Example:
540 naturalSort ["disk11" "disk8" "disk100" "disk9"]
541 => ["disk8" "disk9" "disk11" "disk100"]
542 naturalSort ["10.46.133.149" "10.5.16.62" "10.54.16.25"]
543 => ["10.5.16.62" "10.46.133.149" "10.54.16.25"]
544 naturalSort ["v0.2" "v0.15" "v0.0.9"]
545 => [ "v0.0.9" "v0.2" "v0.15" ]
546 */
547 naturalSort = lst:
548 let
549 vectorise = s: map (x: if isList x then toInt (head x) else x) (builtins.split "(0|[1-9][0-9]*)" s);
550 prepared = map (x: [ (vectorise x) x ]) lst; # remember vectorised version for O(n) regex splits
551 less = a: b: (compareLists compare (head a) (head b)) < 0;
552 in
553 map (x: elemAt x 1) (sort less prepared);
554
555 /* Return the first (at most) N elements of a list.
556
557 Type: take :: int -> [a] -> [a]
558
559 Example:
560 take 2 [ "a" "b" "c" "d" ]
561 => [ "a" "b" ]
562 take 2 [ ]
563 => [ ]
564 */
565 take =
566 # Number of elements to take
567 count: sublist 0 count;
568
569 /* Remove the first (at most) N elements of a list.
570
571 Type: drop :: int -> [a] -> [a]
572
573 Example:
574 drop 2 [ "a" "b" "c" "d" ]
575 => [ "c" "d" ]
576 drop 2 [ ]
577 => [ ]
578 */
579 drop =
580 # Number of elements to drop
581 count:
582 # Input list
583 list: sublist count (length list) list;
584
585 /* Return a list consisting of at most `count` elements of `list`,
586 starting at index `start`.
587
588 Type: sublist :: int -> int -> [a] -> [a]
589
590 Example:
591 sublist 1 3 [ "a" "b" "c" "d" "e" ]
592 => [ "b" "c" "d" ]
593 sublist 1 3 [ ]
594 => [ ]
595 */
596 sublist =
597 # Index at which to start the sublist
598 start:
599 # Number of elements to take
600 count:
601 # Input list
602 list:
603 let len = length list; in
604 genList
605 (n: elemAt list (n + start))
606 (if start >= len then 0
607 else if start + count > len then len - start
608 else count);
609
610 /* Return the last element of a list.
611
612 This function throws an error if the list is empty.
613
614 Type: last :: [a] -> a
615
616 Example:
617 last [ 1 2 3 ]
618 => 3
619 */
620 last = list:
621 assert lib.assertMsg (list != []) "lists.last: list must not be empty!";
622 elemAt list (length list - 1);
623
624 /* Return all elements but the last.
625
626 This function throws an error if the list is empty.
627
628 Type: init :: [a] -> [a]
629
630 Example:
631 init [ 1 2 3 ]
632 => [ 1 2 ]
633 */
634 init = list:
635 assert lib.assertMsg (list != []) "lists.init: list must not be empty!";
636 take (length list - 1) list;
637
638
639 /* Return the image of the cross product of some lists by a function.
640
641 Example:
642 crossLists (x:y: "${toString x}${toString y}") [[1 2] [3 4]]
643 => [ "13" "14" "23" "24" ]
644 */
645 crossLists = builtins.trace
646 "lib.crossLists is deprecated, use lib.cartesianProductOfSets instead"
647 (f: foldl (fs: args: concatMap (f: map f args) fs) [f]);
648
649
650 /* Remove duplicate elements from the list. O(n^2) complexity.
651
652 Type: unique :: [a] -> [a]
653
654 Example:
655 unique [ 3 2 3 4 ]
656 => [ 3 2 4 ]
657 */
658 unique = foldl' (acc: e: if elem e acc then acc else acc ++ [ e ]) [];
659
660 /* Intersects list 'e' and another list. O(nm) complexity.
661
662 Example:
663 intersectLists [ 1 2 3 ] [ 6 3 2 ]
664 => [ 3 2 ]
665 */
666 intersectLists = e: filter (x: elem x e);
667
668 /* Subtracts list 'e' from another list. O(nm) complexity.
669
670 Example:
671 subtractLists [ 3 2 ] [ 1 2 3 4 5 3 ]
672 => [ 1 4 5 ]
673 */
674 subtractLists = e: filter (x: !(elem x e));
675
676 /* Test if two lists have no common element.
677 It should be slightly more efficient than (intersectLists a b == [])
678 */
679 mutuallyExclusive = a: b: length a == 0 || !(any (x: elem x a) b);
680
681}