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