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