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
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
35 Return the length (number of elements) of the given list.
37 val hd : 'a list -> 'a
42 Return the first element of the given list. Raise Failure hd if the
44 list is empty.
45 val tl : 'a list -> 'a list
50 Return the given list without its first element. Raise Failure tl if
52 the list is empty.
53 val nth : 'a list -> int -> 'a
58 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 val rev : 'a list -> 'a list
67 List reversal.
69 val append : 'a list -> 'a list -> 'a list
74 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 val rev_append : 'a list -> 'a list -> 'a list
83 List.rev_append l1 l2 reverses l1 and concatenates it to l2 . This is
86 equivalent to List.rev l1 @ l2 , but rev_append is tail-recursive and
87 more efficient.
88 val concat : 'a list list -> 'a list
93 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 tail-
96 recursive (length of the argument + length of the longest sub-list).
97 val flatten : 'a list list -> 'a list
102 Same as concat . Not tail-recursive (length of the argument + length
104 of the longest sub-list).
105 === Iterators ===
111 val iter : ('a -> unit) -> 'a list -> unit
114 List.iter f [a1; ...; an] applies function f in turn to a1; ...; an .
117 It is equivalent to begin f a1; f a2; ...; f an; () end .
118 val map : ('a -> 'b) -> 'a list -> 'b list
123 List.map f [a1; ...; an] applies function f to a1, ..., an , and builds
126 the list [f a1; ...; f an] with the results returned by f . Not tail-
127 recursive.
128 val rev_map : ('a -> 'b) -> 'a list -> 'b list
133 List.rev_map f l gives the same result as List.rev ( List.map f l) ,
136 but is tail-recursive and more efficient.
137 val fold_left : ('a -> 'b -> 'a) -> 'a -> 'b list -> 'a
142 List.fold_left f a [b1; ...; bn] is f (... (f (f a b1) b2) ...) bn .
145 val fold_right : ('a -> 'b -> 'b) -> 'a list -> 'b -> 'b
150 List.fold_right f [a1; ...; an] b is f a1 (f a2 (... (f an b) ...)) .
153 Not tail-recursive.
154 === Iterators on two lists ===
160 val iter2 : ('a -> 'b -> unit) -> 'a list -> 'b list -> unit
163 List.iter2 f [a1; ...; an] [b1; ...; bn] calls in turn f a1 b1; ...; f
166 an bn . Raise Invalid_argument if the two lists have different
167 lengths.
168 val map2 : ('a -> 'b -> 'c) -> 'a list -> 'b list -> 'c list
173 List.map2 f [a1; ...; an] [b1; ...; bn] is [f a1 b1; ...; f an bn] .
176 Raise Invalid_argument if the two lists have different lengths. Not
177 tail-recursive.
178 val rev_map2 : ('a -> 'b -> 'c) -> 'a list -> 'b list -> 'c list
183 List.rev_map2 f l1 l2 gives the same result as List.rev ( List.map2 f
186 l1 l2) , but is tail-recursive and more efficient.
187 val fold_left2 : ('a -> 'b -> 'c -> 'a) -> 'a -> 'b list -> 'c list ->
192 'a
193 List.fold_left2 f a [b1; ...; bn] [c1; ...; cn] is f (... (f (f a b1
196 c1) b2 c2) ...) bn cn . Raise Invalid_argument if the two lists have
197 different lengths.
198 val fold_right2 : ('a -> 'b -> 'c -> 'c) -> 'a list -> 'b list -> 'c ->
203 'c
204 List.fold_right2 f [a1; ...; an] [b1; ...; bn] c is f a1 b1 (f a2 b2
207 (... (f an bn c) ...)) . Raise Invalid_argument if the two lists have
208 different lengths. Not tail-recursive.
209 === List scanning ===
215 val for_all : ('a -> bool) -> 'a list -> bool
218 for_all p [a1; ...; an] checks if all elements of the list satisfy the
221 predicate p . That is, it returns (p a1) && (p a2) && ... && (p an) .
222 val exists : ('a -> bool) -> 'a list -> bool
227 exists p [a1; ...; an] checks if at least one element of the list sat‐
230 isfies the predicate p . That is, it returns (p a1) || (p a2) || ... ||
231 (p an) .
232 val for_all2 : ('a -> 'b -> bool) -> 'a list -> 'b list -> bool
237 Same as List.for_all , but for a two-argument predicate. Raise
239 Invalid_argument if the two lists have different lengths.
240 val exists2 : ('a -> 'b -> bool) -> 'a list -> 'b list -> bool
245 Same as List.exists , but for a two-argument predicate. Raise
247 Invalid_argument if the two lists have different lengths.
248 val mem : 'a -> 'a list -> bool
253 mem a l is true if and only if a is equal to an element of l .
256 val memq : 'a -> 'a list -> bool
261 Same as List.mem , but uses physical equality instead of structural
263 equality to compare list elements.
264 === List searching ===
270 val find : ('a -> bool) -> 'a list -> 'a
273 find p l returns the first element of the list l that satisfies the
276 predicate p . Raise Not_found if there is no value that satisfies p in
277 the list l .
278 val filter : ('a -> bool) -> 'a list -> 'a list
283 filter p l returns all the elements of the list l that satisfy the
286 predicate p . The order of the elements in the input list is pre‐
287 served.
288 val find_all : ('a -> bool) -> 'a list -> 'a list
293 find_all is another name for List.filter .
296 val partition : ('a -> bool) -> 'a list -> 'a list * 'a list
301 partition p l returns a pair of lists (l1, l2) , where l1 is the list
304 of all the elements of l that satisfy the predicate p , and l2 is the
305 list of all the elements of l that do not satisfy p . The order of the
306 elements in the input list is preserved.
307 === Association lists ===
313 val assoc : 'a -> ('a * 'b) list -> 'b
316 assoc a l returns the value associated with key a in the list of pairs
319 l . That is, assoc a [ ...; (a,b); ...] = b if (a,b) is the leftmost
320 binding of a in list l . Raise Not_found if there is no value associ‐
321 ated with a in the list l .
322 val assq : 'a -> ('a * 'b) list -> 'b
327 Same as List.assoc , but uses physical equality instead of structural
329 equality to compare keys.
330 val mem_assoc : 'a -> ('a * 'b) list -> bool
335 Same as List.assoc , but simply return true if a binding exists, and
337 false if no bindings exist for the given key.
338 val mem_assq : 'a -> ('a * 'b) list -> bool
343 Same as List.mem_assoc , but uses physical equality instead of struc‐
345 tural equality to compare keys.
346 val remove_assoc : 'a -> ('a * 'b) list -> ('a * 'b) list
351 remove_assoc a l returns the list of pairs l without the first pair
354 with key a , if any. Not tail-recursive.
355 val remove_assq : 'a -> ('a * 'b) list -> ('a * 'b) list
360 Same as List.remove_assoc , but uses physical equality instead of
362 structural equality to compare keys. Not tail-recursive.
363 === Lists of pairs ===
369 val split : ('a * 'b) list -> 'a list * 'b list
372 Transform a list of pairs into a pair of lists: split [(a1,b1); ...;
374 (an,bn)] is ([a1; ...; an], [b1; ...; bn]) . Not tail-recursive.
375 val combine : 'a list -> 'b list -> ('a * 'b) list
380 Transform a pair of lists into a list of pairs: combine [a1; ...; an]
382 [b1; ...; bn] is [(a1,b1); ...; (an,bn)] . Raise Invalid_argument if
383 the two lists have different lengths. Not tail-recursive.
384 === Sorting ===
390 val sort : ('a -> 'a -> int) -> 'a list -> 'a list
393 Sort a list in increasing order according to a comparison function.
395 The comparison function must return 0 if its arguments compare as
396 equal, a positive integer if the first is greater, and a negative inte‐
397 ger if the first is smaller (see Array.sort for a complete specifica‐
398 tion). For example, Pervasives.compare is a suitable comparison func‐
399 tion. The resulting list is sorted in increasing order. List.sort is
400 guaranteed to run in constant heap space (in addition to the size of
401 the result list) and logarithmic stack space.
402 The current implementation uses Merge Sort. It runs in constant heap
404 space and logarithmic stack space.
405 val stable_sort : ('a -> 'a -> int) -> 'a list -> 'a list
410 Same as List.sort , but the sorting algorithm is guaranteed to be sta‐
412 ble (i.e. elements that compare equal are kept in their original order)
413 .
414 The current implementation uses Merge Sort. It runs in constant heap
416 space and logarithmic stack space.
417 val fast_sort : ('a -> 'a -> int) -> 'a list -> 'a list
422 Same as List.sort or List.stable_sort , whichever is faster on typical
424 input.
425 val merge : ('a -> 'a -> int) -> 'a list -> 'a list -> 'a list
430 Merge two lists: Assuming that l1 and l2 are sorted according to the
432 comparison function cmp , merge cmp l1 l2 will return a sorted list
433 containting all the elements of l1 and l2 . If several elements com‐
434 pare equal, the elements of l1 will be before the elements of l2 . Not
435 tail-recursive (sum of the lengths of the arguments).
436OCamldoc 2007-05-24 List(3)