1List(3) OCamldoc List(3)
2
6 List - List operations.
7
9 Module List
10
12 Module List
13 : sig end
14 List operations.
17 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 The above considerations can usually be ignored if your lists are not
26 longer than about 10000 elements.
27 val length : 'a list -> int
34 Return the length (number of elements) of the given list.
36 val compare_lengths : 'a list -> 'b list -> int
40 Compare the lengths of two lists. compare_lengths l1 l2 is equivalent
42 to compare (length l1) (length l2) , except that the computation stops
43 after itering on the shortest list.
44 Since 4.05.0
47 val compare_length_with : 'a list -> int -> int
51 Compare the length of a list to an integer. compare_length_with l n is
53 equivalent to compare (length l) n , except that the computation stops
54 after at most n iterations on the list.
55 Since 4.05.0
58 val cons : 'a -> 'a list -> 'a list
62 cons x xs is x :: xs
65 Since 4.03.0
69 val hd : 'a list -> 'a
73 Return the first element of the given list. Raise Failure hd if the
75 list is empty.
76 val tl : 'a list -> 'a list
80 Return the given list without its first element. Raise Failure tl if
82 the list is empty.
83 val nth : 'a list -> int -> 'a
87 Return the n -th element of the given list. The first element (head of
89 the list) is at position 0. Raise Failure nth if the list is too
90 short. Raise Invalid_argument List.nth if n is negative.
91 val nth_opt : 'a list -> int -> 'a option
95 Return the n -th element of the given list. The first element (head of
97 the list) is at position 0. Return None if the list is too short.
98 Raise Invalid_argument List.nth if n is negative.
99 Since 4.05
102 val rev : 'a list -> 'a list
106 List reversal.
108 val append : 'a list -> 'a list -> 'a list
112 Concatenate two lists. Same as the infix operator @ . Not tail-recur‐
114 sive (length of the first argument).
115 val rev_append : 'a list -> 'a list -> 'a list
119 List.rev_append l1 l2 reverses l1 and concatenates it to l2 . This is
122 equivalent to List.rev l1 @ l2 , but rev_append is tail-recursive and
123 more efficient.
124 val concat : 'a list list -> 'a list
128 Concatenate a list of lists. The elements of the argument are all con‐
130 catenated together (in the same order) to give the result. Not
131 tail-recursive (length of the argument + length of the longest
132 sub-list).
133 val flatten : 'a list list -> 'a list
137 An alias for concat .
139 === Iterators ===
144 val iter : ('a -> unit) -> 'a list -> unit
147 List.iter f [a1; ...; an] applies function f in turn to a1; ...; an .
150 It is equivalent to begin f a1; f a2; ...; f an; () end .
151 val iteri : (int -> 'a -> unit) -> 'a list -> unit
155 Same as List.iter , but the function is applied to the index of the
157 element as first argument (counting from 0), and the element itself as
158 second argument.
159 Since 4.00.0
162 val map : ('a -> 'b) -> 'a list -> 'b list
166 List.map f [a1; ...; an] applies function f to a1, ..., an , and builds
169 the list [f a1; ...; f an] with the results returned by f . Not
170 tail-recursive.
171 val mapi : (int -> 'a -> 'b) -> 'a list -> 'b list
175 Same as List.map , but the function is applied to the index of the ele‐
177 ment as first argument (counting from 0), and the element itself as
178 second argument. Not tail-recursive.
179 Since 4.00.0
182 val rev_map : ('a -> 'b) -> 'a list -> 'b list
186 List.rev_map f l gives the same result as List.rev ( List.map f l) ,
189 but is tail-recursive and more efficient.
190 val fold_left : ('a -> 'b -> 'a) -> 'a -> 'b list -> 'a
194 List.fold_left f a [b1; ...; bn] is f (... (f (f a b1) b2) ...) bn .
197 val fold_right : ('a -> 'b -> 'b) -> 'a list -> 'b -> 'b
201 List.fold_right f [a1; ...; an] b is f a1 (f a2 (... (f an b) ...)) .
204 Not tail-recursive.
205 === Iterators on two lists ===
210 val iter2 : ('a -> 'b -> unit) -> 'a list -> 'b list -> unit
213 List.iter2 f [a1; ...; an] [b1; ...; bn] calls in turn f a1 b1; ...; f
216 an bn . Raise Invalid_argument if the two lists are determined to have
217 different lengths.
218 val map2 : ('a -> 'b -> 'c) -> 'a list -> 'b list -> 'c list
222 List.map2 f [a1; ...; an] [b1; ...; bn] is [f a1 b1; ...; f an bn] .
225 Raise Invalid_argument if the two lists are determined to have differ‐
226 ent lengths. Not tail-recursive.
227 val rev_map2 : ('a -> 'b -> 'c) -> 'a list -> 'b list -> 'c list
231 List.rev_map2 f l1 l2 gives the same result as List.rev ( List.map2 f
234 l1 l2) , but is tail-recursive and more efficient.
235 val fold_left2 : ('a -> 'b -> 'c -> 'a) -> 'a -> 'b list -> 'c list ->
239 'a
240 List.fold_left2 f a [b1; ...; bn] [c1; ...; cn] is f (... (f (f a b1
243 c1) b2 c2) ...) bn cn . Raise Invalid_argument if the two lists are
244 determined to have different lengths.
245 val fold_right2 : ('a -> 'b -> 'c -> 'c) -> 'a list -> 'b list -> 'c ->
249 'c
250 List.fold_right2 f [a1; ...; an] [b1; ...; bn] c is f a1 b1 (f a2 b2
253 (... (f an bn c) ...)) . Raise Invalid_argument if the two lists are
254 determined to have different lengths. Not tail-recursive.
255 === List scanning ===
260 val for_all : ('a -> bool) -> 'a list -> bool
263 for_all p [a1; ...; an] checks if all elements of the list satisfy the
266 predicate p . That is, it returns (p a1) && (p a2) && ... && (p an) .
267 val exists : ('a -> bool) -> 'a list -> bool
271 exists p [a1; ...; an] checks if at least one element of the list sat‐
274 isfies the predicate p . That is, it returns (p a1) || (p a2) || ... ||
275 (p an) .
276 val for_all2 : ('a -> 'b -> bool) -> 'a list -> 'b list -> bool
280 Same as List.for_all , but for a two-argument predicate. Raise
282 Invalid_argument if the two lists are determined to have different
283 lengths.
284 val exists2 : ('a -> 'b -> bool) -> 'a list -> 'b list -> bool
288 Same as List.exists , but for a two-argument predicate. Raise
290 Invalid_argument if the two lists are determined to have different
291 lengths.
292 val mem : 'a -> 'a list -> bool
296 mem a l is true if and only if a is equal to an element of l .
299 val memq : 'a -> 'a list -> bool
303 Same as List.mem , but uses physical equality instead of structural
305 equality to compare list elements.
306 === List searching ===
311 val find : ('a -> bool) -> 'a list -> 'a
314 find p l returns the first element of the list l that satisfies the
317 predicate p . Raise Not_found if there is no value that satisfies p in
318 the list l .
319 val find_opt : ('a -> bool) -> 'a list -> 'a option
323 find_opt p l returns the first element of the list l that satisfies the
326 predicate p , or None if there is no value that satisfies p in the list
327 l .
328 Since 4.05
331 val filter : ('a -> bool) -> 'a list -> 'a list
335 filter p l returns all the elements of the list l that satisfy the
338 predicate p . The order of the elements in the input list is pre‐
339 served.
340 val find_all : ('a -> bool) -> 'a list -> 'a list
344 find_all is another name for List.filter .
347 val partition : ('a -> bool) -> 'a list -> 'a list * 'a list
351 partition p l returns a pair of lists (l1, l2) , where l1 is the list
354 of all the elements of l that satisfy the predicate p , and l2 is the
355 list of all the elements of l that do not satisfy p . The order of the
356 elements in the input list is preserved.
357 === Association lists ===
362 val assoc : 'a -> ('a * 'b) list -> 'b
365 assoc a l returns the value associated with key a in the list of pairs
368 l . That is, assoc a [ ...; (a,b); ...] = b if (a,b) is the leftmost
369 binding of a in list l . Raise Not_found if there is no value associ‐
370 ated with a in the list l .
371 val assoc_opt : 'a -> ('a * 'b) list -> 'b option
375 assoc_opt a l returns the value associated with key a in the list of
378 pairs l . That is, assoc_opt a [ ...; (a,b); ...] = b if (a,b) is the
379 leftmost binding of a in list l . Returns None if there is no value
380 associated with a in the list l .
381 Since 4.05
384 val assq : 'a -> ('a * 'b) list -> 'b
388 Same as List.assoc , but uses physical equality instead of structural
390 equality to compare keys.
391 val assq_opt : 'a -> ('a * 'b) list -> 'b option
395 Same as List.assoc_opt , but uses physical equality instead of struc‐
397 tural equality to compare keys.
398 Since 4.05
401 val mem_assoc : 'a -> ('a * 'b) list -> bool
405 Same as List.assoc , but simply return true if a binding exists, and
407 false if no bindings exist for the given key.
408 val mem_assq : 'a -> ('a * 'b) list -> bool
412 Same as List.mem_assoc , but uses physical equality instead of struc‐
414 tural equality to compare keys.
415 val remove_assoc : 'a -> ('a * 'b) list -> ('a * 'b) list
419 remove_assoc a l returns the list of pairs l without the first pair
422 with key a , if any. Not tail-recursive.
423 val remove_assq : 'a -> ('a * 'b) list -> ('a * 'b) list
427 Same as List.remove_assoc , but uses physical equality instead of
429 structural equality to compare keys. Not tail-recursive.
430 === Lists of pairs ===
435 val split : ('a * 'b) list -> 'a list * 'b list
438 Transform a list of pairs into a pair of lists: split [(a1,b1); ...;
440 (an,bn)] is ([a1; ...; an], [b1; ...; bn]) . Not tail-recursive.
441 val combine : 'a list -> 'b list -> ('a * 'b) list
445 Transform a pair of lists into a list of pairs: combine [a1; ...; an]
447 [b1; ...; bn] is [(a1,b1); ...; (an,bn)] . Raise Invalid_argument if
448 the two lists have different lengths. Not tail-recursive.
449 === Sorting ===
454 val sort : ('a -> 'a -> int) -> 'a list -> 'a list
457 Sort a list in increasing order according to a comparison function.
459 The comparison function must return 0 if its arguments compare as
460 equal, a positive integer if the first is greater, and a negative inte‐
461 ger if the first is smaller (see Array.sort for a complete specifica‐
462 tion). For example, Pervasives.compare is a suitable comparison func‐
463 tion. The resulting list is sorted in increasing order. List.sort is
464 guaranteed to run in constant heap space (in addition to the size of
465 the result list) and logarithmic stack space.
466 The current implementation uses Merge Sort. It runs in constant heap
468 space and logarithmic stack space.
469 val stable_sort : ('a -> 'a -> int) -> 'a list -> 'a list
473 Same as List.sort , but the sorting algorithm is guaranteed to be sta‐
475 ble (i.e. elements that compare equal are kept in their original order)
476 .
477 The current implementation uses Merge Sort. It runs in constant heap
479 space and logarithmic stack space.
480 val fast_sort : ('a -> 'a -> int) -> 'a list -> 'a list
484 Same as List.sort or List.stable_sort , whichever is faster on typical
486 input.
487 val sort_uniq : ('a -> 'a -> int) -> 'a list -> 'a list
491 Same as List.sort , but also remove duplicates.
493 Since 4.02.0
496 val merge : ('a -> 'a -> int) -> 'a list -> 'a list -> 'a list
500 Merge two lists: Assuming that l1 and l2 are sorted according to the
502 comparison function cmp , merge cmp l1 l2 will return a sorted list
503 containting all the elements of l1 and l2 . If several elements com‐
504 pare equal, the elements of l1 will be before the elements of l2 . Not
505 tail-recursive (sum of the lengths of the arguments).
5062018-04-14 source: List(3)