1ListLabels(3)                    OCaml library                   ListLabels(3)
2
3
4

NAME

6       ListLabels - List operations.
7

Module

9       Module   ListLabels
10

Documentation

12       Module ListLabels
13        : sig end
14
15
16       List operations.
17
18       Some  functions  are  flagged  as not tail-recursive.  A tail-recursive
19       function uses constant stack space, while a non-tail-recursive function
20       uses stack space proportional to the length of its list argument, which
21       can be a problem with very long lists.  When the function takes several
22       list  arguments,  an  approximate  formula  giving stack usage (in some
23       unspecified constant unit) is shown in parentheses.
24
25       The above considerations can usually be ignored if your lists  are  not
26       longer than about 10000 elements.
27
28
29
30
31
32
33
34       val length : 'a list -> int
35
36       Return the length (number of elements) of the given list.
37
38
39
40
41       val hd : 'a list -> 'a
42
43       Return  the  first  element  of the given list. Raise Failure hd if the
44       list is empty.
45
46
47
48
49       val tl : 'a list -> 'a list
50
51       Return the given list without its first element. Raise  Failure  tl  if
52       the list is empty.
53
54
55
56
57       val nth : 'a list -> int -> 'a
58
59       Return  the n-th element of the given list.  The first element (head of
60       the list) is at position 0.  Raise Failure  nth  if  the  list  is  too
61       short.
62
63
64
65
66       val rev : 'a list -> 'a list
67
68       List reversal.
69
70
71
72
73       val append : 'a list -> 'a list -> 'a list
74
75       Catenate two lists.  Same function as the infix operator @ .  Not tail-
76       recursive (length of the first argument).  The @ operator is not  tail-
77       recursive either.
78
79
80
81
82       val rev_append : 'a list -> 'a list -> 'a list
83
84
85       List.rev_append  l1 l2 reverses l1 and concatenates it to l2 .  This is
86       equivalent to ListLabels.rev l1 @ l2 , but rev_append is tail-recursive
87       and more efficient.
88
89
90
91
92       val concat : 'a list list -> 'a list
93
94       Concatenate  a  list of lists.  Not tail-recursive (length of the argu‐
95       ment + length of the longest sub-list).
96
97
98
99
100       val flatten : 'a list list -> 'a list
101
102       Flatten a list of lists.  Not tail-recursive (length of the argument  +
103       length of the longest sub-list).
104
105
106
107
108
109       === Iterators ===
110
111
112       val iter : f:('a -> unit) -> 'a list -> unit
113
114
115       List.iter  f  [a1; ...; an] applies function f in turn to a1; ...; an .
116       It is equivalent to begin f a1; f a2; ...; f an; () end .
117
118
119
120
121       val map : f:('a -> 'b) -> 'a list -> 'b list
122
123
124       List.map f [a1; ...; an] applies function f to a1, ..., an , and builds
125       the  list [f a1; ...; f an] with the results returned by f .  Not tail-
126       recursive.
127
128
129
130
131       val rev_map : f:('a -> 'b) -> 'a list -> 'b list
132
133
134       List.rev_map f l gives the same  result  as  ListLabels.rev  (  ListLa‐
135       bels.map f l) , but is tail-recursive and more efficient.
136
137
138
139
140       val fold_left : f:('a -> 'b -> 'a) -> init:'a -> 'b list -> 'a
141
142
143       List.fold_left f a [b1; ...; bn] is f (... (f (f a b1) b2) ...) bn .
144
145
146
147
148       val fold_right : f:('a -> 'b -> 'b) -> 'a list -> init:'b -> 'b
149
150
151       List.fold_right  f [a1; ...; an] b is f a1 (f a2 (... (f an b) ...))  .
152       Not tail-recursive.
153
154
155
156
157
158       === Iterators on two lists ===
159
160
161       val iter2 : f:('a -> 'b -> unit) -> 'a list -> 'b list -> unit
162
163
164       List.iter2 f [a1; ...; an] [b1; ...; bn] calls in turn f a1 b1; ...;  f
165       an  bn  .   Raise  Invalid_argument  if  the  two  lists have different
166       lengths.
167
168
169
170
171       val map2 : f:('a -> 'b -> 'c) -> 'a list -> 'b list -> 'c list
172
173
174       List.map2 f [a1; ...; an] [b1; ...; bn] is [f a1 b1; ...; f  an  bn]  .
175       Raise  Invalid_argument  if  the two lists have different lengths.  Not
176       tail-recursive.
177
178
179
180
181       val rev_map2 : f:('a -> 'b -> 'c) -> 'a list -> 'b list -> 'c list
182
183
184       List.rev_map2 f l gives the same result  as  ListLabels.rev  (  ListLa‐
185       bels.map2 f l) , but is tail-recursive and more efficient.
186
187
188
189
190       val  fold_left2  : f:('a -> 'b -> 'c -> 'a) -> init:'a -> 'b list -> 'c
191       list -> 'a
192
193
194       List.fold_left2 f a [b1; ...; bn] [c1; ...; cn] is f (... (f  (f  a  b1
195       c1)  b2  c2) ...) bn cn .  Raise Invalid_argument if the two lists have
196       different lengths.
197
198
199
200
201       val fold_right2 : f:('a -> 'b -> 'c -> 'c) -> 'a list  ->  'b  list  ->
202       init:'c -> 'c
203
204
205       List.fold_right2  f  [a1;  ...; an] [b1; ...; bn] c is f a1 b1 (f a2 b2
206       (... (f an bn c) ...))  .  Raise Invalid_argument if the two lists have
207       different lengths.  Not tail-recursive.
208
209
210
211
212
213       === List scanning ===
214
215
216       val for_all : f:('a -> bool) -> 'a list -> bool
217
218
219       for_all  p [a1; ...; an] checks if all elements of the list satisfy the
220       predicate p . That is, it returns (p a1) && (p a2) && ... && (p an) .
221
222
223
224
225       val exists : f:('a -> bool) -> 'a list -> bool
226
227
228       exists p [a1; ...; an] checks if at least one element of the list  sat‐
229       isfies the predicate p . That is, it returns (p a1) || (p a2) || ... ||
230       (p an) .
231
232
233
234
235       val for_all2 : f:('a -> 'b -> bool) -> 'a list -> 'b list -> bool
236
237       Same as ListLabels.for_all , but for a two-argument  predicate.   Raise
238       Invalid_argument if the two lists have different lengths.
239
240
241
242
243       val exists2 : f:('a -> 'b -> bool) -> 'a list -> 'b list -> bool
244
245       Same  as  ListLabels.exists  , but for a two-argument predicate.  Raise
246       Invalid_argument if the two lists have different lengths.
247
248
249
250
251       val mem : 'a -> set:'a list -> bool
252
253
254       mem a l is true if and only if a is equal to an element of l .
255
256
257
258
259       val memq : 'a -> set:'a list -> bool
260
261       Same as ListLabels.mem , but uses physical equality instead  of  struc‐
262       tural equality to compare list elements.
263
264
265
266
267
268       === List searching ===
269
270
271       val find : f:('a -> bool) -> 'a list -> 'a
272
273
274       find  p  l  returns  the first element of the list l that satisfies the
275       predicate p .  Raise Not_found if there is no value that satisfies p in
276       the list l .
277
278
279
280
281       val filter : f:('a -> bool) -> 'a list -> 'a list
282
283
284       filter  p  l  returns  all  the elements of the list l that satisfy the
285       predicate p .  The order of the elements in  the  input  list  is  pre‐
286       served.
287
288
289
290
291       val find_all : f:('a -> bool) -> 'a list -> 'a list
292
293
294       find_all is another name for ListLabels.filter .
295
296
297
298
299       val partition : f:('a -> bool) -> 'a list -> 'a list * 'a list
300
301
302       partition  p  l returns a pair of lists (l1, l2) , where l1 is the list
303       of all the elements of l that satisfy the predicate p , and l2  is  the
304       list of all the elements of l that do not satisfy p .  The order of the
305       elements in the input list is preserved.
306
307
308
309
310
311       === Association lists ===
312
313
314       val assoc : 'a -> ('a * 'b) list -> 'b
315
316
317       assoc a l returns the value associated with key a in the list of  pairs
318       l  .  That  is, assoc a [ ...; (a,b); ...] = b if (a,b) is the leftmost
319       binding of a in list l .  Raise Not_found if there is no value  associ‐
320       ated with a in the list l .
321
322
323
324
325       val assq : 'a -> ('a * 'b) list -> 'b
326
327       Same as ListLabels.assoc , but uses physical equality instead of struc‐
328       tural equality to compare keys.
329
330
331
332
333       val mem_assoc : 'a -> map:('a * 'b) list -> bool
334
335       Same as ListLabels.assoc , but simply return true if a binding  exists,
336       and false if no bindings exist for the given key.
337
338
339
340
341       val mem_assq : 'a -> map:('a * 'b) list -> bool
342
343       Same  as  ListLabels.mem_assoc  , but uses physical equality instead of
344       structural equality to compare keys.
345
346
347
348
349       val remove_assoc : 'a -> ('a * 'b) list -> ('a * 'b) list
350
351
352       remove_assoc a l returns the list of pairs l  without  the  first  pair
353       with key a , if any.  Not tail-recursive.
354
355
356
357
358       val remove_assq : 'a -> ('a * 'b) list -> ('a * 'b) list
359
360       Same  as ListLabels.remove_assq , but uses physical equality instead of
361       structural equality to compare keys.  Not tail-recursive.
362
363
364
365
366
367       === Lists of pairs ===
368
369
370       val split : ('a * 'b) list -> 'a list * 'b list
371
372       Transform a list of pairs into a pair of lists:  split  [(a1,b1);  ...;
373       (an,bn)] is ([a1; ...; an], [b1; ...; bn]) .  Not tail-recursive.
374
375
376
377
378       val combine : 'a list -> 'b list -> ('a * 'b) list
379
380       Transform  a  pair of lists into a list of pairs: combine [a1; ...; an]
381       [b1; ...; bn] is [(a1,b1); ...; (an,bn)] .  Raise  Invalid_argument  if
382       the two lists have different lengths.  Not tail-recursive.
383
384
385
386
387
388       === Sorting ===
389
390
391       val sort : cmp:('a -> 'a -> int) -> 'a list -> 'a list
392
393       Sort  a  list  in  increasing order according to a comparison function.
394       The comparison function must return 0 if it arguments compare as equal,
395       a  positive  integer if the first is greater, and a negative integer if
396       the first is smaller.  For example, the compare function is a  suitable
397       comparison function.  The resulting list is sorted in increasing order.
398       List.sort is guaranteed to run in constant heap space (in  addition  to
399       the size of the result list) and logarithmic stack space.
400
401       The  current  implementation uses Merge Sort and is the same as ListLa‐
402       bels.stable_sort .
403
404
405
406
407       val stable_sort : cmp:('a -> 'a -> int) -> 'a list -> 'a list
408
409       Same as ListLabels.sort , but the sorting algorithm is stable.
410
411       The current implementation is Merge Sort.  It  runs  in  constant  heap
412       space and logarithmic stack space.
413
414
415
416
417       val fast_sort : cmp:('a -> 'a -> int) -> 'a list -> 'a list
418
419       Same  as List.sort or List.stable_sort , whichever is faster on typical
420       input.
421
422
423
424
425       val merge : cmp:('a -> 'a -> int) -> 'a list -> 'a list -> 'a list
426
427       Merge two lists: Assuming that l1 and l2 are sorted  according  to  the
428       comparison  function  cmp  ,  merge cmp l1 l2 will return a sorted list
429       containting all the elements of l1 and l2 .  If several  elements  com‐
430       pare equal, the elements of l1 will be before the elements of l2 .  Not
431       tail-recursive (sum of the lengths of the arguments).
432
433
434
435
436
437
438OCamldoc                          2007-05-24                     ListLabels(3)