stdlib/list.mli

   1 (***********************************************************************)
   2 (*                                                                     *)
   3 (*                           Objective Caml                            *)
   4 (*                                                                     *)
   5 (*            Xavier Leroy, projet Cristal, INRIA Rocquencourt         *)
   6 (*                                                                     *)
   7 (*  Copyright 1996 Institut National de Recherche en Informatique et   *)
   8 (*  en Automatique.  All rights reserved.  This file is distributed    *)
   9 (*  under the terms of the GNU Library General Public License, with    *)
  10 (*  the special exception on linking described in file ../LICENSE.     *)
  11 (*                                                                     *)
  12 (***********************************************************************)
  13
  14 (* $Id$ *)
  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 val length : 'a list -> int
  30 (** Return the length (number of elements) of the given list. *)
  31
  32 val hd : 'a list -> 'a
  33 (** Return the first element of the given list. Raise
  34    [Failure "hd"] if the list is empty. *)
  35
  36 val tl : 'a list -> 'a list
  37 (** Return the given list without its first element. Raise
  38    [Failure "tl"] if the list is empty. *)
  39
  40 val nth : 'a list -> int -> 'a
  41 (** Return the [n]-th element of the given list.
  42    The first element (head of the list) is at position 0.
  43    Raise [Failure "nth"] if the list is too short.
  44    Raise [Invalid_argument "List.nth"] if [n] is negative. *)
  45
  46 val rev : 'a list -> 'a list
  47 (** List reversal. *)
  48
  49 val append : 'a list -> 'a list -> 'a list
  50 (** Catenate two lists.  Same function as the infix operator [@].
  51    Not tail-recursive (length of the first argument).  The [@]
  52    operator is not tail-recursive either. *)
  53
  54 val rev_append : 'a list -> 'a list -> 'a list
  55 (** [List.rev_append l1 l2] reverses [l1] and concatenates it to [l2].
  56    This is equivalent to {!List.rev}[ l1 @ l2], but [rev_append] is
  57    tail-recursive and more efficient. *)
  58
  59 val concat : 'a list list -> 'a list
  60 (** Concatenate a list of lists.  The elements of the argument are all
  61    concatenated together (in the same order) to give the result.
  62    Not tail-recursive
  63    (length of the argument + length of the longest sub-list). *)
  64
  65 val flatten : 'a list list -> 'a list
  66 (** Same as [concat].  Not tail-recursive
  67    (length of the argument + length of the longest sub-list). *)
  68
  69
  70 (** {6 Iterators} *)
  71
  72
  73 val iter : ('a -> unit) -> 'a list -> unit
  74 (** [List.iter f [a1; ...; an]] applies function [f] in turn to
  75    [a1; ...; an]. It is equivalent to
  76    [begin f a1; f a2; ...; f an; () end]. *)
  77
  78 val map : ('a -> 'b) -> 'a list -> 'b list
  79 (** [List.map f [a1; ...; an]] applies function [f] to [a1, ..., an],
  80    and builds the list [[f a1; ...; f an]]
  81    with the results returned by [f].  Not tail-recursive. *)
  82
  83 val rev_map : ('a -> 'b) -> 'a list -> 'b list
  84 (** [List.rev_map f l] gives the same result as
  85    {!List.rev}[ (]{!List.map}[ f l)], but is tail-recursive and
  86    more efficient. *)
  87
  88 val fold_left : ('a -> 'b -> 'a) -> 'a -> 'b list -> 'a
  89 (** [List.fold_left f a [b1; ...; bn]] is
  90    [f (... (f (f a b1) b2) ...) bn]. *)
  91
  92 val fold_right : ('a -> 'b -> 'b) -> 'a list -> 'b -> 'b
  93 (** [List.fold_right f [a1; ...; an] b] is
  94    [f a1 (f a2 (... (f an b) ...))].  Not tail-recursive. *)
  95
  96
  97 (** {6 Iterators on two lists} *)
  98
  99
 100 val iter2 : ('a -> 'b -> unit) -> 'a list -> 'b list -> unit
 101 (** [List.iter2 f [a1; ...; an] [b1; ...; bn]] calls in turn
 102    [f a1 b1; ...; f an bn].
 103    Raise [Invalid_argument] if the two lists have
 104    different lengths. *)
 105
 106 val map2 : ('a -> 'b -> 'c) -> 'a list -> 'b list -> 'c list
 107 (** [List.map2 f [a1; ...; an] [b1; ...; bn]] is
 108    [[f a1 b1; ...; f an bn]].
 109    Raise [Invalid_argument] if the two lists have
 110    different lengths.  Not tail-recursive. *)
 111
 112 val rev_map2 : ('a -> 'b -> 'c) -> 'a list -> 'b list -> 'c list
 113 (** [List.rev_map2 f l1 l2] gives the same result as
 114    {!List.rev}[ (]{!List.map2}[ f l1 l2)], but is tail-recursive and
 115    more efficient. *)
 116
 117 val fold_left2 : ('a -> 'b -> 'c -> 'a) -> 'a -> 'b list -> 'c list -> 'a
 118 (** [List.fold_left2 f a [b1; ...; bn] [c1; ...; cn]] is
 119    [f (... (f (f a b1 c1) b2 c2) ...) bn cn].
 120    Raise [Invalid_argument] if the two lists have
 121    different lengths. *)
 122
 123 val fold_right2 : ('a -> 'b -> 'c -> 'c) -> 'a list -> 'b list -> 'c -> 'c
 124 (** [List.fold_right2 f [a1; ...; an] [b1; ...; bn] c] is
 125    [f a1 b1 (f a2 b2 (... (f an bn c) ...))].
 126    Raise [Invalid_argument] if the two lists have
 127    different lengths.  Not tail-recursive. *)
 128
 129
 130 (** {6 List scanning} *)
 131
 132
 133 val for_all : ('a -> bool) -> 'a list -> bool
 134 (** [for_all p [a1; ...; an]] checks if all elements of the list
 135    satisfy the predicate [p]. That is, it returns
 136    [(p a1) && (p a2) && ... && (p an)]. *)
 137
 138 val exists : ('a -> bool) -> 'a list -> bool
 139 (** [exists p [a1; ...; an]] checks if at least one element of
 140    the list satisfies the predicate [p]. That is, it returns
 141    [(p a1) || (p a2) || ... || (p an)]. *)
 142
 143 val for_all2 : ('a -> 'b -> bool) -> 'a list -> 'b list -> bool
 144 (** Same as {!List.for_all}, but for a two-argument predicate.
 145    Raise [Invalid_argument] if the two lists have
 146    different lengths. *)
 147
 148 val exists2 : ('a -> 'b -> bool) -> 'a list -> 'b list -> bool
 149 (** Same as {!List.exists}, but for a two-argument predicate.
 150    Raise [Invalid_argument] if the two lists have
 151    different lengths. *)
 152
 153 val mem : 'a -> 'a list -> bool
 154 (** [mem a l] is true if and only if [a] is equal
 155    to an element of [l]. *)
 156
 157 val memq : 'a -> 'a list -> bool
 158 (** Same as {!List.mem}, but uses physical equality instead of structural
 159    equality to compare list elements. *)
 160
 161
 162 (** {6 List searching} *)
 163
 164
 165 val find : ('a -> bool) -> 'a list -> 'a
 166 (** [find p l] returns the first element of the list [l]
 167    that satisfies the predicate [p].
 168    Raise [Not_found] if there is no value that satisfies [p] in the
 169    list [l]. *)
 170
 171 val filter : ('a -> bool) -> 'a list -> 'a list
 172 (** [filter p l] returns all the elements of the list [l]
 173    that satisfy the predicate [p].  The order of the elements
 174    in the input list is preserved.  *)
 175
 176 val find_all : ('a -> bool) -> 'a list -> 'a list
 177 (** [find_all] is another name for {!List.filter}. *)
 178
 179 val partition : ('a -> bool) -> 'a list -> 'a list * 'a list
 180 (** [partition p l] returns a pair of lists [(l1, l2)], where
 181    [l1] is the list of all the elements of [l] that
 182    satisfy the predicate [p], and [l2] is the list of all the
 183    elements of [l] that do not satisfy [p].
 184    The order of the elements in the input list is preserved. *)
 185
 186
 187 (** {6 Association lists} *)
 188
 189
 190 val assoc : 'a -> ('a * 'b) list -> 'b
 191 (** [assoc a l] returns the value associated with key [a] in the list of
 192    pairs [l]. That is,
 193    [assoc a [ ...; (a,b); ...] = b]
 194    if [(a,b)] is the leftmost binding of [a] in list [l].
 195    Raise [Not_found] if there is no value associated with [a] in the
 196    list [l]. *)
 197
 198 val assq : 'a -> ('a * 'b) list -> 'b
 199 (** Same as {!List.assoc}, but uses physical equality instead of structural
 200    equality to compare keys. *)
 201
 202 val mem_assoc : 'a -> ('a * 'b) list -> bool
 203 (** Same as {!List.assoc}, but simply return true if a binding exists,
 204    and false if no bindings exist for the given key. *)
 205
 206 val mem_assq : 'a -> ('a * 'b) list -> bool
 207 (** Same as {!List.mem_assoc}, but uses physical equality instead of
 208    structural equality to compare keys. *)
 209
 210 val remove_assoc : 'a -> ('a * 'b) list -> ('a * 'b) list
 211 (** [remove_assoc a l] returns the list of
 212    pairs [l] without the first pair with key [a], if any.
 213    Not tail-recursive. *)
 214
 215 val remove_assq : 'a -> ('a * 'b) list -> ('a * 'b) list
 216 (** Same as {!List.remove_assoc}, but uses physical equality instead
 217    of structural equality to compare keys.  Not tail-recursive. *)
 218
 219
 220 (** {6 Lists of pairs} *)
 221
 222
 223 val split : ('a * 'b) list -> 'a list * 'b list
 224 (** Transform a list of pairs into a pair of lists:
 225    [split [(a1,b1); ...; (an,bn)]] is [([a1; ...; an], [b1; ...; bn])].
 226    Not tail-recursive.
 227 *)
 228
 229 val combine : 'a list -> 'b list -> ('a * 'b) list
 230 (** Transform a pair of lists into a list of pairs:
 231    [combine [a1; ...; an] [b1; ...; bn]] is
 232    [[(a1,b1); ...; (an,bn)]].
 233    Raise [Invalid_argument] if the two lists
 234    have different lengths.  Not tail-recursive. *)
 235
 236
 237 (** {6 Sorting} *)
 238
 239
 240 val sort : ('a -> 'a -> int) -> 'a list -> 'a list
 241 (** Sort a list in increasing order according to a comparison
 242    function.  The comparison function must return 0 if its arguments
 243    compare as equal, a positive integer if the first is greater,
 244    and a negative integer if the first is smaller (see Array.sort for
 245    a complete specification).  For example,
 246    {!Pervasives.compare} is a suitable comparison function.
 247    The resulting list is sorted in increasing order.
 248    [List.sort] is guaranteed to run in constant heap space
 249    (in addition to the size of the result list) and logarithmic
 250    stack space.
 251
 252    The current implementation uses Merge Sort. It runs in constant
 253    heap space and logarithmic stack space.
 254 *)
 255
 256 val stable_sort : ('a -> 'a -> int) -> 'a list -> 'a list
 257 (** Same as {!List.sort}, but the sorting algorithm is guaranteed to
 258    be stable (i.e. elements that compare equal are kept in their
 259    original order) .
 260
 261    The current implementation uses Merge Sort. It runs in constant
 262    heap space and logarithmic stack space.
 263 *)
 264
 265 val fast_sort : ('a -> 'a -> int) -> 'a list -> 'a list
 266 (** Same as {!List.sort} or {!List.stable_sort}, whichever is faster
 267     on typical input. *)
 268
 269 val merge : ('a -> 'a -> int) -> 'a list -> 'a list -> 'a list
 270 (** Merge two lists:
 271     Assuming that [l1] and [l2] are sorted according to the
 272     comparison function [cmp], [merge cmp l1 l2] will return a
 273     sorted list containting all the elements of [l1] and [l2].
 274     If several elements compare equal, the elements of [l1] will be
 275     before the elements of [l2].
 276     Not tail-recursive (sum of the lengths of the arguments).
 277 *)
 278
 279 val cons : 'a -> 'a list -> 'a list
 280 (** Same as constructor [::], but as a function *)
 281
 282 val count : ('a -> bool) -> 'a list -> int
 283 (** [count pred l] returns the number of elements [e] of [l] for which [pred e] evaluates to true *)
 284
 285 val positions : ('a -> bool) -> 'a list -> int list
 286 (** [positions pred l] returns a list of positions at which elements [e] of [l] make [pred e] true.  ex: [positions (fun x -> x > 2) [1; 3; 5; 2; 4]] returns [[1; 2; 4]] *)
 287
 288 val mapi : (int -> 'a -> 'b) -> 'a list -> 'b list
 289 (** [mapi f l] will build the list containing
 290     [(f 0 a0);(f 1 a1) ... (f n an)] where [a0..an] are the elements of
 291     the list [l]. *)
 292
 293 val split_nth : int -> 'a list -> 'a list * 'a list
 294 (** [List.split_nth pos l] returns the prefix of l up to pos and the remaining elements of l *)
 295
 296 val take : int -> 'a list -> 'a list
 297   (** [take n l] returns up to the [n] first elements from list [l], if
 298       available. *)
 299
 300 val drop : int -> 'a list -> 'a list
 301   (** [drop n l] returns [l] without the first [n] elements, or the empty
 302       list if [l] have less than [n] elements. *)
 303
 304 val takewhile : ('a -> bool) -> 'a list -> 'a list
 305   (** [takewhile f xs] returns the first elements of list [xs]
 306       which satisfy the predicate [f]. *)
 307
 308 val dropwhile : ('a -> bool) -> 'a list -> 'a list
 309   (** [dropwhile f xs] returns the list [xs] with the first
 310       elements satisfying the predicate [f] dropped. *)
 311
 312 val reduce : ('a -> 'a -> 'a) -> 'a list -> 'a
 313 (** [reduce f l] applies [f] as fold_left, but with first element as initial value.  Raises Failure "tl" if [l] is empty. *)
 314
 315 val make : int -> 'a -> 'a list
 316 (** Similar to [String.make], [make n x] returns a
 317     * list containing [n] elements [x].
 318 *)
 319
 320 val unique : ?cmp:('a -> 'a -> bool) -> 'a list -> 'a list
 321 (** [unique cmp l] returns the list [l] without any duplicate element.
 322     Default comparator ( = ) is used if no comparison function specified. *)
 323
 324 val filter_map : ('a -> 'b option) -> 'a list -> 'b list
 325 (** [List.filter_map f l] works as map and filter together - return [None] in [f] to remove that element from the list, return [Some b] to put [b] in the output list *)
 326
 327 val rfind : ('a -> bool) -> 'a list -> 'a
 328 (** [rfind p l] returns the last element [x] of [l] such as [p x] returns
 329     [true] or raises [Not_found] if such element as not been found. *)
 330
 331 val findi : (int -> 'a -> bool) -> 'a list -> (int * 'a)
 332 (** [findi p e l] returns the first element [ai] of [l] along with its
 333     index [i] such that [p i ai] is true, or raises [Not_found] if no
 334     such element has been found. *)
 335
 336 val find_exc : ('a -> bool) -> exn -> 'a list -> 'a
 337 (** [find_exc p e l] returns the first element of [l] such as [p x]
 338     returns [true] or raises [e] if such element as not been found. *)
 339
 340 val init : int -> (int -> 'a) -> 'a list
 341 (** Similar to [Array.init], [init n f] returns the list containing
 342     the results of (f 0),(f 1).... (f (n-1)).
 343     Raise [Invalid_arg "ExtList.init"] if n < 0.*)
 344
 345 val iteri : (int -> 'a -> 'b) -> 'a list -> unit
 346 (** [iteri f l] will call [(f 0 a0);(f 1 a1) ... (f n an)] where
 347     [a0..an] are the elements of the list [l]. *)
 348
 349 val first : 'a list -> 'a
 350 (** Returns the first element of a list (as [List.hd]) *)
 351
 352 val last : 'a list -> 'a
 353 (** Returns the last element of a list (not the same as [List.tl]) *)
 354
 355 val (--) : int -> int -> int list
 356 (** m--n returns the list of values from m to n (excluding n) *)