module Array: Extlib.ExtArray.Array
Array operations.
Arrays are mutable data structures with a fixed size, which support fast access and modification, and are used pervasively in imperative computing. While arrays are completely supported in OCaml, it is often a good idea to investigate persistent alternatives, such as lists or hash maps.
A variant of arrays, arrays with capabilities, is provided in
module Array.Cap
. This notion of capabilities permit the transformation
of a mutable array into a read-only or a write-only arrays, without
loss of speed and with the possibility of distributing different
capabilities to different expressions.
Author(s): Xavier Leroy, Richard W.M. Jones, David Teller
type'a
t ='a array
include Array.Enumerable
include Array.Mappable
val length : 'a array -> int
val get : 'a array -> int -> 'a
Array.get a n
returns the element number n
of array a
.
The first element has number 0.
The last element has number Array.length a - 1
.
You can also write a.(n)
instead of Array.get a n
.Invalid_argument
"index out of bounds"
if n
is outside the range 0 to (Array.length a - 1)
.val set : 'a array -> int -> 'a -> unit
Array.set a n x
modifies array a
in place, replacing
element number n
with x
.
You can also write a.(n) <- x
instead of Array.set a n x
.Invalid_argument
"index out of bounds"
if n
is outside the range 0 to Array.length a - 1
.val make : int -> 'a -> 'a array
Array.make n x
returns a fresh array of length n
,
initialized with x
.
All the elements of this new array are initially
physically equal to x
(in the sense of the ==
predicate).
Consequently, if x
is mutable, it is shared among all elements
of the array, and modifying x
through one of the array entries
will modify all other entries at the same time.Invalid_argument
if n < 0
or n > Sys.max_array_length
.
If the value of x
is a floating-point number, then the maximum
size is only Sys.max_array_length / 2
.val create : int -> 'a -> 'a array
val init : int -> (int -> 'a) -> 'a array
Array.init n f
returns a fresh array of length n
,
with element number i
initialized to the result of f i
.
In other terms, Array.init n f
tabulates the results of f
applied to the integers 0
to n-1
.Invalid_argument
if n < 0
or n > Sys.max_array_length
.
If the return type of f
is float
, then the maximum
size is only Sys.max_array_length / 2
.val make_matrix : int -> int -> 'a -> 'a array array
Array.make_matrix dimx dimy e
returns a two-dimensional array
(an array of arrays) with first dimension dimx
and
second dimension dimy
. All the elements of this new matrix
are initially physically equal to e
.
The element (x,y
) of a matrix m
is accessed
with the notation m.(x).(y)
.Invalid_argument
if dimx
or dimy
is negative or
greater than Sys.max_array_length
.
If the value of e
is a floating-point number, then the maximum
size is only Sys.max_array_length / 2
.val create_matrix : int -> int -> 'a -> 'a array array
val iter : ('a -> unit) -> 'a array -> unit
Array.iter f a
applies function f
in turn to all
the elements of a
. It is equivalent to
f a.(0); f a.(1); ...; f a.(Array.length a - 1); ()
.val map : ('a -> 'b) -> 'a array -> 'b array
Array.map f a
applies function f
to all the elements of a
,
and builds an array with the results returned by f
:
[| f a.(0); f a.(1); ...; f a.(Array.length a - 1) |]
.val iteri : (int -> 'a -> unit) -> 'a array -> unit
Array.iter
, but the
function is applied to the index of the element as first argument,
and the element itself as second argument.val mapi : (int -> 'a -> 'b) -> 'a array -> 'b array
Array.map
, but the
function is applied to the index of the element as first argument,
and the element itself as second argument.val fold_left : ('a -> 'b -> 'a) -> 'a -> 'b array -> 'a
Array.fold_left f x a
computes
f (... (f (f x a.(0)) a.(1)) ...) a.(n-1)
,
where n
is the length of the array a
.val fold_right : ('a -> 'b -> 'b) -> 'a array -> 'b -> 'b
Array.fold_right f a x
computes
f a.(0) (f a.(1) ( ... (f a.(n-1) x) ...))
,
where n
is the length of the array a
.val reduce : ('a -> 'a -> 'a) -> 'a array -> 'a
Array.reduce f a
is fold_left f a.(0) a.(1 .. n-1)
.Invalid_argument
on empty arrays.val max : 'a array -> 'a
max a
returns the largest value in a
as judged by
Pervasives.compare
val min : 'a array -> 'a
min a
returns the smallest value in a
as judged by
Pervasives.compare
val iter2 : ('a -> 'b -> unit) -> 'a array -> 'b array -> unit
Array.iter2 f [|a1; ...; an|] [|b1; ...; bn|]
performs
calls f a1 b1; ...; f an bn
in that order.Invalid_argument
if the length of a1
does not equal the
length of a2
.val iter2i : (int -> 'a -> 'b -> unit) -> 'a array -> 'b array -> unit
Array.iter2i f [|a1; ...; an|] [|b1; ...; bn|]
performs
calls f 0 a1 b1; ...; f (n - 1) an bn
in that order.Invalid_argument
if the length of a1
does not equal the
length of a2
.val for_all : ('a -> bool) -> 'a array -> bool
for_all p [a1; ...; an]
checks if all elements of the array
satisfy the predicate p
. That is, it returns
(p a1) && (p a2) && ... && (p an)
.val exists : ('a -> bool) -> 'a array -> bool
exists p [a1; ...; an]
checks if at least one element of
the array satisfies the predicate p
. That is, it returns
(p a1) || (p a2) || ... || (p an)
.val find : ('a -> bool) -> 'a array -> 'a
find p a
returns the first element of array a
that satisfies the predicate p
.Not_found
if there is no value that satisfies p
in the
array a
.val mem : 'a -> 'a array -> bool
mem m a
is true if and only if m
is equal to an element of a
.val memq : 'a -> 'a array -> bool
Array.mem
but uses physical equality instead of
structural equality to compare array elements.val findi : ('a -> bool) -> 'a array -> int
findi p a
returns the index of the first element of array a
that satisfies the predicate p
.Not_found
if there is no value that satisfies p
in the
array a
.val filter : ('a -> bool) -> 'a array -> 'a array
filter p a
returns all the elements of the array a
that satisfy the predicate p
. The order of the elements
in the input array is preserved.val filter_map : ('a -> 'b option) -> 'a array -> 'b array
filter_map f e
returns an array consisting in all elements
x
such that f y
returns Some x
, where y
is an element
of e
.val find_all : ('a -> bool) -> 'a array -> 'a array
val partition : ('a -> bool) -> 'a array -> 'a array * 'a array
partition p a
returns a pair of arrays (a1, a2)
, where
a1
is the array of all the elements of a
that
satisfy the predicate p
, and a2
is the array of all the
elements of a
that do not satisfy p
.
The order of the elements in the input array is preserved.val rev : 'a array -> 'a array
val rev_in_place : 'a array -> unit
val append : 'a array -> 'a array -> 'a array
Array.append v1 v2
returns a fresh array containing the
concatenation of the arrays v1
and v2
.val concat : 'a array list -> 'a array
Array.append
, but concatenates a list of arrays.val sub : 'a array -> int -> int -> 'a array
Array.sub a start len
returns a fresh array of length len
,
containing the elements number start
to start + len - 1
of array a
.Invalid_argument
"Array.sub"
if start
and len
do not
designate a valid subarray of a
; that is, if
start < 0
, or len < 0
, or start + len > Array.length a
.val copy : 'a array -> 'a array
Array.copy a
returns a copy of a
, that is, a fresh array
containing the same elements as a
.val fill : 'a array -> int -> int -> 'a -> unit
Array.fill a ofs len x
modifies the array a
in place,
storing x
in elements number ofs
to ofs + len - 1
.Invalid_argument
"Array.fill"
if ofs
and len
do not
designate a valid subarray of a
.val blit : 'a array -> int -> 'a array -> int -> int -> unit
Array.blit v1 o1 v2 o2 len
copies len
elements
from array v1
, starting at element number o1
, to array v2
,
starting at element number o2
. It works correctly even if
v1
and v2
are the same array, and the source and
destination chunks overlap.Invalid_argument
"Array.blit"
if o1
and len
do not
designate a valid subarray of v1
, or if o2
and len
do not
designate a valid subarray of v2
.val enum : 'a array -> 'a Enum.t
val of_enum : 'a Enum.t -> 'a array
val backwards : 'a array -> 'a Enum.t
val of_backwards : 'a Enum.t -> 'a array
val to_list : 'a array -> 'a list
Array.to_list a
returns the list of all the elements of a
.val of_list : 'a list -> 'a array
Array.of_list l
returns a fresh array containing the elements
of l
.val make_compare : ('a -> 'a -> int) -> 'a array -> 'a array -> int
make_compare c
generates the lexicographical order on arrays
induced by c
val sort : ('a -> 'a -> int) -> 'a array -> unit
Standard.compare
is
a suitable comparison function, provided there are no floating-point
NaN values in the data. After calling Array.sort
, the
array is sorted in place in increasing order.
Array.sort
is guaranteed to run in constant heap space
and (at most) logarithmic stack space.
The current implementation uses Heap Sort. It runs in constant stack space.
Specification of the comparison function:
Let a
be the array and cmp
the comparison function. The following
must be true for all x, y, z in a :
cmp x y
> 0 if and only if cmp y x
< 0cmp x y
>= 0 and cmp y z
>= 0 then cmp x z
>= 0Array.sort
returns, a
contains the same elements as before,
reordered in such a way that for all i and j valid indices of a
:cmp a.(i) a.(j)
>= 0 if and only if i >= jval stable_sort : ('a -> 'a -> int) -> 'a array -> unit
Array.sort
, but the sorting algorithm is stable (i.e.
elements that compare equal are kept in their original order) and
not guaranteed to run in constant heap space.
The current implementation uses Merge Sort. It uses n/2
words of heap space, where n
is the length of the array.
It is usually faster than the current implementation of Array.sort
.
val fast_sort : ('a -> 'a -> int) -> 'a array -> unit
val t_of_sexp : (Sexplib.Sexp.t -> 'a) -> Sexplib.Sexp.t -> 'a t
val sexp_of_t : ('a -> Sexplib.Sexp.t) -> 'a t -> Sexplib.Sexp.t
val print : ?first:string ->
?last:string ->
?sep:string ->
('a IO.output -> 'b -> unit) ->
'a IO.output -> 'b t -> unit
val sprint : ?first:string ->
?last:string ->
?sep:string ->
('a IO.output -> 'b -> unit) -> 'b t -> string
val t_printer : 'a Value_printer.t ->
'a t Value_printer.t
module Array.Cap:sig
..end
val t_of_sexp : (Sexplib.Sexp.t -> 'a) -> Sexplib.Sexp.t -> 'a t
val sexp_of_t : ('a -> Sexplib.Sexp.t) -> 'a t -> Sexplib.Sexp.t
val print : ?first:string ->
?last:string ->
?sep:string ->
('a IO.output -> 'b -> unit) ->
'a IO.output -> 'b t -> unit
val sprint : ?first:string ->
?last:string ->
?sep:string ->
('a IO.output -> 'b -> unit) -> 'b t -> string
Array
with functions
behaving slightly differently but having the same name. This is by design:
the functions meant to override the corresponding functions of Array
.
To take advantage of these overrides, you probably want to
or . For instance, to open a version of Array
with exceptionless error management, you may write open Array,
Exceptionless
. To locally replace module Array
with a module of
the same name but with exceptionless error management, you may
write module Array = Array include Exceptionless
.
module Array.Exceptionless:sig
..end
Array
without exceptions.
module Array.Labels:sig
..end
Array
with labels.