1Array(3) OCaml library Array(3)
2
6 Array - Array operations.
7
9 Module Array
10
12 Module Array
13 : sig end
14 Array operations.
17 The labeled version of this module can be used as described in the Std‐
19 Labels module.
20 type 'a t = 'a array
26 An alias for the type of arrays.
29 val length : 'a array -> int
33 Return the length (number of elements) of the given array.
35 val get : 'a array -> int -> 'a
39 get a n returns the element number n of array a . The first element
42 has number 0. The last element has number length a - 1 . You can also
43 write a.(n) instead of get a n .
44 Raises Invalid_argument if n is outside the range 0 to (length a - 1) .
47 val set : 'a array -> int -> 'a -> unit
51 set a n x modifies array a in place, replacing element number n with x
54 . You can also write a.(n) <- x instead of set a n x .
55 Raises Invalid_argument if n is outside the range 0 to length a - 1 .
58 val make : int -> 'a -> 'a array
62 make n x returns a fresh array of length n , initialized with x . All
65 the elements of this new array are initially physically equal to x (in
66 the sense of the == predicate). Consequently, if x is mutable, it is
67 shared among all elements of the array, and modifying x through one of
68 the array entries will modify all other entries at the same time.
69 Raises Invalid_argument if n < 0 or n > Sys.max_array_length . If the
72 value of x is a floating-point number, then the maximum size is only
73 Sys.max_array_length / 2 .
74 val create_float : int -> float array
78 create_float n returns a fresh float array of length n , with unini‐
81 tialized data.
82 Since 4.03
85 val init : int -> (int -> 'a) -> 'a array
89 init n f returns a fresh array of length n , with element number i ini‐
92 tialized to the result of f i . In other terms, init n f tabulates the
93 results of f applied to the integers 0 to n-1 .
94 Raises Invalid_argument if n < 0 or n > Sys.max_array_length . If the
97 return type of f is float , then the maximum size is only Sys.max_ar‐
98 ray_length / 2 .
99 val make_matrix : int -> int -> 'a -> 'a array array
103 make_matrix dimx dimy e returns a two-dimensional array (an array of
106 arrays) with first dimension dimx and second dimension dimy . All the
107 elements of this new matrix are initially physically equal to e . The
108 element ( x,y ) of a matrix m is accessed with the notation m.(x).(y) .
109 Raises Invalid_argument if dimx or dimy is negative or greater than
112 Sys.max_array_length . If the value of e is a floating-point number,
113 then the maximum size is only Sys.max_array_length / 2 .
114 val append : 'a array -> 'a array -> 'a array
118 append v1 v2 returns a fresh array containing the concatenation of the
121 arrays v1 and v2 .
122 Raises Invalid_argument if length v1 + length v2 > Sys.max_array_length
125 .
126 val concat : 'a array list -> 'a array
130 Same as Array.append , but concatenates a list of arrays.
132 val sub : 'a array -> int -> int -> 'a array
136 sub a pos len returns a fresh array of length len , containing the ele‐
139 ments number pos to pos + len - 1 of array a .
140 Raises Invalid_argument if pos and len do not designate a valid subar‐
143 ray of a ; that is, if pos < 0 , or len < 0 , or pos + len > length a .
144 val copy : 'a array -> 'a array
148 copy a returns a copy of a , that is, a fresh array containing the same
151 elements as a .
152 val fill : 'a array -> int -> int -> 'a -> unit
156 fill a pos len x modifies the array a in place, storing x in elements
159 number pos to pos + len - 1 .
160 Raises Invalid_argument if pos and len do not designate a valid subar‐
163 ray of a .
164 val blit : 'a array -> int -> 'a array -> int -> int -> unit
168 blit src src_pos dst dst_pos len copies len elements from array src ,
171 starting at element number src_pos , to array dst , starting at element
172 number dst_pos . It works correctly even if src and dst are the same
173 array, and the source and destination chunks overlap.
174 Raises Invalid_argument if src_pos and len do not designate a valid
177 subarray of src , or if dst_pos and len do not designate a valid subar‐
178 ray of dst .
179 val to_list : 'a array -> 'a list
183 to_list a returns the list of all the elements of a .
186 val of_list : 'a list -> 'a array
190 of_list l returns a fresh array containing the elements of l .
193 Raises Invalid_argument if the length of l is greater than Sys.max_ar‐
196 ray_length .
197 Iterators
202 val iter : ('a -> unit) -> 'a array -> unit
203 iter f a applies function f in turn to all the elements of a . It is
206 equivalent to f a.(0); f a.(1); ...; f a.(length a - 1); () .
207 val iteri : (int -> 'a -> unit) -> 'a array -> unit
211 Same as Array.iter , but the function is applied to the index of the
213 element as first argument, and the element itself as second argument.
214 val map : ('a -> 'b) -> 'a array -> 'b array
218 map f a applies function f to all the elements of a , and builds an ar‐
221 ray with the results returned by f : [| f a.(0); f a.(1); ...; f
222 a.(length a - 1) |] .
223 val mapi : (int -> 'a -> 'b) -> 'a array -> 'b array
227 Same as Array.map , but the function is applied to the index of the el‐
229 ement as first argument, and the element itself as second argument.
230 val fold_left : ('a -> 'b -> 'a) -> 'a -> 'b array -> 'a
234 fold_left f init a computes f (... (f (f init a.(0)) a.(1)) ...)
237 a.(n-1) , where n is the length of the array a .
238 val fold_left_map : ('a -> 'b -> 'a * 'c) -> 'a -> 'b array -> 'a * 'c
242 array
243 fold_left_map is a combination of Array.fold_left and Array.map that
246 threads an accumulator through calls to f .
247 Since 4.13.0
250 val fold_right : ('b -> 'a -> 'a) -> 'b array -> 'a -> 'a
254 fold_right f a init computes f a.(0) (f a.(1) ( ... (f a.(n-1) init)
257 ...)) , where n is the length of the array a .
258 Iterators on two arrays
263 val iter2 : ('a -> 'b -> unit) -> 'a array -> 'b array -> unit
264 iter2 f a b applies function f to all the elements of a and b .
267 Since 4.03.0 (4.05.0 in ArrayLabels)
270 Raises Invalid_argument if the arrays are not the same size.
273 val map2 : ('a -> 'b -> 'c) -> 'a array -> 'b array -> 'c array
277 map2 f a b applies function f to all the elements of a and b , and
280 builds an array with the results returned by f : [| f a.(0) b.(0); ...;
281 f a.(length a - 1) b.(length b - 1)|] .
282 Since 4.03.0 (4.05.0 in ArrayLabels)
285 Raises Invalid_argument if the arrays are not the same size.
288 Array scanning
293 val for_all : ('a -> bool) -> 'a array -> bool
294 for_all f [|a1; ...; an|] checks if all elements of the array satisfy
297 the predicate f . That is, it returns (f a1) && (f a2) && ... && (f an)
298 .
299 Since 4.03.0
302 val exists : ('a -> bool) -> 'a array -> bool
306 exists f [|a1; ...; an|] checks if at least one element of the array
309 satisfies the predicate f . That is, it returns (f a1) || (f a2) || ...
310 || (f an) .
311 Since 4.03.0
314 val for_all2 : ('a -> 'b -> bool) -> 'a array -> 'b array -> bool
318 Same as Array.for_all , but for a two-argument predicate.
320 Since 4.11.0
323 Raises Invalid_argument if the two arrays have different lengths.
326 val exists2 : ('a -> 'b -> bool) -> 'a array -> 'b array -> bool
330 Same as Array.exists , but for a two-argument predicate.
332 Since 4.11.0
335 Raises Invalid_argument if the two arrays have different lengths.
338 val mem : 'a -> 'a array -> bool
342 mem a set is true if and only if a is structurally equal to an element
345 of l (i.e. there is an x in l such that compare a x = 0 ).
346 Since 4.03.0
349 val memq : 'a -> 'a array -> bool
353 Same as Array.mem , but uses physical equality instead of structural
355 equality to compare list elements.
356 Since 4.03.0
359 val find_opt : ('a -> bool) -> 'a array -> 'a option
363 find_opt f a returns the first element of the array a that satisfies
366 the predicate f , or None if there is no value that satisfies f in the
367 array a .
368 Since 4.13.0
371 val find_map : ('a -> 'b option) -> 'a array -> 'b option
375 find_map f a applies f to the elements of a in order, and returns the
378 first result of the form Some v , or None if none exist.
379 Since 4.13.0
382 Arrays of pairs
387 val split : ('a * 'b) array -> 'a array * 'b array
388 split [|(a1,b1); ...; (an,bn)|] is ([|a1; ...; an|], [|b1; ...; bn|]) .
391 Since 4.13.0
394 val combine : 'a array -> 'b array -> ('a * 'b) array
398 combine [|a1; ...; an|] [|b1; ...; bn|] is [|(a1,b1); ...; (an,bn)|] .
401 Raise Invalid_argument if the two arrays have different lengths.
402 Since 4.13.0
405 Sorting
410 val sort : ('a -> 'a -> int) -> 'a array -> unit
411 Sort an array in increasing order according to a comparison function.
413 The comparison function must return 0 if its arguments compare as
414 equal, a positive integer if the first is greater, and a negative inte‐
415 ger if the first is smaller (see below for a complete specification).
416 For example, compare is a suitable comparison function. After calling
417 sort , the array is sorted in place in increasing order. sort is guar‐
418 anteed to run in constant heap space and (at most) logarithmic stack
419 space.
420 The current implementation uses Heap Sort. It runs in constant stack
422 space.
423 Specification of the comparison function: Let a be the array and cmp
425 the comparison function. The following must be true for all x , y , z
426 in a :
427 - cmp x y > 0 if and only if cmp y x < 0
429 - if cmp x y >= 0 and cmp y z >= 0 then cmp x z >= 0
431 When sort returns, a contains the same elements as before, reordered in
433 such a way that for all i and j valid indices of a :
434 - cmp a.(i) a.(j) >= 0 if and only if i >= j
436 val stable_sort : ('a -> 'a -> int) -> 'a array -> unit
441 Same as Array.sort , but the sorting algorithm is stable (i.e. ele‐
443 ments that compare equal are kept in their original order) and not
444 guaranteed to run in constant heap space.
445 The current implementation uses Merge Sort. It uses a temporary array
447 of length n/2 , where n is the length of the array. It is usually
448 faster than the current implementation of Array.sort .
449 val fast_sort : ('a -> 'a -> int) -> 'a array -> unit
453 Same as Array.sort or Array.stable_sort , whichever is faster on typi‐
455 cal input.
456 Arrays and Sequences
461 val to_seq : 'a array -> 'a Seq.t
462 Iterate on the array, in increasing order. Modifications of the array
464 during iteration will be reflected in the sequence.
465 Since 4.07
468 val to_seqi : 'a array -> (int * 'a) Seq.t
472 Iterate on the array, in increasing order, yielding indices along ele‐
474 ments. Modifications of the array during iteration will be reflected
475 in the sequence.
476 Since 4.07
479 val of_seq : 'a Seq.t -> 'a array
483 Create an array from the generator
485 Since 4.07
488 Arrays and concurrency safety
493 Care must be taken when concurrently accessing arrays from multiple do‐
494 mains: accessing an array will never crash a program, but unsynchro‐
495 nized accesses might yield surprising (non-sequentially-consistent) re‐
496 sults.
497 Atomicity
500 Every array operation that accesses more than one array element is not
501 atomic. This includes iteration, scanning, sorting, splitting and com‐
502 bining arrays.
503 For example, consider the following program:
505 let size = 100_000_000
506 let a = Array.make size 1
507 let d1 = Domain.spawn (fun () ->
508 Array.iteri (fun i x -> a.(i) <- x + 1) a
509 )
510 let d2 = Domain.spawn (fun () ->
511 Array.iteri (fun i x -> a.(i) <- 2 * x + 1) a
512 )
513 let () = Domain.join d1; Domain.join d2
514 After executing this code, each field of the array a is either 2 , 3 ,
517 4 or 5 . If atomicity is required, then the user must implement their
518 own synchronization (for example, using Mutex.t ).
519 Data races
522 If two domains only access disjoint parts of the array, then the ob‐
523 served behaviour is the equivalent to some sequential interleaving of
524 the operations from the two domains.
525 A data race is said to occur when two domains access the same array el‐
527 ement without synchronization and at least one of the accesses is a
528 write. In the absence of data races, the observed behaviour is equiva‐
529 lent to some sequential interleaving of the operations from different
530 domains.
531 Whenever possible, data races should be avoided by using synchroniza‐
533 tion to mediate the accesses to the array elements.
534 Indeed, in the presence of data races, programs will not crash but the
536 observed behaviour may not be equivalent to any sequential interleaving
537 of operations from different domains. Nevertheless, even in the pres‐
538 ence of data races, a read operation will return the value of some
539 prior write to that location (with a few exceptions for float arrays).
540 Float arrays
543 Float arrays have two supplementary caveats in the presence of data
544 races.
545 First, the blit operation might copy an array byte-by-byte. Data races
547 between such a blit operation and another operation might produce sur‐
548 prising values due to tearing: partial writes interleaved with other
549 operations can create float values that would not exist with a sequen‐
550 tial execution.
551 For instance, at the end of
553 let zeros = Array.make size 0.
554 let max_floats = Array.make size Float.max_float
555 let res = Array.copy zeros
556 let d1 = Domain.spawn (fun () -> Array.blit zeros 0 res 0 size)
557 let d2 = Domain.spawn (fun () -> Array.blit max_floats 0 res 0 size)
558 let () = Domain.join d1; Domain.join d2
559 the res array might contain values that are neither 0. nor max_float .
561 Second, on 32-bit architectures, getting or setting a field involves
563 two separate memory accesses. In the presence of data races, the user
564 may observe tearing on any operation.
565OCamldoc 2023-07-20 Array(3)