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