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
10 # Create a list consisting of a single element. `singleton x' is
11 # sometimes more convenient with respect to indentation than `[x]'
12 # when x spans multiple lines.
13 singleton = x: [x];
14
15
16 # "Fold" a binary function `op' between successive elements of
17 # `list' with `nul' as the starting value, i.e., `fold op nul [x_1
18 # x_2 ... x_n] == op x_1 (op x_2 ... (op x_n nul))'. (This is
19 # Haskell's foldr).
20 fold = op: nul: list:
21 let
22 len = length list;
23 fold' = n:
24 if n == len
25 then nul
26 else op (elemAt list n) (fold' (n + 1));
27 in fold' 0;
28
29 # Left fold: `fold op nul [x_1 x_2 ... x_n] == op (... (op (op nul
30 # x_1) x_2) ... x_n)'.
31 foldl = op: nul: list:
32 let
33 len = length list;
34 foldl' = n:
35 if n == -1
36 then nul
37 else op (foldl' (n - 1)) (elemAt list n);
38 in foldl' (length list - 1);
39
40
41 # Strict version of foldl.
42 foldl' = builtins.foldl' or foldl;
43
44
45 # Map with index: `imap (i: v: "${v}-${toString i}") ["a" "b"] ==
46 # ["a-1" "b-2"]'. FIXME: why does this start to count at 1?
47 imap =
48 if builtins ? genList then
49 f: list: genList (n: f (n + 1) (elemAt list n)) (length list)
50 else
51 f: list:
52 let
53 len = length list;
54 imap' = n:
55 if n == len
56 then []
57 else [ (f (n + 1) (elemAt list n)) ] ++ imap' (n + 1);
58 in imap' 0;
59
60
61 # Map and concatenate the result.
62 concatMap = f: list: concatLists (map f list);
63
64
65 # Flatten the argument into a single list; that is, nested lists are
66 # spliced into the top-level lists. E.g., `flatten [1 [2 [3] 4] 5]
67 # == [1 2 3 4 5]' and `flatten 1 == [1]'.
68 flatten = x:
69 if isList x
70 then foldl' (x: y: x ++ (flatten y)) [] x
71 else [x];
72
73
74 # Remove elements equal to 'e' from a list. Useful for buildInputs.
75 remove = e: filter (x: x != e);
76
77
78 # Find the sole element in the list matching the specified
79 # predicate, returns `default' if no such element exists, or
80 # `multiple' if there are multiple matching elements.
81 findSingle = pred: default: multiple: list:
82 let found = filter pred list; len = length found;
83 in if len == 0 then default
84 else if len != 1 then multiple
85 else head found;
86
87
88 # Find the first element in the list matching the specified
89 # predicate or returns `default' if no such element exists.
90 findFirst = pred: default: list:
91 let found = filter pred list;
92 in if found == [] then default else head found;
93
94
95 # Return true iff function `pred' returns true for at least element
96 # of `list'.
97 any = builtins.any or (pred: fold (x: y: if pred x then true else y) false);
98
99
100 # Return true iff function `pred' returns true for all elements of
101 # `list'.
102 all = builtins.all or (pred: fold (x: y: if pred x then y else false) true);
103
104
105 # Count how many times function `pred' returns true for the elements
106 # of `list'.
107 count = pred: foldl' (c: x: if pred x then c + 1 else c) 0;
108
109
110 # Return a singleton list or an empty list, depending on a boolean
111 # value. Useful when building lists with optional elements
112 # (e.g. `++ optional (system == "i686-linux") flashplayer').
113 optional = cond: elem: if cond then [elem] else [];
114
115
116 # Return a list or an empty list, dependening on a boolean value.
117 optionals = cond: elems: if cond then elems else [];
118
119
120 # If argument is a list, return it; else, wrap it in a singleton
121 # list. If you're using this, you should almost certainly
122 # reconsider if there isn't a more "well-typed" approach.
123 toList = x: if isList x then x else [x];
124
125
126 # Return a list of integers from `first' up to and including `last'.
127 range =
128 if builtins ? genList then
129 first: last:
130 if first > last
131 then []
132 else genList (n: first + n) (last - first + 1)
133 else
134 first: last:
135 if last < first
136 then []
137 else [first] ++ range (first + 1) last;
138
139
140 # Partition the elements of a list in two lists, `right' and
141 # `wrong', depending on the evaluation of a predicate.
142 partition = pred:
143 fold (h: t:
144 if pred h
145 then { right = [h] ++ t.right; wrong = t.wrong; }
146 else { right = t.right; wrong = [h] ++ t.wrong; }
147 ) { right = []; wrong = []; };
148
149
150 zipListsWith =
151 if builtins ? genList then
152 f: fst: snd: genList (n: f (elemAt fst n) (elemAt snd n)) (min (length fst) (length snd))
153 else
154 f: fst: snd:
155 let
156 len = min (length fst) (length snd);
157 zipListsWith' = n:
158 if n != len then
159 [ (f (elemAt fst n) (elemAt snd n)) ]
160 ++ zipListsWith' (n + 1)
161 else [];
162 in zipListsWith' 0;
163
164 zipLists = zipListsWith (fst: snd: { inherit fst snd; });
165
166
167 # Reverse the order of the elements of a list.
168 reverseList =
169 if builtins ? genList then
170 xs: let l = length xs; in genList (n: elemAt xs (l - n - 1)) l
171 else
172 fold (e: acc: acc ++ [ e ]) [];
173
174
175 # Sort a list based on a comparator function which compares two
176 # elements and returns true if the first argument is strictly below
177 # the second argument. The returned list is sorted in an increasing
178 # order. The implementation does a quick-sort.
179 sort = builtins.sort or (
180 strictLess: list:
181 let
182 len = length list;
183 first = head list;
184 pivot' = n: acc@{ left, right }: let el = elemAt list n; next = pivot' (n + 1); in
185 if n == len
186 then acc
187 else if strictLess first el
188 then next { inherit left; right = [ el ] ++ right; }
189 else
190 next { left = [ el ] ++ left; inherit right; };
191 pivot = pivot' 1 { left = []; right = []; };
192 in
193 if len < 2 then list
194 else (sort strictLess pivot.left) ++ [ first ] ++ (sort strictLess pivot.right));
195
196
197 # Return the first (at most) N elements of a list.
198 take =
199 if builtins ? genList then
200 count: sublist 0 count
201 else
202 count: list:
203 let
204 len = length list;
205 take' = n:
206 if n == len || n == count
207 then []
208 else
209 [ (elemAt list n) ] ++ take' (n + 1);
210 in take' 0;
211
212
213 # Remove the first (at most) N elements of a list.
214 drop =
215 if builtins ? genList then
216 count: list: sublist count (length list) list
217 else
218 count: list:
219 let
220 len = length list;
221 drop' = n:
222 if n == -1 || n < count
223 then []
224 else
225 drop' (n - 1) ++ [ (elemAt list n) ];
226 in drop' (len - 1);
227
228
229 # Return a list consisting of at most ‘count’ elements of ‘list’,
230 # starting at index ‘start’.
231 sublist = start: count: list:
232 let len = length list; in
233 genList
234 (n: elemAt list (n + start))
235 (if start >= len then 0
236 else if start + count > len then len - start
237 else count);
238
239
240 # Return the last element of a list.
241 last = list:
242 assert list != []; elemAt list (length list - 1);
243
244
245 # Return all elements but the last
246 init = list: assert list != []; take (length list - 1) list;
247
248
249 deepSeqList = xs: y: if any (x: deepSeq x false) xs then y else y;
250
251
252 crossLists = f: foldl (fs: args: concatMap (f: map f args) fs) [f];
253
254
255 # Remove duplicate elements from the list. O(n^2) complexity.
256 unique = list:
257 if list == [] then
258 []
259 else
260 let
261 x = head list;
262 xs = unique (drop 1 list);
263 in [x] ++ remove x xs;
264
265
266 # Intersects list 'e' and another list. O(nm) complexity.
267 intersectLists = e: filter (x: elem x e);
268
269
270 # Subtracts list 'e' from another list. O(nm) complexity.
271 subtractLists = e: filter (x: !(elem x e));
272
273}