stdlib/listLabels.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 {!ListLabels.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 : f:('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 : f:('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 : f:('a -> 'b) -> 'a list -> 'b list
  84 (** [List.rev_map f l] gives the same result as
  85    {!ListLabels.rev}[ (]{!ListLabels.map}[ f l)], but is tail-recursive and
  86    more efficient. *)
  87
  88 val fold_left : f:('a -> 'b -> 'a) -> init:'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 : f:('a -> 'b -> 'b) -> 'a list -> init:'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 : f:('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 : f:('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 : f:('a -> 'b -> 'c) -> 'a list -> 'b list -> 'c list
 113 (** [List.rev_map2 f l1 l2] gives the same result as
 114    {!ListLabels.rev}[ (]{!ListLabels.map2}[ f l1 l2)], but is tail-recursive and
 115    more efficient. *)
 116
 117 val fold_left2 :
 118   f:('a -> 'b -> 'c -> 'a) -> init:'a -> 'b list -> 'c list -> 'a
 119 (** [List.fold_left2 f a [b1; ...; bn] [c1; ...; cn]] is
 120    [f (... (f (f a b1 c1) b2 c2) ...) bn cn].
 121    Raise [Invalid_argument] if the two lists have
 122    different lengths. *)
 123
 124 val fold_right2 :
 125   f:('a -> 'b -> 'c -> 'c) -> 'a list -> 'b list -> init:'c -> 'c
 126 (** [List.fold_right2 f [a1; ...; an] [b1; ...; bn] c] is
 127    [f a1 b1 (f a2 b2 (... (f an bn c) ...))].
 128    Raise [Invalid_argument] if the two lists have
 129    different lengths.  Not tail-recursive. *)
 130
 131
 132 (** {6 List scanning} *)
 133
 134
 135 val for_all : f:('a -> bool) -> 'a list -> bool
 136 (** [for_all p [a1; ...; an]] checks if all elements of the list
 137    satisfy the predicate [p]. That is, it returns
 138    [(p a1) && (p a2) && ... && (p an)]. *)
 139
 140 val exists : f:('a -> bool) -> 'a list -> bool
 141 (** [exists p [a1; ...; an]] checks if at least one element of
 142    the list satisfies the predicate [p]. That is, it returns
 143    [(p a1) || (p a2) || ... || (p an)]. *)
 144
 145 val for_all2 : f:('a -> 'b -> bool) -> 'a list -> 'b list -> bool
 146 (** Same as {!ListLabels.for_all}, but for a two-argument predicate.
 147    Raise [Invalid_argument] if the two lists have
 148    different lengths. *)
 149
 150 val exists2 : f:('a -> 'b -> bool) -> 'a list -> 'b list -> bool
 151 (** Same as {!ListLabels.exists}, but for a two-argument predicate.
 152    Raise [Invalid_argument] if the two lists have
 153    different lengths. *)
 154
 155 val mem : 'a -> set:'a list -> bool
 156 (** [mem a l] is true if and only if [a] is equal
 157    to an element of [l]. *)
 158
 159 val memq : 'a -> set:'a list -> bool
 160 (** Same as {!ListLabels.mem}, but uses physical equality instead of structural
 161    equality to compare list elements. *)
 162
 163
 164 (** {6 List searching} *)
 165
 166
 167 val find : f:('a -> bool) -> 'a list -> 'a
 168 (** [find p l] returns the first element of the list [l]
 169    that satisfies the predicate [p].
 170    Raise [Not_found] if there is no value that satisfies [p] in the
 171    list [l]. *)
 172
 173 val filter : f:('a -> bool) -> 'a list -> 'a list
 174 (** [filter p l] returns all the elements of the list [l]
 175    that satisfy the predicate [p].  The order of the elements
 176    in the input list is preserved.  *)
 177
 178 val find_all : f:('a -> bool) -> 'a list -> 'a list
 179 (** [find_all] is another name for {!ListLabels.filter}. *)
 180
 181 val partition : f:('a -> bool) -> 'a list -> 'a list * 'a list
 182 (** [partition p l] returns a pair of lists [(l1, l2)], where
 183    [l1] is the list of all the elements of [l] that
 184    satisfy the predicate [p], and [l2] is the list of all the
 185    elements of [l] that do not satisfy [p].
 186    The order of the elements in the input list is preserved. *)
 187
 188
 189 (** {6 Association lists} *)
 190
 191
 192 val assoc : 'a -> ('a * 'b) list -> 'b
 193 (** [assoc a l] returns the value associated with key [a] in the list of
 194    pairs [l]. That is,
 195    [assoc a [ ...; (a,b); ...] = b]
 196    if [(a,b)] is the leftmost binding of [a] in list [l].
 197    Raise [Not_found] if there is no value associated with [a] in the
 198    list [l]. *)
 199
 200 val assq : 'a -> ('a * 'b) list -> 'b
 201 (** Same as {!ListLabels.assoc}, but uses physical equality instead of
 202    structural equality to compare keys. *)
 203
 204 val mem_assoc : 'a -> map:('a * 'b) list -> bool
 205 (** Same as {!ListLabels.assoc}, but simply return true if a binding exists,
 206    and false if no bindings exist for the given key. *)
 207
 208 val mem_assq : 'a -> map:('a * 'b) list -> bool
 209 (** Same as {!ListLabels.mem_assoc}, but uses physical equality instead of
 210    structural equality to compare keys. *)
 211
 212 val remove_assoc : 'a -> ('a * 'b) list -> ('a * 'b) list
 213 (** [remove_assoc a l] returns the list of
 214    pairs [l] without the first pair with key [a], if any.
 215    Not tail-recursive. *)
 216
 217 val remove_assq : 'a -> ('a * 'b) list -> ('a * 'b) list
 218 (** Same as {!ListLabels.remove_assoc}, but uses physical equality instead
 219    of structural equality to compare keys.  Not tail-recursive. *)
 220
 221
 222 (** {6 Lists of pairs} *)
 223
 224
 225 val split : ('a * 'b) list -> 'a list * 'b list
 226 (** Transform a list of pairs into a pair of lists:
 227    [split [(a1,b1); ...; (an,bn)]] is [([a1; ...; an], [b1; ...; bn])].
 228    Not tail-recursive.
 229 *)
 230
 231 val combine : 'a list -> 'b list -> ('a * 'b) list
 232 (** Transform a pair of lists into a list of pairs:
 233    [combine [a1; ...; an] [b1; ...; bn]] is
 234    [[(a1,b1); ...; (an,bn)]].
 235    Raise [Invalid_argument] if the two lists
 236    have different lengths.  Not tail-recursive. *)
 237
 238
 239 (** {6 Sorting} *)
 240
 241
 242 val sort : cmp:('a -> 'a -> int) -> 'a list -> 'a list
 243 (** Sort a list in increasing order according to a comparison
 244    function.  The comparison function must return 0 if its arguments
 245    compare as equal, a positive integer if the first is greater,
 246    and a negative integer if the first is smaller (see Array.sort for
 247    a complete specification).  For example,
 248    {!Pervasives.compare} is a suitable comparison function.
 249    The resulting list is sorted in increasing order.
 250    [List.sort] is guaranteed to run in constant heap space
 251    (in addition to the size of the result list) and logarithmic
 252    stack space.
 253
 254    The current implementation uses Merge Sort. It runs in constant
 255    heap space and logarithmic stack space.
 256 *)
 257
 258 val stable_sort : cmp:('a -> 'a -> int) -> 'a list -> 'a list
 259 (** Same as {!ListLabels.sort}, but the sorting algorithm is guaranteed to
 260    be stable (i.e. elements that compare equal are kept in their
 261    original order) .
 262
 263    The current implementation uses Merge Sort. It runs in constant
 264    heap space and logarithmic stack space.
 265 *)
 266
 267 val fast_sort : cmp:('a -> 'a -> int) -> 'a list -> 'a list
 268 (** Same as {!List.sort} or {!List.stable_sort}, whichever is faster
 269     on typical input. *)
 270
 271 val merge : cmp:('a -> 'a -> int) -> 'a list -> 'a list -> 'a list
 272 (** Merge two lists:
 273     Assuming that [l1] and [l2] are sorted according to the
 274     comparison function [cmp], [merge cmp l1 l2] will return a
 275     sorted list containting all the elements of [l1] and [l2].
 276     If several elements compare equal, the elements of [l1] will be
 277     before the elements of [l2].
 278     Not tail-recursive (sum of the lengths of the arguments).
 279 *)