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 The labeled version of this module can be used as described in the Std‐
29 Labels module.
30 type 'a t = 'a list =
36 | []
37 | (::) of 'a * 'a list
38 An alias for the type of lists.
41 val length : 'a list -> int
45 Return the length (number of elements) of the given list.
47 val compare_lengths : 'a list -> 'b list -> int
51 Compare the lengths of two lists. compare_lengths l1 l2 is equivalent
53 to compare (length l1) (length l2) , except that the computation stops
54 after reaching the end of the shortest list.
55 Since 4.05.0
58 val compare_length_with : 'a list -> int -> int
62 Compare the length of a list to an integer. compare_length_with l len
64 is equivalent to compare (length l) len , except that the computation
65 stops after at most len iterations on the list.
66 Since 4.05.0
69 val cons : 'a -> 'a list -> 'a list
73 cons x xs is x :: xs
76 Since 4.03.0 (4.05.0 in ListLabels)
80 val hd : 'a list -> 'a
84 Return the first element of the given list.
86 Raises Failure if the list is empty.
89 val tl : 'a list -> 'a list
93 Return the given list without its first element.
95 Raises Failure if the list is empty.
98 val nth : 'a list -> int -> 'a
102 Return the n -th element of the given list. The first element (head of
104 the list) is at position 0.
105 Raises Failure if the list is too short.
108 Raises Invalid_argument if n is negative.
111 val nth_opt : 'a list -> int -> 'a option
115 Return the n -th element of the given list. The first element (head of
117 the list) is at position 0. Return None if the list is too short.
118 Since 4.05
121 Raises Invalid_argument if n is negative.
124 val rev : 'a list -> 'a list
128 List reversal.
130 val init : int -> (int -> 'a) -> 'a list
134 init len f is f 0; f 1; ...; f (len-1) , evaluated left to right.
137 Since 4.06.0
140 Raises Invalid_argument if len < 0 .
143 val append : 'a list -> 'a list -> 'a list
147 Concatenate two lists. Same function as the infix operator @ . Not
149 tail-recursive (length of the first argument). The @ operator is not
150 tail-recursive either.
151 val rev_append : 'a list -> 'a list -> 'a list
155 rev_append l1 l2 reverses l1 and concatenates it with l2 . This is
158 equivalent to ( List.rev l1) @ l2 , but rev_append is tail-recursive
159 and more efficient.
160 val concat : 'a list list -> 'a list
164 Concatenate a list of lists. The elements of the argument are all con‐
166 catenated together (in the same order) to give the result. Not
167 tail-recursive (length of the argument + length of the longest
168 sub-list).
169 val flatten : 'a list list -> 'a list
173 Same as List.concat . Not tail-recursive (length of the argument +
175 length of the longest sub-list).
176 Comparison
181 val equal : ('a -> 'a -> bool) -> 'a list -> 'a list -> bool
182 equal eq [a1; ...; an] [b1; ..; bm] holds when the two input lists have
185 the same length, and for each pair of elements ai , bi at the same po‐
186 sition we have eq ai bi .
187 Note: the eq function may be called even if the lists have different
189 length. If you know your equality function is costly, you may want to
190 check List.compare_lengths first.
191 Since 4.12.0
194 val compare : ('a -> 'a -> int) -> 'a list -> 'a list -> int
198 compare cmp [a1; ...; an] [b1; ...; bm] performs a lexicographic com‐
201 parison of the two input lists, using the same 'a -> 'a -> int inter‐
202 face as compare :
203 - a1 :: l1 is smaller than a2 :: l2 (negative result) if a1 is smaller
206 than a2 , or if they are equal (0 result) and l1 is smaller than l2
207 -the empty list [] is strictly smaller than non-empty lists
210 Note: the cmp function will be called even if the lists have different
212 lengths.
213 Since 4.12.0
216 Iterators
221 val iter : ('a -> unit) -> 'a list -> unit
222 iter f [a1; ...; an] applies function f in turn to a1; ...; an . It is
225 equivalent to begin f a1; f a2; ...; f an; () end .
226 val iteri : (int -> 'a -> unit) -> 'a list -> unit
230 Same as List.iter , but the function is applied to the index of the el‐
232 ement as first argument (counting from 0), and the element itself as
233 second argument.
234 Since 4.00.0
237 val map : ('a -> 'b) -> 'a list -> 'b list
241 map f [a1; ...; an] applies function f to a1, ..., an , and builds the
244 list [f a1; ...; f an] with the results returned by f . Not tail-recur‐
245 sive.
246 val mapi : (int -> 'a -> 'b) -> 'a list -> 'b list
250 Same as List.map , but the function is applied to the index of the ele‐
252 ment as first argument (counting from 0), and the element itself as
253 second argument. Not tail-recursive.
254 Since 4.00.0
257 val rev_map : ('a -> 'b) -> 'a list -> 'b list
261 rev_map f l gives the same result as List.rev ( List.map f l) , but is
264 tail-recursive and more efficient.
265 val filter_map : ('a -> 'b option) -> 'a list -> 'b list
269 filter_map f l applies f to every element of l , filters out the None
272 elements and returns the list of the arguments of the Some elements.
273 Since 4.08.0
276 val concat_map : ('a -> 'b list) -> 'a list -> 'b list
280 concat_map f l gives the same result as List.concat ( List.map f l) .
283 Tail-recursive.
284 Since 4.10.0
287 val fold_left_map : ('a -> 'b -> 'a * 'c) -> 'a -> 'b list -> 'a * 'c
291 list
292 fold_left_map is a combination of fold_left and map that threads an
295 accumulator through calls to f .
296 Since 4.11.0
299 val fold_left : ('a -> 'b -> 'a) -> 'a -> 'b list -> 'a
303 fold_left f init [b1; ...; bn] is f (... (f (f init b1) b2) ...) bn .
306 val fold_right : ('a -> 'b -> 'b) -> 'a list -> 'b -> 'b
310 fold_right f [a1; ...; an] init is f a1 (f a2 (... (f an init) ...)) .
313 Not tail-recursive.
314 Iterators on two lists
319 val iter2 : ('a -> 'b -> unit) -> 'a list -> 'b list -> unit
320 iter2 f [a1; ...; an] [b1; ...; bn] calls in turn f a1 b1; ...; f an bn
323 .
324 Raises Invalid_argument if the two lists are determined to have differ‐
327 ent lengths.
328 val map2 : ('a -> 'b -> 'c) -> 'a list -> 'b list -> 'c list
332 map2 f [a1; ...; an] [b1; ...; bn] is [f a1 b1; ...; f an bn] .
335 Raises Invalid_argument if the two lists are determined to have differ‐
338 ent lengths. Not tail-recursive.
339 val rev_map2 : ('a -> 'b -> 'c) -> 'a list -> 'b list -> 'c list
343 rev_map2 f l1 l2 gives the same result as List.rev ( List.map2 f l1 l2)
346 , but is tail-recursive and more efficient.
347 val fold_left2 : ('a -> 'b -> 'c -> 'a) -> 'a -> 'b list -> 'c list ->
351 'a
352 fold_left2 f init [a1; ...; an] [b1; ...; bn] is f (... (f (f init a1
355 b1) a2 b2) ...) an bn .
356 Raises Invalid_argument if the two lists are determined to have differ‐
359 ent lengths.
360 val fold_right2 : ('a -> 'b -> 'c -> 'c) -> 'a list -> 'b list -> 'c ->
364 'c
365 fold_right2 f [a1; ...; an] [b1; ...; bn] init is f a1 b1 (f a2 b2 (...
368 (f an bn init) ...)) .
369 Raises Invalid_argument if the two lists are determined to have differ‐
372 ent lengths. Not tail-recursive.
373 List scanning
378 val for_all : ('a -> bool) -> 'a list -> bool
379 for_all f [a1; ...; an] checks if all elements of the list satisfy the
382 predicate f . That is, it returns (f a1) && (f a2) && ... && (f an) for
383 a non-empty list and true if the list is empty.
384 val exists : ('a -> bool) -> 'a list -> bool
388 exists f [a1; ...; an] checks if at least one element of the list sat‐
391 isfies the predicate f . That is, it returns (f a1) || (f a2) || ... ||
392 (f an) for a non-empty list and false if the list is empty.
393 val for_all2 : ('a -> 'b -> bool) -> 'a list -> 'b list -> bool
397 Same as List.for_all , but for a two-argument predicate.
399 Raises Invalid_argument if the two lists are determined to have differ‐
402 ent lengths.
403 val exists2 : ('a -> 'b -> bool) -> 'a list -> 'b list -> bool
407 Same as List.exists , but for a two-argument predicate.
409 Raises Invalid_argument if the two lists are determined to have differ‐
412 ent lengths.
413 val mem : 'a -> 'a list -> bool
417 mem a set is true if and only if a is equal to an element of set .
420 val memq : 'a -> 'a list -> bool
424 Same as List.mem , but uses physical equality instead of structural
426 equality to compare list elements.
427 List searching
432 val find : ('a -> bool) -> 'a list -> 'a
433 find f l returns the first element of the list l that satisfies the
436 predicate f .
437 Raises Not_found if there is no value that satisfies f in the list l .
440 val find_opt : ('a -> bool) -> 'a list -> 'a option
444 find f l returns the first element of the list l that satisfies the
447 predicate f . Returns None if there is no value that satisfies f in
448 the list l .
449 Since 4.05
452 val find_map : ('a -> 'b option) -> 'a list -> 'b option
456 find_map f l applies f to the elements of l in order, and returns the
459 first result of the form Some v , or None if none exist.
460 Since 4.10.0
463 val filter : ('a -> bool) -> 'a list -> 'a list
467 filter f l returns all the elements of the list l that satisfy the
470 predicate f . The order of the elements in the input list is preserved.
471 val find_all : ('a -> bool) -> 'a list -> 'a list
475 find_all is another name for List.filter .
478 val filteri : (int -> 'a -> bool) -> 'a list -> 'a list
482 Same as List.filter , but the predicate is applied to the index of the
484 element as first argument (counting from 0), and the element itself as
485 second argument.
486 Since 4.11.0
489 val partition : ('a -> bool) -> 'a list -> 'a list * 'a list
493 partition f l returns a pair of lists (l1, l2) , where l1 is the list
496 of all the elements of l that satisfy the predicate f , and l2 is the
497 list of all the elements of l that do not satisfy f . The order of the
498 elements in the input list is preserved.
499 val partition_map : ('a -> ('b, 'c) Either.t) -> 'a list -> 'b list *
503 'c list
504 partition_map f l returns a pair of lists (l1, l2) such that, for each
507 element x of the input list l :
508 -if f x is Left y1 , then y1 is in l1 , and
510 -if f x is Right y2 , then y2 is in l2 .
512 The output elements are included in l1 and l2 in the same relative or‐
514 der as the corresponding input elements in l .
515 In particular, partition_map (fun x -> if f x then Left x else Right x)
517 l is equivalent to partition f l .
518 Since 4.12.0
521 Association lists
526 val assoc : 'a -> ('a * 'b) list -> 'b
527 assoc a l returns the value associated with key a in the list of pairs
530 l . That is, assoc a [ ...; (a,b); ...] = b if (a,b) is the leftmost
531 binding of a in list l .
532 Raises Not_found if there is no value associated with a in the list l .
535 val assoc_opt : 'a -> ('a * 'b) list -> 'b option
539 assoc_opt a l returns the value associated with key a in the list of
542 pairs l . That is, assoc_opt a [ ...; (a,b); ...] = Some b if (a,b) is
543 the leftmost binding of a in list l . Returns None if there is no
544 value associated with a in the list l .
545 Since 4.05
548 val assq : 'a -> ('a * 'b) list -> 'b
552 Same as List.assoc , but uses physical equality instead of structural
554 equality to compare keys.
555 val assq_opt : 'a -> ('a * 'b) list -> 'b option
559 Same as List.assoc_opt , but uses physical equality instead of struc‐
561 tural equality to compare keys.
562 Since 4.05.0
565 val mem_assoc : 'a -> ('a * 'b) list -> bool
569 Same as List.assoc , but simply return true if a binding exists, and
571 false if no bindings exist for the given key.
572 val mem_assq : 'a -> ('a * 'b) list -> bool
576 Same as List.mem_assoc , but uses physical equality instead of struc‐
578 tural equality to compare keys.
579 val remove_assoc : 'a -> ('a * 'b) list -> ('a * 'b) list
583 remove_assoc a l returns the list of pairs l without the first pair
586 with key a , if any. Not tail-recursive.
587 val remove_assq : 'a -> ('a * 'b) list -> ('a * 'b) list
591 Same as List.remove_assoc , but uses physical equality instead of
593 structural equality to compare keys. Not tail-recursive.
594 Lists of pairs
599 val split : ('a * 'b) list -> 'a list * 'b list
600 Transform a list of pairs into a pair of lists: split [(a1,b1); ...;
602 (an,bn)] is ([a1; ...; an], [b1; ...; bn]) . Not tail-recursive.
603 val combine : 'a list -> 'b list -> ('a * 'b) list
607 Transform a pair of lists into a list of pairs: combine [a1; ...; an]
609 [b1; ...; bn] is [(a1,b1); ...; (an,bn)] .
610 Raises Invalid_argument if the two lists have different lengths. Not
613 tail-recursive.
614 Sorting
619 val sort : ('a -> 'a -> int) -> 'a list -> 'a list
620 Sort a list in increasing order according to a comparison function. The
622 comparison function must return 0 if its arguments compare as equal, a
623 positive integer if the first is greater, and a negative integer if the
624 first is smaller (see Array.sort for a complete specification). For ex‐
625 ample, compare is a suitable comparison function. The resulting list
626 is sorted in increasing order. List.sort is guaranteed to run in con‐
627 stant heap space (in addition to the size of the result list) and loga‐
628 rithmic stack space.
629 The current implementation uses Merge Sort. It runs in constant heap
631 space and logarithmic stack space.
632 val stable_sort : ('a -> 'a -> int) -> 'a list -> 'a list
636 Same as List.sort , but the sorting algorithm is guaranteed to be sta‐
638 ble (i.e. elements that compare equal are kept in their original or‐
639 der).
640 The current implementation uses Merge Sort. It runs in constant heap
642 space and logarithmic stack space.
643 val fast_sort : ('a -> 'a -> int) -> 'a list -> 'a list
647 Same as List.sort or List.stable_sort , whichever is faster on typical
649 input.
650 val sort_uniq : ('a -> 'a -> int) -> 'a list -> 'a list
654 Same as List.sort , but also remove duplicates.
656 Since 4.02.0 (4.03.0 in ListLabels)
659 val merge : ('a -> 'a -> int) -> 'a list -> 'a list -> 'a list
663 Merge two lists: Assuming that l1 and l2 are sorted according to the
665 comparison function cmp , merge cmp l1 l2 will return a sorted list
666 containing all the elements of l1 and l2 . If several elements compare
667 equal, the elements of l1 will be before the elements of l2 . Not
668 tail-recursive (sum of the lengths of the arguments).
669 Lists and Sequences
674 val to_seq : 'a list -> 'a Seq.t
675 Iterate on the list.
677 Since 4.07
680 val of_seq : 'a Seq.t -> 'a list
684 Create a list from a sequence.
686 Since 4.07
689OCamldoc 2022-07-22 List(3)