pyrox.dev
1/* General list operations. */
2{ lib }:
3let
4 inherit (lib.strings) toInt;
5 inherit (lib.trivial) compare min id;
6 inherit (lib.attrsets) mapAttrs;
7in
8rec {
9
10 inherit (builtins) head tail length isList elemAt concatLists filter elem genList map;
11
12 /* Create a list consisting of a single element. `singleton x` is
13 sometimes more convenient with respect to indentation than `[x]`
14 when x spans multiple lines.
15
16 Type: singleton :: a -> [a]
17
18 Example:
19 singleton "foo"
20 => [ "foo" ]
21 */
22 singleton = x: [x];
23
24 /* Apply the function to each element in the list. Same as `map`, but arguments
25 flipped.
26
27 Type: forEach :: [a] -> (a -> b) -> [b]
28
29 Example:
30 forEach [ 1 2 ] (x:
31 toString x
32 )
33 => [ "1" "2" ]
34 */
35 forEach = xs: f: map f xs;
36
37 /* “right fold” a binary function `op` between successive elements of
38 `list` with `nul` as the starting value, i.e.,
39 `foldr op nul [x_1 x_2 ... x_n] == op x_1 (op x_2 ... (op x_n nul))`.
40
41 Type: foldr :: (a -> b -> b) -> b -> [a] -> b
42
43 Example:
44 concat = foldr (a: b: a + b) "z"
45 concat [ "a" "b" "c" ]
46 => "abcz"
47 # different types
48 strange = foldr (int: str: toString (int + 1) + str) "a"
49 strange [ 1 2 3 4 ]
50 => "2345a"
51 */
52 foldr = op: nul: list:
53 let
54 len = length list;
55 fold' = n:
56 if n == len
57 then nul
58 else op (elemAt list n) (fold' (n + 1));
59 in fold' 0;
60
61 /* `fold` is an alias of `foldr` for historic reasons */
62 # FIXME(Profpatsch): deprecate?
63 fold = foldr;
64
65
66 /* “left fold”, like `foldr`, but from the left:
67 `foldl op nul [x_1 x_2 ... x_n] == op (... (op (op nul x_1) x_2) ... x_n)`.
68
69 Type: foldl :: (b -> a -> b) -> b -> [a] -> b
70
71 Example:
72 lconcat = foldl (a: b: a + b) "z"
73 lconcat [ "a" "b" "c" ]
74 => "zabc"
75 # different types
76 lstrange = foldl (str: int: str + toString (int + 1)) "a"
77 lstrange [ 1 2 3 4 ]
78 => "a2345"
79 */
80 foldl = op: nul: list:
81 let
82 foldl' = n:
83 if n == -1
84 then nul
85 else op (foldl' (n - 1)) (elemAt list n);
86 in foldl' (length list - 1);
87
88 /*
89 Reduce a list by applying a binary operator from left to right,
90 starting with an initial accumulator.
91
92 Before each application of the operator, the accumulator value is evaluated.
93 This behavior makes this function stricter than [`foldl`](#function-library-lib.lists.foldl).
94
95 Unlike [`builtins.foldl'`](https://nixos.org/manual/nix/unstable/language/builtins.html#builtins-foldl'),
96 the initial accumulator argument is evaluated before the first iteration.
97
98 A call like
99
100 ```nix
101 foldl' op acc₀ [ x₀ x₁ x₂ ... xₙ₋₁ xₙ ]
102 ```
103
104 is (denotationally) equivalent to the following,
105 but with the added benefit that `foldl'` itself will never overflow the stack.
106
107 ```nix
108 let
109 acc₁ = builtins.seq acc₀ (op acc₀ x₀ );
110 acc₂ = builtins.seq acc₁ (op acc₁ x₁ );
111 acc₃ = builtins.seq acc₂ (op acc₂ x₂ );
112 ...
113 accₙ = builtins.seq accₙ₋₁ (op accₙ₋₁ xₙ₋₁);
114 accₙ₊₁ = builtins.seq accₙ (op accₙ xₙ );
115 in
116 accₙ₊₁
117
118 # Or ignoring builtins.seq
119 op (op (... (op (op (op acc₀ x₀) x₁) x₂) ...) xₙ₋₁) xₙ
120 ```
121
122 Type: foldl' :: (acc -> x -> acc) -> acc -> [x] -> acc
123
124 Example:
125 foldl' (acc: x: acc + x) 0 [1 2 3]
126 => 6
127 */
128 foldl' =
129 /* The binary operation to run, where the two arguments are:
130
131 1. `acc`: The current accumulator value: Either the initial one for the first iteration, or the result of the previous iteration
132 2. `x`: The corresponding list element for this iteration
133 */
134 op:
135 # The initial accumulator value
136 acc:
137 # The list to fold
138 list:
139
140 # The builtin `foldl'` is a bit lazier than one might expect.
141 # See https://github.com/NixOS/nix/pull/7158.
142 # In particular, the initial accumulator value is not forced before the first iteration starts.
143 builtins.seq acc
144 (builtins.foldl' op acc list);
145
146 /* Map with index starting from 0
147
148 Type: imap0 :: (int -> a -> b) -> [a] -> [b]
149
150 Example:
151 imap0 (i: v: "${v}-${toString i}") ["a" "b"]
152 => [ "a-0" "b-1" ]
153 */
154 imap0 = f: list: genList (n: f n (elemAt list n)) (length list);
155
156 /* Map with index starting from 1
157
158 Type: imap1 :: (int -> a -> b) -> [a] -> [b]
159
160 Example:
161 imap1 (i: v: "${v}-${toString i}") ["a" "b"]
162 => [ "a-1" "b-2" ]
163 */
164 imap1 = f: list: genList (n: f (n + 1) (elemAt list n)) (length list);
165
166 /* Map and concatenate the result.
167
168 Type: concatMap :: (a -> [b]) -> [a] -> [b]
169
170 Example:
171 concatMap (x: [x] ++ ["z"]) ["a" "b"]
172 => [ "a" "z" "b" "z" ]
173 */
174 concatMap = builtins.concatMap or (f: list: concatLists (map f list));
175
176 /* Flatten the argument into a single list; that is, nested lists are
177 spliced into the top-level lists.
178
179 Example:
180 flatten [1 [2 [3] 4] 5]
181 => [1 2 3 4 5]
182 flatten 1
183 => [1]
184 */
185 flatten = x:
186 if isList x
187 then concatMap (y: flatten y) x
188 else [x];
189
190 /* Remove elements equal to 'e' from a list. Useful for buildInputs.
191
192 Type: remove :: a -> [a] -> [a]
193
194 Example:
195 remove 3 [ 1 3 4 3 ]
196 => [ 1 4 ]
197 */
198 remove =
199 # Element to remove from the list
200 e: filter (x: x != e);
201
202 /* Find the sole element in the list matching the specified
203 predicate, returns `default` if no such element exists, or
204 `multiple` if there are multiple matching elements.
205
206 Type: findSingle :: (a -> bool) -> a -> a -> [a] -> a
207
208 Example:
209 findSingle (x: x == 3) "none" "multiple" [ 1 3 3 ]
210 => "multiple"
211 findSingle (x: x == 3) "none" "multiple" [ 1 3 ]
212 => 3
213 findSingle (x: x == 3) "none" "multiple" [ 1 9 ]
214 => "none"
215 */
216 findSingle =
217 # Predicate
218 pred:
219 # Default value to return if element was not found.
220 default:
221 # Default value to return if more than one element was found
222 multiple:
223 # Input list
224 list:
225 let found = filter pred list; len = length found;
226 in if len == 0 then default
227 else if len != 1 then multiple
228 else head found;
229
230 /* Find the first index in the list matching the specified
231 predicate or return `default` if no such element exists.
232
233 Type: findFirstIndex :: (a -> Bool) -> b -> [a] -> (Int | b)
234
235 Example:
236 findFirstIndex (x: x > 3) null [ 0 6 4 ]
237 => 1
238 findFirstIndex (x: x > 9) null [ 0 6 4 ]
239 => null
240 */
241 findFirstIndex =
242 # Predicate
243 pred:
244 # Default value to return
245 default:
246 # Input list
247 list:
248 let
249 # A naive recursive implementation would be much simpler, but
250 # would also overflow the evaluator stack. We use `foldl'` as a workaround
251 # because it reuses the same stack space, evaluating the function for one
252 # element after another. We can't return early, so this means that we
253 # sacrifice early cutoff, but that appears to be an acceptable cost. A
254 # clever scheme with "exponential search" is possible, but appears over-
255 # engineered for now. See https://github.com/NixOS/nixpkgs/pull/235267
256
257 # Invariant:
258 # - if index < 0 then el == elemAt list (- index - 1) and all elements before el didn't satisfy pred
259 # - if index >= 0 then pred (elemAt list index) and all elements before (elemAt list index) didn't satisfy pred
260 #
261 # We start with index -1 and the 0'th element of the list, which satisfies the invariant
262 resultIndex = foldl' (index: el:
263 if index < 0 then
264 # No match yet before the current index, we need to check the element
265 if pred el then
266 # We have a match! Turn it into the actual index to prevent future iterations from modifying it
267 - index - 1
268 else
269 # Still no match, update the index to the next element (we're counting down, so minus one)
270 index - 1
271 else
272 # There's already a match, propagate the index without evaluating anything
273 index
274 ) (-1) list;
275 in
276 if resultIndex < 0 then
277 default
278 else
279 resultIndex;
280
281 /* Find the first element in the list matching the specified
282 predicate or return `default` if no such element exists.
283
284 Type: findFirst :: (a -> bool) -> a -> [a] -> a
285
286 Example:
287 findFirst (x: x > 3) 7 [ 1 6 4 ]
288 => 6
289 findFirst (x: x > 9) 7 [ 1 6 4 ]
290 => 7
291 */
292 findFirst =
293 # Predicate
294 pred:
295 # Default value to return
296 default:
297 # Input list
298 list:
299 let
300 index = findFirstIndex pred null list;
301 in
302 if index == null then
303 default
304 else
305 elemAt list index;
306
307 /* Return true if function `pred` returns true for at least one
308 element of `list`.
309
310 Type: any :: (a -> bool) -> [a] -> bool
311
312 Example:
313 any isString [ 1 "a" { } ]
314 => true
315 any isString [ 1 { } ]
316 => false
317 */
318 any = builtins.any or (pred: foldr (x: y: if pred x then true else y) false);
319
320 /* Return true if function `pred` returns true for all elements of
321 `list`.
322
323 Type: all :: (a -> bool) -> [a] -> bool
324
325 Example:
326 all (x: x < 3) [ 1 2 ]
327 => true
328 all (x: x < 3) [ 1 2 3 ]
329 => false
330 */
331 all = builtins.all or (pred: foldr (x: y: if pred x then y else false) true);
332
333 /* Count how many elements of `list` match the supplied predicate
334 function.
335
336 Type: count :: (a -> bool) -> [a] -> int
337
338 Example:
339 count (x: x == 3) [ 3 2 3 4 6 ]
340 => 2
341 */
342 count =
343 # Predicate
344 pred: foldl' (c: x: if pred x then c + 1 else c) 0;
345
346 /* Return a singleton list or an empty list, depending on a boolean
347 value. Useful when building lists with optional elements
348 (e.g. `++ optional (system == "i686-linux") firefox`).
349
350 Type: optional :: bool -> a -> [a]
351
352 Example:
353 optional true "foo"
354 => [ "foo" ]
355 optional false "foo"
356 => [ ]
357 */
358 optional = cond: elem: if cond then [elem] else [];
359
360 /* Return a list or an empty list, depending on a boolean value.
361
362 Type: optionals :: bool -> [a] -> [a]
363
364 Example:
365 optionals true [ 2 3 ]
366 => [ 2 3 ]
367 optionals false [ 2 3 ]
368 => [ ]
369 */
370 optionals =
371 # Condition
372 cond:
373 # List to return if condition is true
374 elems: if cond then elems else [];
375
376
377 /* If argument is a list, return it; else, wrap it in a singleton
378 list. If you're using this, you should almost certainly
379 reconsider if there isn't a more "well-typed" approach.
380
381 Example:
382 toList [ 1 2 ]
383 => [ 1 2 ]
384 toList "hi"
385 => [ "hi "]
386 */
387 toList = x: if isList x then x else [x];
388
389 /* Return a list of integers from `first` up to and including `last`.
390
391 Type: range :: int -> int -> [int]
392
393 Example:
394 range 2 4
395 => [ 2 3 4 ]
396 range 3 2
397 => [ ]
398 */
399 range =
400 # First integer in the range
401 first:
402 # Last integer in the range
403 last:
404 if first > last then
405 []
406 else
407 genList (n: first + n) (last - first + 1);
408
409 /* Return a list with `n` copies of an element.
410
411 Type: replicate :: int -> a -> [a]
412
413 Example:
414 replicate 3 "a"
415 => [ "a" "a" "a" ]
416 replicate 2 true
417 => [ true true ]
418 */
419 replicate = n: elem: genList (_: elem) n;
420
421 /* Splits the elements of a list in two lists, `right` and
422 `wrong`, depending on the evaluation of a predicate.
423
424 Type: (a -> bool) -> [a] -> { right :: [a]; wrong :: [a]; }
425
426 Example:
427 partition (x: x > 2) [ 5 1 2 3 4 ]
428 => { right = [ 5 3 4 ]; wrong = [ 1 2 ]; }
429 */
430 partition = builtins.partition or (pred:
431 foldr (h: t:
432 if pred h
433 then { right = [h] ++ t.right; wrong = t.wrong; }
434 else { right = t.right; wrong = [h] ++ t.wrong; }
435 ) { right = []; wrong = []; });
436
437 /* Splits the elements of a list into many lists, using the return value of a predicate.
438 Predicate should return a string which becomes keys of attrset `groupBy` returns.
439
440 `groupBy'` allows to customise the combining function and initial value
441
442 Example:
443 groupBy (x: boolToString (x > 2)) [ 5 1 2 3 4 ]
444 => { true = [ 5 3 4 ]; false = [ 1 2 ]; }
445 groupBy (x: x.name) [ {name = "icewm"; script = "icewm &";}
446 {name = "xfce"; script = "xfce4-session &";}
447 {name = "icewm"; script = "icewmbg &";}
448 {name = "mate"; script = "gnome-session &";}
449 ]
450 => { icewm = [ { name = "icewm"; script = "icewm &"; }
451 { name = "icewm"; script = "icewmbg &"; } ];
452 mate = [ { name = "mate"; script = "gnome-session &"; } ];
453 xfce = [ { name = "xfce"; script = "xfce4-session &"; } ];
454 }
455
456 groupBy' builtins.add 0 (x: boolToString (x > 2)) [ 5 1 2 3 4 ]
457 => { true = 12; false = 3; }
458 */
459 groupBy' = op: nul: pred: lst: mapAttrs (name: foldl op nul) (groupBy pred lst);
460
461 groupBy = builtins.groupBy or (
462 pred: foldl' (r: e:
463 let
464 key = pred e;
465 in
466 r // { ${key} = (r.${key} or []) ++ [e]; }
467 ) {});
468
469 /* Merges two lists of the same size together. If the sizes aren't the same
470 the merging stops at the shortest. How both lists are merged is defined
471 by the first argument.
472
473 Type: zipListsWith :: (a -> b -> c) -> [a] -> [b] -> [c]
474
475 Example:
476 zipListsWith (a: b: a + b) ["h" "l"] ["e" "o"]
477 => ["he" "lo"]
478 */
479 zipListsWith =
480 # Function to zip elements of both lists
481 f:
482 # First list
483 fst:
484 # Second list
485 snd:
486 genList
487 (n: f (elemAt fst n) (elemAt snd n)) (min (length fst) (length snd));
488
489 /* Merges two lists of the same size together. If the sizes aren't the same
490 the merging stops at the shortest.
491
492 Type: zipLists :: [a] -> [b] -> [{ fst :: a; snd :: b; }]
493
494 Example:
495 zipLists [ 1 2 ] [ "a" "b" ]
496 => [ { fst = 1; snd = "a"; } { fst = 2; snd = "b"; } ]
497 */
498 zipLists = zipListsWith (fst: snd: { inherit fst snd; });
499
500 /* Reverse the order of the elements of a list.
501
502 Type: reverseList :: [a] -> [a]
503
504 Example:
505
506 reverseList [ "b" "o" "j" ]
507 => [ "j" "o" "b" ]
508 */
509 reverseList = xs:
510 let l = length xs; in genList (n: elemAt xs (l - n - 1)) l;
511
512 /* Depth-First Search (DFS) for lists `list != []`.
513
514 `before a b == true` means that `b` depends on `a` (there's an
515 edge from `b` to `a`).
516
517 Example:
518 listDfs true hasPrefix [ "/home/user" "other" "/" "/home" ]
519 == { minimal = "/"; # minimal element
520 visited = [ "/home/user" ]; # seen elements (in reverse order)
521 rest = [ "/home" "other" ]; # everything else
522 }
523
524 listDfs true hasPrefix [ "/home/user" "other" "/" "/home" "/" ]
525 == { cycle = "/"; # cycle encountered at this element
526 loops = [ "/" ]; # and continues to these elements
527 visited = [ "/" "/home/user" ]; # elements leading to the cycle (in reverse order)
528 rest = [ "/home" "other" ]; # everything else
529
530 */
531 listDfs = stopOnCycles: before: list:
532 let
533 dfs' = us: visited: rest:
534 let
535 c = filter (x: before x us) visited;
536 b = partition (x: before x us) rest;
537 in if stopOnCycles && (length c > 0)
538 then { cycle = us; loops = c; inherit visited rest; }
539 else if length b.right == 0
540 then # nothing is before us
541 { minimal = us; inherit visited rest; }
542 else # grab the first one before us and continue
543 dfs' (head b.right)
544 ([ us ] ++ visited)
545 (tail b.right ++ b.wrong);
546 in dfs' (head list) [] (tail list);
547
548 /* Sort a list based on a partial ordering using DFS. This
549 implementation is O(N^2), if your ordering is linear, use `sort`
550 instead.
551
552 `before a b == true` means that `b` should be after `a`
553 in the result.
554
555 Example:
556
557 toposort hasPrefix [ "/home/user" "other" "/" "/home" ]
558 == { result = [ "/" "/home" "/home/user" "other" ]; }
559
560 toposort hasPrefix [ "/home/user" "other" "/" "/home" "/" ]
561 == { cycle = [ "/home/user" "/" "/" ]; # path leading to a cycle
562 loops = [ "/" ]; } # loops back to these elements
563
564 toposort hasPrefix [ "other" "/home/user" "/home" "/" ]
565 == { result = [ "other" "/" "/home" "/home/user" ]; }
566
567 toposort (a: b: a < b) [ 3 2 1 ] == { result = [ 1 2 3 ]; }
568
569 */
570 toposort = before: list:
571 let
572 dfsthis = listDfs true before list;
573 toporest = toposort before (dfsthis.visited ++ dfsthis.rest);
574 in
575 if length list < 2
576 then # finish
577 { result = list; }
578 else if dfsthis ? cycle
579 then # there's a cycle, starting from the current vertex, return it
580 { cycle = reverseList ([ dfsthis.cycle ] ++ dfsthis.visited);
581 inherit (dfsthis) loops; }
582 else if toporest ? cycle
583 then # there's a cycle somewhere else in the graph, return it
584 toporest
585 # Slow, but short. Can be made a bit faster with an explicit stack.
586 else # there are no cycles
587 { result = [ dfsthis.minimal ] ++ toporest.result; };
588
589 /* Sort a list based on a comparator function which compares two
590 elements and returns true if the first argument is strictly below
591 the second argument. The returned list is sorted in an increasing
592 order. The implementation does a quick-sort.
593
594 Example:
595 sort (a: b: a < b) [ 5 3 7 ]
596 => [ 3 5 7 ]
597 */
598 sort = builtins.sort or (
599 strictLess: list:
600 let
601 len = length list;
602 first = head list;
603 pivot' = n: acc@{ left, right }: let el = elemAt list n; next = pivot' (n + 1); in
604 if n == len
605 then acc
606 else if strictLess first el
607 then next { inherit left; right = [ el ] ++ right; }
608 else
609 next { left = [ el ] ++ left; inherit right; };
610 pivot = pivot' 1 { left = []; right = []; };
611 in
612 if len < 2 then list
613 else (sort strictLess pivot.left) ++ [ first ] ++ (sort strictLess pivot.right));
614
615 /* Compare two lists element-by-element.
616
617 Example:
618 compareLists compare [] []
619 => 0
620 compareLists compare [] [ "a" ]
621 => -1
622 compareLists compare [ "a" ] []
623 => 1
624 compareLists compare [ "a" "b" ] [ "a" "c" ]
625 => -1
626 */
627 compareLists = cmp: a: b:
628 if a == []
629 then if b == []
630 then 0
631 else -1
632 else if b == []
633 then 1
634 else let rel = cmp (head a) (head b); in
635 if rel == 0
636 then compareLists cmp (tail a) (tail b)
637 else rel;
638
639 /* Sort list using "Natural sorting".
640 Numeric portions of strings are sorted in numeric order.
641
642 Example:
643 naturalSort ["disk11" "disk8" "disk100" "disk9"]
644 => ["disk8" "disk9" "disk11" "disk100"]
645 naturalSort ["10.46.133.149" "10.5.16.62" "10.54.16.25"]
646 => ["10.5.16.62" "10.46.133.149" "10.54.16.25"]
647 naturalSort ["v0.2" "v0.15" "v0.0.9"]
648 => [ "v0.0.9" "v0.2" "v0.15" ]
649 */
650 naturalSort = lst:
651 let
652 vectorise = s: map (x: if isList x then toInt (head x) else x) (builtins.split "(0|[1-9][0-9]*)" s);
653 prepared = map (x: [ (vectorise x) x ]) lst; # remember vectorised version for O(n) regex splits
654 less = a: b: (compareLists compare (head a) (head b)) < 0;
655 in
656 map (x: elemAt x 1) (sort less prepared);
657
658 /* Return the first (at most) N elements of a list.
659
660 Type: take :: int -> [a] -> [a]
661
662 Example:
663 take 2 [ "a" "b" "c" "d" ]
664 => [ "a" "b" ]
665 take 2 [ ]
666 => [ ]
667 */
668 take =
669 # Number of elements to take
670 count: sublist 0 count;
671
672 /* Remove the first (at most) N elements of a list.
673
674 Type: drop :: int -> [a] -> [a]
675
676 Example:
677 drop 2 [ "a" "b" "c" "d" ]
678 => [ "c" "d" ]
679 drop 2 [ ]
680 => [ ]
681 */
682 drop =
683 # Number of elements to drop
684 count:
685 # Input list
686 list: sublist count (length list) list;
687
688 /* Whether the first list is a prefix of the second list.
689
690 Type: hasPrefix :: [a] -> [a] -> bool
691
692 Example:
693 hasPrefix [ 1 2 ] [ 1 2 3 4 ]
694 => true
695 hasPrefix [ 0 1 ] [ 1 2 3 4 ]
696 => false
697 */
698 hasPrefix =
699 list1:
700 list2:
701 take (length list1) list2 == list1;
702
703 /* Remove the first list as a prefix from the second list.
704 Error if the first list isn't a prefix of the second list.
705
706 Type: removePrefix :: [a] -> [a] -> [a]
707
708 Example:
709 removePrefix [ 1 2 ] [ 1 2 3 4 ]
710 => [ 3 4 ]
711 removePrefix [ 0 1 ] [ 1 2 3 4 ]
712 => <error>
713 */
714 removePrefix =
715 list1:
716 list2:
717 if hasPrefix list1 list2 then
718 drop (length list1) list2
719 else
720 throw "lib.lists.removePrefix: First argument is not a list prefix of the second argument";
721
722 /* Return a list consisting of at most `count` elements of `list`,
723 starting at index `start`.
724
725 Type: sublist :: int -> int -> [a] -> [a]
726
727 Example:
728 sublist 1 3 [ "a" "b" "c" "d" "e" ]
729 => [ "b" "c" "d" ]
730 sublist 1 3 [ ]
731 => [ ]
732 */
733 sublist =
734 # Index at which to start the sublist
735 start:
736 # Number of elements to take
737 count:
738 # Input list
739 list:
740 let len = length list; in
741 genList
742 (n: elemAt list (n + start))
743 (if start >= len then 0
744 else if start + count > len then len - start
745 else count);
746
747 /* The common prefix of two lists.
748
749 Type: commonPrefix :: [a] -> [a] -> [a]
750
751 Example:
752 commonPrefix [ 1 2 3 4 5 6 ] [ 1 2 4 8 ]
753 => [ 1 2 ]
754 commonPrefix [ 1 2 3 ] [ 1 2 3 4 5 ]
755 => [ 1 2 3 ]
756 commonPrefix [ 1 2 3 ] [ 4 5 6 ]
757 => [ ]
758 */
759 commonPrefix =
760 list1:
761 list2:
762 let
763 # Zip the lists together into a list of booleans whether each element matches
764 matchings = zipListsWith (fst: snd: fst != snd) list1 list2;
765 # Find the first index where the elements don't match,
766 # which will then also be the length of the common prefix.
767 # If all elements match, we fall back to the length of the zipped list,
768 # which is the same as the length of the smaller list.
769 commonPrefixLength = findFirstIndex id (length matchings) matchings;
770 in
771 take commonPrefixLength list1;
772
773 /* Return the last element of a list.
774
775 This function throws an error if the list is empty.
776
777 Type: last :: [a] -> a
778
779 Example:
780 last [ 1 2 3 ]
781 => 3
782 */
783 last = list:
784 assert lib.assertMsg (list != []) "lists.last: list must not be empty!";
785 elemAt list (length list - 1);
786
787 /* Return all elements but the last.
788
789 This function throws an error if the list is empty.
790
791 Type: init :: [a] -> [a]
792
793 Example:
794 init [ 1 2 3 ]
795 => [ 1 2 ]
796 */
797 init = list:
798 assert lib.assertMsg (list != []) "lists.init: list must not be empty!";
799 take (length list - 1) list;
800
801
802 /* Return the image of the cross product of some lists by a function.
803
804 Example:
805 crossLists (x:y: "${toString x}${toString y}") [[1 2] [3 4]]
806 => [ "13" "14" "23" "24" ]
807 */
808 crossLists = builtins.trace
809 "lib.crossLists is deprecated, use lib.cartesianProductOfSets instead"
810 (f: foldl (fs: args: concatMap (f: map f args) fs) [f]);
811
812
813 /* Remove duplicate elements from the list. O(n^2) complexity.
814
815 Type: unique :: [a] -> [a]
816
817 Example:
818 unique [ 3 2 3 4 ]
819 => [ 3 2 4 ]
820 */
821 unique = foldl' (acc: e: if elem e acc then acc else acc ++ [ e ]) [];
822
823 /* Check if list contains only unique elements. O(n^2) complexity.
824
825 Type: allUnique :: [a] -> bool
826
827 Example:
828 allUnique [ 3 2 3 4 ]
829 => false
830 allUnique [ 3 2 4 1 ]
831 => true
832 */
833 allUnique = list: (length (unique list) == length list);
834
835
836 /* Intersects list 'e' and another list. O(nm) complexity.
837
838 Example:
839 intersectLists [ 1 2 3 ] [ 6 3 2 ]
840 => [ 3 2 ]
841 */
842 intersectLists = e: filter (x: elem x e);
843
844 /* Subtracts list 'e' from another list. O(nm) complexity.
845
846 Example:
847 subtractLists [ 3 2 ] [ 1 2 3 4 5 3 ]
848 => [ 1 4 5 ]
849 */
850 subtractLists = e: filter (x: !(elem x e));
851
852 /* Test if two lists have no common element.
853 It should be slightly more efficient than (intersectLists a b == [])
854 */
855 mutuallyExclusive = a: b: length a == 0 || !(any (x: elem x a) b);
856
857}