1List(3) OCaml library 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 un‐
23 specified 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 type 'a t = 'a list =
33 | []
34 | :: of 'a * 'a list
35 An alias for the type of lists.
38 val length : 'a list -> int
42 Return the length (number of elements) of the given list.
44 val compare_lengths : 'a list -> 'b list -> int
48 Compare the lengths of two lists. compare_lengths l1 l2 is equivalent
50 to compare (length l1) (length l2) , except that the computation stops
51 after itering on the shortest list.
52 Since 4.05.0
55 val compare_length_with : 'a list -> int -> int
59 Compare the length of a list to an integer. compare_length_with l n is
61 equivalent to compare (length l) n , except that the computation stops
62 after at most n iterations on the list.
63 Since 4.05.0
66 val cons : 'a -> 'a list -> 'a list
70 cons x xs is x :: xs
73 Since 4.03.0
77 val hd : 'a list -> 'a
81 Return the first element of the given list.
83 Raises Failure if the list is empty.
86 val tl : 'a list -> 'a list
90 Return the given list without its first element.
92 Raises Failure if the list is empty.
95 val nth : 'a list -> int -> 'a
99 Return the n -th element of the given list. The first element (head of
101 the list) is at position 0.
102 Raises Failure if the list is too short.
105 Raises Invalid_argument if n is negative.
108 val nth_opt : 'a list -> int -> 'a option
112 Return the n -th element of the given list. The first element (head of
114 the list) is at position 0. Return None if the list is too short.
115 Since 4.05
118 Raises Invalid_argument if n is negative.
121 val rev : 'a list -> 'a list
125 List reversal.
127 val init : int -> (int -> 'a) -> 'a list
131 List.init len f is [f 0; f 1; ...; f (len-1)] , evaluated left to
134 right.
135 Since 4.06.0
138 Raises Invalid_argument if len < 0.
141 val append : 'a list -> 'a list -> 'a list
145 Concatenate two lists. Same as the infix operator @ . Not tail-recur‐
147 sive (length of the first argument).
148 val rev_append : 'a list -> 'a list -> 'a list
152 List.rev_append l1 l2 reverses l1 and concatenates it to l2 . This is
155 equivalent to List.rev l1 @ l2 , but rev_append is tail-recursive and
156 more efficient.
157 val concat : 'a list list -> 'a list
161 Concatenate a list of lists. The elements of the argument are all con‐
163 catenated together (in the same order) to give the result. Not
164 tail-recursive (length of the argument + length of the longest
165 sub-list).
166 val flatten : 'a list list -> 'a list
170 An alias for concat .
172 Iterators
177 val iter : ('a -> unit) -> 'a list -> unit
178 List.iter f [a1; ...; an] applies function f in turn to a1; ...; an .
181 It is equivalent to begin f a1; f a2; ...; f an; () end .
182 val iteri : (int -> 'a -> unit) -> 'a list -> unit
186 Same as List.iter , but the function is applied to the index of the el‐
188 ement as first argument (counting from 0), and the element itself as
189 second argument.
190 Since 4.00.0
193 val map : ('a -> 'b) -> 'a list -> 'b list
197 List.map f [a1; ...; an] applies function f to a1, ..., an , and builds
200 the list [f a1; ...; f an] with the results returned by f . Not
201 tail-recursive.
202 val mapi : (int -> 'a -> 'b) -> 'a list -> 'b list
206 Same as List.map , but the function is applied to the index of the ele‐
208 ment as first argument (counting from 0), and the element itself as
209 second argument. Not tail-recursive.
210 Since 4.00.0
213 val rev_map : ('a -> 'b) -> 'a list -> 'b list
217 List.rev_map f l gives the same result as List.rev ( List.map f l) ,
220 but is tail-recursive and more efficient.
221 val filter_map : ('a -> 'b option) -> 'a list -> 'b list
225 filter_map f l applies f to every element of l , filters out the None
228 elements and returns the list of the arguments of the Some elements.
229 Since 4.08.0
232 val concat_map : ('a -> 'b list) -> 'a list -> 'b list
236 List.concat_map f l gives the same result as List.concat ( List.map f
239 l) . Tail-recursive.
240 Since 4.10.0
243 val fold_left_map : ('a -> 'b -> 'a * 'c) -> 'a -> 'b list -> 'a * 'c
247 list
248 fold_left_map is a combination of fold_left and map that threads an
251 accumulator through calls to f
252 Since 4.11.0
256 val fold_left : ('a -> 'b -> 'a) -> 'a -> 'b list -> 'a
260 List.fold_left f a [b1; ...; bn] is f (... (f (f a b1) b2) ...) bn .
263 val fold_right : ('a -> 'b -> 'b) -> 'a list -> 'b -> 'b
267 List.fold_right f [a1; ...; an] b is f a1 (f a2 (... (f an b) ...)) .
270 Not tail-recursive.
271 Iterators on two lists
276 val iter2 : ('a -> 'b -> unit) -> 'a list -> 'b list -> unit
277 List.iter2 f [a1; ...; an] [b1; ...; bn] calls in turn f a1 b1; ...; f
280 an bn .
281 Raises Invalid_argument if the two lists are determined to have differ‐
284 ent lengths.
285 val map2 : ('a -> 'b -> 'c) -> 'a list -> 'b list -> 'c list
289 List.map2 f [a1; ...; an] [b1; ...; bn] is [f a1 b1; ...; f an bn] .
292 Raises Invalid_argument if the two lists are determined to have differ‐
295 ent lengths. Not tail-recursive.
296 val rev_map2 : ('a -> 'b -> 'c) -> 'a list -> 'b list -> 'c list
300 List.rev_map2 f l1 l2 gives the same result as List.rev ( List.map2 f
303 l1 l2) , but is tail-recursive and more efficient.
304 val fold_left2 : ('a -> 'b -> 'c -> 'a) -> 'a -> 'b list -> 'c list ->
308 'a
309 List.fold_left2 f a [b1; ...; bn] [c1; ...; cn] is f (... (f (f a b1
312 c1) b2 c2) ...) bn cn .
313 Raises Invalid_argument if the two lists are determined to have differ‐
316 ent lengths.
317 val fold_right2 : ('a -> 'b -> 'c -> 'c) -> 'a list -> 'b list -> 'c ->
321 'c
322 List.fold_right2 f [a1; ...; an] [b1; ...; bn] c is f a1 b1 (f a2 b2
325 (... (f an bn c) ...)) .
326 Raises Invalid_argument if the two lists are determined to have differ‐
329 ent lengths. Not tail-recursive.
330 List scanning
335 val for_all : ('a -> bool) -> 'a list -> bool
336 for_all p [a1; ...; an] checks if all elements of the list satisfy the
339 predicate p . That is, it returns (p a1) && (p a2) && ... && (p an) for
340 a non-empty list and true if the list is empty.
341 val exists : ('a -> bool) -> 'a list -> bool
345 exists p [a1; ...; an] checks if at least one element of the list sat‐
348 isfies the predicate p . That is, it returns (p a1) || (p a2) || ... ||
349 (p an) for a non-empty list and false if the list is empty.
350 val for_all2 : ('a -> 'b -> bool) -> 'a list -> 'b list -> bool
354 Same as List.for_all , but for a two-argument predicate.
356 Raises Invalid_argument if the two lists are determined to have differ‐
359 ent lengths.
360 val exists2 : ('a -> 'b -> bool) -> 'a list -> 'b list -> bool
364 Same as List.exists , but for a two-argument predicate.
366 Raises Invalid_argument if the two lists are determined to have differ‐
369 ent lengths.
370 val mem : 'a -> 'a list -> bool
374 mem a l is true if and only if a is equal to an element of l .
377 val memq : 'a -> 'a list -> bool
381 Same as List.mem , but uses physical equality instead of structural
383 equality to compare list elements.
384 List searching
389 val find : ('a -> bool) -> 'a list -> 'a
390 find p l returns the first element of the list l that satisfies the
393 predicate p .
394 Raises Not_found if there is no value that satisfies p in the list l .
397 val find_opt : ('a -> bool) -> 'a list -> 'a option
401 find_opt p l returns the first element of the list l that satisfies the
404 predicate p , or None if there is no value that satisfies p in the list
405 l .
406 Since 4.05
409 val find_map : ('a -> 'b option) -> 'a list -> 'b option
413 find_map f l applies f to the elements of l in order, and returns the
416 first result of the form Some v , or None if none exist.
417 Since 4.10.0
420 val filter : ('a -> bool) -> 'a list -> 'a list
424 filter p l returns all the elements of the list l that satisfy the
427 predicate p . The order of the elements in the input list is pre‐
428 served.
429 val find_all : ('a -> bool) -> 'a list -> 'a list
433 find_all is another name for List.filter .
436 val filteri : (int -> 'a -> bool) -> 'a list -> 'a list
440 Same as List.filter , but the predicate is applied to the index of the
442 element as first argument (counting from 0), and the element itself as
443 second argument.
444 Since 4.11.0
447 val partition : ('a -> bool) -> 'a list -> 'a list * 'a list
451 partition p l returns a pair of lists (l1, l2) , where l1 is the list
454 of all the elements of l that satisfy the predicate p , and l2 is the
455 list of all the elements of l that do not satisfy p . The order of the
456 elements in the input list is preserved.
457 Association lists
462 val assoc : 'a -> ('a * 'b) list -> 'b
463 assoc a l returns the value associated with key a in the list of pairs
466 l . That is, assoc a [ ...; (a,b); ...] = b if (a,b) is the leftmost
467 binding of a in list l .
468 Raises Not_found if there is no value associated with a in the list l .
471 val assoc_opt : 'a -> ('a * 'b) list -> 'b option
475 assoc_opt a l returns the value associated with key a in the list of
478 pairs l . That is, assoc_opt a [ ...; (a,b); ...] = b if (a,b) is the
479 leftmost binding of a in list l . Returns None if there is no value
480 associated with a in the list l .
481 Since 4.05
484 val assq : 'a -> ('a * 'b) list -> 'b
488 Same as List.assoc , but uses physical equality instead of structural
490 equality to compare keys.
491 val assq_opt : 'a -> ('a * 'b) list -> 'b option
495 Same as List.assoc_opt , but uses physical equality instead of struc‐
497 tural equality to compare keys.
498 Since 4.05
501 val mem_assoc : 'a -> ('a * 'b) list -> bool
505 Same as List.assoc , but simply return true if a binding exists, and
507 false if no bindings exist for the given key.
508 val mem_assq : 'a -> ('a * 'b) list -> bool
512 Same as List.mem_assoc , but uses physical equality instead of struc‐
514 tural equality to compare keys.
515 val remove_assoc : 'a -> ('a * 'b) list -> ('a * 'b) list
519 remove_assoc a l returns the list of pairs l without the first pair
522 with key a , if any. Not tail-recursive.
523 val remove_assq : 'a -> ('a * 'b) list -> ('a * 'b) list
527 Same as List.remove_assoc , but uses physical equality instead of
529 structural equality to compare keys. Not tail-recursive.
530 Lists of pairs
535 val split : ('a * 'b) list -> 'a list * 'b list
536 Transform a list of pairs into a pair of lists: split [(a1,b1); ...;
538 (an,bn)] is ([a1; ...; an], [b1; ...; bn]) . Not tail-recursive.
539 val combine : 'a list -> 'b list -> ('a * 'b) list
543 Transform a pair of lists into a list of pairs: combine [a1; ...; an]
545 [b1; ...; bn] is [(a1,b1); ...; (an,bn)] .
546 Raises Invalid_argument if the two lists have different lengths. Not
549 tail-recursive.
550 Sorting
555 val sort : ('a -> 'a -> int) -> 'a list -> 'a list
556 Sort a list in increasing order according to a comparison function.
558 The comparison function must return 0 if its arguments compare as
559 equal, a positive integer if the first is greater, and a negative inte‐
560 ger if the first is smaller (see Array.sort for a complete specifica‐
561 tion). For example, compare is a suitable comparison function. The
562 resulting list is sorted in increasing order. List.sort is guaranteed
563 to run in constant heap space (in addition to the size of the result
564 list) and logarithmic stack space.
565 The current implementation uses Merge Sort. It runs in constant heap
567 space and logarithmic stack space.
568 val stable_sort : ('a -> 'a -> int) -> 'a list -> 'a list
572 Same as List.sort , but the sorting algorithm is guaranteed to be sta‐
574 ble (i.e. elements that compare equal are kept in their original order)
575 .
576 The current implementation uses Merge Sort. It runs in constant heap
578 space and logarithmic stack space.
579 val fast_sort : ('a -> 'a -> int) -> 'a list -> 'a list
583 Same as List.sort or List.stable_sort , whichever is faster on typical
585 input.
586 val sort_uniq : ('a -> 'a -> int) -> 'a list -> 'a list
590 Same as List.sort , but also remove duplicates.
592 Since 4.02.0
595 val merge : ('a -> 'a -> int) -> 'a list -> 'a list -> 'a list
599 Merge two lists: Assuming that l1 and l2 are sorted according to the
601 comparison function cmp , merge cmp l1 l2 will return a sorted list
602 containing all the elements of l1 and l2 . If several elements compare
603 equal, the elements of l1 will be before the elements of l2 . Not
604 tail-recursive (sum of the lengths of the arguments).
605 Iterators
610 val to_seq : 'a list -> 'a Seq.t
611 Iterate on the list
613 Since 4.07
616 val of_seq : 'a Seq.t -> 'a list
620 Create a list from the iterator
622 Since 4.07
625OCamldoc 2021-01-26 List(3)