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