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.  Raise Invalid_argument List.nth if n is negative.
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
76       tail-recursive (length of the first argument).  The @ operator  is  not
77       tail-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.  The elements of the argument are all con‐
95       catenated together (in  the  same  order)  to  give  the  result.   Not
96       tail-recursive  (length  of  the  argument  +  length  of  the  longest
97       sub-list).
98
99
100
101
102       val flatten : 'a list list -> 'a list
103
104       Same as concat .  Not tail-recursive (length of the argument  +  length
105       of the longest sub-list).
106
107
108
109
110
111       === Iterators ===
112
113
114       val iter : f:('a -> unit) -> 'a list -> unit
115
116
117       List.iter  f  [a1; ...; an] applies function f in turn to a1; ...; an .
118       It is equivalent to begin f a1; f a2; ...; f an; () end .
119
120
121
122
123       val map : f:('a -> 'b) -> 'a list -> 'b list
124
125
126       List.map f [a1; ...; an] applies function f to a1, ..., an , and builds
127       the  list  [f  a1;  ...;  f  an]  with the results returned by f .  Not
128       tail-recursive.
129
130
131
132
133       val rev_map : f:('a -> 'b) -> 'a list -> 'b list
134
135
136       List.rev_map f l gives the same  result  as  ListLabels.rev  (  ListLa‐
137       bels.map f l) , but is tail-recursive and more efficient.
138
139
140
141
142       val fold_left : f:('a -> 'b -> 'a) -> init:'a -> 'b list -> 'a
143
144
145       List.fold_left f a [b1; ...; bn] is f (... (f (f a b1) b2) ...) bn .
146
147
148
149
150       val fold_right : f:('a -> 'b -> 'b) -> 'a list -> init:'b -> 'b
151
152
153       List.fold_right  f [a1; ...; an] b is f a1 (f a2 (... (f an b) ...))  .
154       Not tail-recursive.
155
156
157
158
159
160       === Iterators on two lists ===
161
162
163       val iter2 : f:('a -> 'b -> unit) -> 'a list -> 'b list -> unit
164
165
166       List.iter2 f [a1; ...; an] [b1; ...; bn] calls in turn f a1 b1; ...;  f
167       an  bn  .   Raise  Invalid_argument  if  the  two  lists have different
168       lengths.
169
170
171
172
173       val map2 : f:('a -> 'b -> 'c) -> 'a list -> 'b list -> 'c list
174
175
176       List.map2 f [a1; ...; an] [b1; ...; bn] is [f a1 b1; ...; f  an  bn]  .
177       Raise  Invalid_argument  if  the two lists have different lengths.  Not
178       tail-recursive.
179
180
181
182
183       val rev_map2 : f:('a -> 'b -> 'c) -> 'a list -> 'b list -> 'c list
184
185
186       List.rev_map2 f l1 l2 gives the same result as ListLabels.rev ( ListLa‐
187       bels.map2 f l1 l2) , but is tail-recursive and more efficient.
188
189
190
191
192       val  fold_left2  : f:('a -> 'b -> 'c -> 'a) -> init:'a -> 'b list -> 'c
193       list -> 'a
194
195
196       List.fold_left2 f a [b1; ...; bn] [c1; ...; cn] is f (... (f  (f  a  b1
197       c1)  b2  c2) ...) bn cn .  Raise Invalid_argument if the two lists have
198       different lengths.
199
200
201
202
203       val fold_right2 : f:('a -> 'b -> 'c -> 'c) -> 'a list  ->  'b  list  ->
204       init:'c -> 'c
205
206
207       List.fold_right2  f  [a1;  ...; an] [b1; ...; bn] c is f a1 b1 (f a2 b2
208       (... (f an bn c) ...))  .  Raise Invalid_argument if the two lists have
209       different lengths.  Not tail-recursive.
210
211
212
213
214
215       === List scanning ===
216
217
218       val for_all : f:('a -> bool) -> 'a list -> bool
219
220
221       for_all  p [a1; ...; an] checks if all elements of the list satisfy the
222       predicate p . That is, it returns (p a1) && (p a2) && ... && (p an) .
223
224
225
226
227       val exists : f:('a -> bool) -> 'a list -> bool
228
229
230       exists p [a1; ...; an] checks if at least one element of the list  sat‐
231       isfies the predicate p . That is, it returns (p a1) || (p a2) || ... ||
232       (p an) .
233
234
235
236
237       val for_all2 : f:('a -> 'b -> bool) -> 'a list -> 'b list -> bool
238
239       Same as ListLabels.for_all , but for a two-argument  predicate.   Raise
240       Invalid_argument if the two lists have different lengths.
241
242
243
244
245       val exists2 : f:('a -> 'b -> bool) -> 'a list -> 'b list -> bool
246
247       Same  as  ListLabels.exists  , but for a two-argument predicate.  Raise
248       Invalid_argument if the two lists have different lengths.
249
250
251
252
253       val mem : 'a -> set:'a list -> bool
254
255
256       mem a l is true if and only if a is equal to an element of l .
257
258
259
260
261       val memq : 'a -> set:'a list -> bool
262
263       Same as ListLabels.mem , but uses physical equality instead  of  struc‐
264       tural equality to compare list elements.
265
266
267
268
269
270       === List searching ===
271
272
273       val find : f:('a -> bool) -> 'a list -> 'a
274
275
276       find  p  l  returns  the first element of the list l that satisfies the
277       predicate p .  Raise Not_found if there is no value that satisfies p in
278       the list l .
279
280
281
282
283       val filter : f:('a -> bool) -> 'a list -> 'a list
284
285
286       filter  p  l  returns  all  the elements of the list l that satisfy the
287       predicate p .  The order of the elements in  the  input  list  is  pre‐
288       served.
289
290
291
292
293       val find_all : f:('a -> bool) -> 'a list -> 'a list
294
295
296       find_all is another name for ListLabels.filter .
297
298
299
300
301       val partition : f:('a -> bool) -> 'a list -> 'a list * 'a list
302
303
304       partition  p  l returns a pair of lists (l1, l2) , where l1 is the list
305       of all the elements of l that satisfy the predicate p , and l2  is  the
306       list of all the elements of l that do not satisfy p .  The order of the
307       elements in the input list is preserved.
308
309
310
311
312
313       === Association lists ===
314
315
316       val assoc : 'a -> ('a * 'b) list -> 'b
317
318
319       assoc a l returns the value associated with key a in the list of  pairs
320       l  .  That  is, assoc a [ ...; (a,b); ...] = b if (a,b) is the leftmost
321       binding of a in list l .  Raise Not_found if there is no value  associ‐
322       ated with a in the list l .
323
324
325
326
327       val assq : 'a -> ('a * 'b) list -> 'b
328
329       Same as ListLabels.assoc , but uses physical equality instead of struc‐
330       tural equality to compare keys.
331
332
333
334
335       val mem_assoc : 'a -> map:('a * 'b) list -> bool
336
337       Same as ListLabels.assoc , but simply return true if a binding  exists,
338       and false if no bindings exist for the given key.
339
340
341
342
343       val mem_assq : 'a -> map:('a * 'b) list -> bool
344
345       Same  as  ListLabels.mem_assoc  , but uses physical equality instead of
346       structural equality to compare keys.
347
348
349
350
351       val remove_assoc : 'a -> ('a * 'b) list -> ('a * 'b) list
352
353
354       remove_assoc a l returns the list of pairs l  without  the  first  pair
355       with key a , if any.  Not tail-recursive.
356
357
358
359
360       val remove_assq : 'a -> ('a * 'b) list -> ('a * 'b) list
361
362       Same as ListLabels.remove_assoc , but uses physical equality instead of
363       structural equality to compare keys.  Not tail-recursive.
364
365
366
367
368
369       === Lists of pairs ===
370
371
372       val split : ('a * 'b) list -> 'a list * 'b list
373
374       Transform a list of pairs into a pair of lists:  split  [(a1,b1);  ...;
375       (an,bn)] is ([a1; ...; an], [b1; ...; bn]) .  Not tail-recursive.
376
377
378
379
380       val combine : 'a list -> 'b list -> ('a * 'b) list
381
382       Transform  a  pair of lists into a list of pairs: combine [a1; ...; an]
383       [b1; ...; bn] is [(a1,b1); ...; (an,bn)] .  Raise  Invalid_argument  if
384       the two lists have different lengths.  Not tail-recursive.
385
386
387
388
389
390       === Sorting ===
391
392
393       val sort : cmp:('a -> 'a -> int) -> 'a list -> 'a list
394
395       Sort  a  list  in  increasing order according to a comparison function.
396       The comparison function must return  0  if  its  arguments  compare  as
397       equal, a positive integer if the first is greater, and a negative inte‐
398       ger if the first is smaller (see Array.sort for a  complete  specifica‐
399       tion).   For example, Pervasives.compare is a suitable comparison func‐
400       tion.  The resulting list is sorted in increasing order.  List.sort  is
401       guaranteed  to  run  in constant heap space (in addition to the size of
402       the result list) and logarithmic stack space.
403
404       The current implementation uses Merge Sort. It runs  in  constant  heap
405       space and logarithmic stack space.
406
407
408
409
410       val stable_sort : cmp:('a -> 'a -> int) -> 'a list -> 'a list
411
412       Same as ListLabels.sort , but the sorting algorithm is guaranteed to be
413       stable (i.e. elements that compare equal are  kept  in  their  original
414       order) .
415
416       The  current  implementation  uses Merge Sort. It runs in constant heap
417       space and logarithmic stack space.
418
419
420
421
422       val fast_sort : cmp:('a -> 'a -> int) -> 'a list -> 'a list
423
424       Same as List.sort or List.stable_sort , whichever is faster on  typical
425       input.
426
427
428
429
430       val merge : cmp:('a -> 'a -> int) -> 'a list -> 'a list -> 'a list
431
432       Merge  two  lists:  Assuming that l1 and l2 are sorted according to the
433       comparison function cmp , merge cmp l1 l2 will  return  a  sorted  list
434       containting  all  the elements of l1 and l2 .  If several elements com‐
435       pare equal, the elements of l1 will be before the elements of l2 .  Not
436       tail-recursive (sum of the lengths of the arguments).
437
438
439
440
441
442
443OCamldoc                          2010-01-29                     ListLabels(3)