pyrox.dev
1# General list operations.
2
3with import ./trivial.nix;
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 /* Return the first (at most) N elements of a list.
389
390 Example:
391 take 2 [ "a" "b" "c" "d" ]
392 => [ "a" "b" ]
393 take 2 [ ]
394 => [ ]
395 */
396 take = count: sublist 0 count;
397
398 /* Remove the first (at most) N elements of a list.
399
400 Example:
401 drop 2 [ "a" "b" "c" "d" ]
402 => [ "c" "d" ]
403 drop 2 [ ]
404 => [ ]
405 */
406 drop = count: list: sublist count (length list) list;
407
408 /* Return a list consisting of at most ‘count’ elements of ‘list’,
409 starting at index ‘start’.
410
411 Example:
412 sublist 1 3 [ "a" "b" "c" "d" "e" ]
413 => [ "b" "c" "d" ]
414 sublist 1 3 [ ]
415 => [ ]
416 */
417 sublist = start: count: list:
418 let len = length list; in
419 genList
420 (n: elemAt list (n + start))
421 (if start >= len then 0
422 else if start + count > len then len - start
423 else count);
424
425 /* Return the last element of a list.
426
427 Example:
428 last [ 1 2 3 ]
429 => 3
430 */
431 last = list:
432 assert list != []; elemAt list (length list - 1);
433
434 /* Return all elements but the last
435
436 Example:
437 init [ 1 2 3 ]
438 => [ 1 2 ]
439 */
440 init = list: assert list != []; take (length list - 1) list;
441
442
443 /* FIXME(zimbatm) Not used anywhere
444 */
445 crossLists = f: foldl (fs: args: concatMap (f: map f args) fs) [f];
446
447
448 /* Remove duplicate elements from the list. O(n^2) complexity.
449
450 Example:
451
452 unique [ 3 2 3 4 ]
453 => [ 3 2 4 ]
454 */
455 unique = list:
456 if list == [] then
457 []
458 else
459 let
460 x = head list;
461 xs = unique (drop 1 list);
462 in [x] ++ remove x xs;
463
464 /* Intersects list 'e' and another list. O(nm) complexity.
465
466 Example:
467 intersectLists [ 1 2 3 ] [ 6 3 2 ]
468 => [ 3 2 ]
469 */
470 intersectLists = e: filter (x: elem x e);
471
472 /* Subtracts list 'e' from another list. O(nm) complexity.
473
474 Example:
475 subtractLists [ 3 2 ] [ 1 2 3 4 5 3 ]
476 => [ 1 4 5 ]
477 */
478 subtractLists = e: filter (x: !(elem x e));
479
480 /* Test if two lists have no common element.
481 It should be slightly more efficient than (intersectLists a b == [])
482 */
483 mutuallyExclusive = a: b:
484 (builtins.length a) == 0 ||
485 (!(builtins.elem (builtins.head a) b) &&
486 mutuallyExclusive (builtins.tail a) b);
487
488}