1Stdlib.Array(3) OCaml library Stdlib.Array(3)
2
6 Stdlib.Array - no description
7
9 Module Stdlib.Array
10
12 Module Array
13 : (module Stdlib__Array)
14 type 'a t = 'a array
22 An alias for the type of arrays.
25 val length : 'a array -> int
29 Return the length (number of elements) of the given array.
31 val get : 'a array -> int -> 'a
35 get a n returns the element number n of array a . The first element
38 has number 0. The last element has number length a - 1 . You can also
39 write a.(n) instead of get a n .
40 Raises Invalid_argument if n is outside the range 0 to (length a - 1) .
43 val set : 'a array -> int -> 'a -> unit
47 set a n x modifies array a in place, replacing element number n with x
50 . You can also write a.(n) <- x instead of set a n x .
51 Raises Invalid_argument if n is outside the range 0 to length a - 1 .
54 val make : int -> 'a -> 'a array
58 make n x returns a fresh array of length n , initialized with x . All
61 the elements of this new array are initially physically equal to x (in
62 the sense of the == predicate). Consequently, if x is mutable, it is
63 shared among all elements of the array, and modifying x through one of
64 the array entries will modify all other entries at the same time.
65 Raises Invalid_argument if n < 0 or n > Sys.max_array_length . If the
68 value of x is a floating-point number, then the maximum size is only
69 Sys.max_array_length / 2 .
70 val create_float : int -> float array
74 create_float n returns a fresh float array of length n , with unini‐
77 tialized data.
78 Since 4.03
81 val init : int -> (int -> 'a) -> 'a array
85 init n f returns a fresh array of length n , with element number i ini‐
88 tialized to the result of f i . In other terms, init n f tabulates the
89 results of f applied to the integers 0 to n-1 .
90 Raises Invalid_argument if n < 0 or n > Sys.max_array_length . If the
93 return type of f is float , then the maximum size is only Sys.max_ar‐
94 ray_length / 2 .
95 val make_matrix : int -> int -> 'a -> 'a array array
99 make_matrix dimx dimy e returns a two-dimensional array (an array of
102 arrays) with first dimension dimx and second dimension dimy . All the
103 elements of this new matrix are initially physically equal to e . The
104 element ( x,y ) of a matrix m is accessed with the notation m.(x).(y) .
105 Raises Invalid_argument if dimx or dimy is negative or greater than
108 Sys.max_array_length . If the value of e is a floating-point number,
109 then the maximum size is only Sys.max_array_length / 2 .
110 val append : 'a array -> 'a array -> 'a array
114 append v1 v2 returns a fresh array containing the concatenation of the
117 arrays v1 and v2 .
118 Raises Invalid_argument if length v1 + length v2 > Sys.max_array_length
121 .
122 val concat : 'a array list -> 'a array
126 Same as Array.append , but concatenates a list of arrays.
128 val sub : 'a array -> int -> int -> 'a array
132 sub a pos len returns a fresh array of length len , containing the ele‐
135 ments number pos to pos + len - 1 of array a .
136 Raises Invalid_argument if pos and len do not designate a valid subar‐
139 ray of a ; that is, if pos < 0 , or len < 0 , or pos + len > length a .
140 val copy : 'a array -> 'a array
144 copy a returns a copy of a , that is, a fresh array containing the same
147 elements as a .
148 val fill : 'a array -> int -> int -> 'a -> unit
152 fill a pos len x modifies the array a in place, storing x in elements
155 number pos to pos + len - 1 .
156 Raises Invalid_argument if pos and len do not designate a valid subar‐
159 ray of a .
160 val blit : 'a array -> int -> 'a array -> int -> int -> unit
164 blit src src_pos dst dst_pos len copies len elements from array src ,
167 starting at element number src_pos , to array dst , starting at element
168 number dst_pos . It works correctly even if src and dst are the same
169 array, and the source and destination chunks overlap.
170 Raises Invalid_argument if src_pos and len do not designate a valid
173 subarray of src , or if dst_pos and len do not designate a valid subar‐
174 ray of dst .
175 val to_list : 'a array -> 'a list
179 to_list a returns the list of all the elements of a .
182 val of_list : 'a list -> 'a array
186 of_list l returns a fresh array containing the elements of l .
189 Raises Invalid_argument if the length of l is greater than Sys.max_ar‐
192 ray_length .
193 Iterators
198 val iter : ('a -> unit) -> 'a array -> unit
199 iter f a applies function f in turn to all the elements of a . It is
202 equivalent to f a.(0); f a.(1); ...; f a.(length a - 1); () .
203 val iteri : (int -> 'a -> unit) -> 'a array -> unit
207 Same as Array.iter , but the function is applied to the index of the
209 element as first argument, and the element itself as second argument.
210 val map : ('a -> 'b) -> 'a array -> 'b array
214 map f a applies function f to all the elements of a , and builds an ar‐
217 ray with the results returned by f : [| f a.(0); f a.(1); ...; f
218 a.(length a - 1) |] .
219 val mapi : (int -> 'a -> 'b) -> 'a array -> 'b array
223 Same as Array.map , but the function is applied to the index of the el‐
225 ement as first argument, and the element itself as second argument.
226 val fold_left : ('a -> 'b -> 'a) -> 'a -> 'b array -> 'a
230 fold_left f init a computes f (... (f (f init a.(0)) a.(1)) ...)
233 a.(n-1) , where n is the length of the array a .
234 val fold_left_map : ('a -> 'b -> 'a * 'c) -> 'a -> 'b array -> 'a * 'c
238 array
239 fold_left_map is a combination of Array.fold_left and Array.map that
242 threads an accumulator through calls to f .
243 Since 4.13.0
246 val fold_right : ('b -> 'a -> 'a) -> 'b array -> 'a -> 'a
250 fold_right f a init computes f a.(0) (f a.(1) ( ... (f a.(n-1) init)
253 ...)) , where n is the length of the array a .
254 Iterators on two arrays
259 val iter2 : ('a -> 'b -> unit) -> 'a array -> 'b array -> unit
260 iter2 f a b applies function f to all the elements of a and b .
263 Since 4.03.0 (4.05.0 in ArrayLabels)
266 Raises Invalid_argument if the arrays are not the same size.
269 val map2 : ('a -> 'b -> 'c) -> 'a array -> 'b array -> 'c array
273 map2 f a b applies function f to all the elements of a and b , and
276 builds an array with the results returned by f : [| f a.(0) b.(0); ...;
277 f a.(length a - 1) b.(length b - 1)|] .
278 Since 4.03.0 (4.05.0 in ArrayLabels)
281 Raises Invalid_argument if the arrays are not the same size.
284 Array scanning
289 val for_all : ('a -> bool) -> 'a array -> bool
290 for_all f [|a1; ...; an|] checks if all elements of the array satisfy
293 the predicate f . That is, it returns (f a1) && (f a2) && ... && (f an)
294 .
295 Since 4.03.0
298 val exists : ('a -> bool) -> 'a array -> bool
302 exists f [|a1; ...; an|] checks if at least one element of the array
305 satisfies the predicate f . That is, it returns (f a1) || (f a2) || ...
306 || (f an) .
307 Since 4.03.0
310 val for_all2 : ('a -> 'b -> bool) -> 'a array -> 'b array -> bool
314 Same as Array.for_all , but for a two-argument predicate.
316 Since 4.11.0
319 Raises Invalid_argument if the two arrays have different lengths.
322 val exists2 : ('a -> 'b -> bool) -> 'a array -> 'b array -> bool
326 Same as Array.exists , but for a two-argument predicate.
328 Since 4.11.0
331 Raises Invalid_argument if the two arrays have different lengths.
334 val mem : 'a -> 'a array -> bool
338 mem a set is true if and only if a is structurally equal to an element
341 of l (i.e. there is an x in l such that compare a x = 0 ).
342 Since 4.03.0
345 val memq : 'a -> 'a array -> bool
349 Same as Array.mem , but uses physical equality instead of structural
351 equality to compare list elements.
352 Since 4.03.0
355 val find_opt : ('a -> bool) -> 'a array -> 'a option
359 find_opt f a returns the first element of the array a that satisfies
362 the predicate f , or None if there is no value that satisfies f in the
363 array a .
364 Since 4.13.0
367 val find_map : ('a -> 'b option) -> 'a array -> 'b option
371 find_map f a applies f to the elements of a in order, and returns the
374 first result of the form Some v , or None if none exist.
375 Since 4.13.0
378 Arrays of pairs
383 val split : ('a * 'b) array -> 'a array * 'b array
384 split [|(a1,b1); ...; (an,bn)|] is ([|a1; ...; an|], [|b1; ...; bn|]) .
387 Since 4.13.0
390 val combine : 'a array -> 'b array -> ('a * 'b) array
394 combine [|a1; ...; an|] [|b1; ...; bn|] is [|(a1,b1); ...; (an,bn)|] .
397 Raise Invalid_argument if the two arrays have different lengths.
398 Since 4.13.0
401 Sorting
406 val sort : ('a -> 'a -> int) -> 'a array -> unit
407 Sort an array in increasing order according to a comparison function.
409 The comparison function must return 0 if its arguments compare as
410 equal, a positive integer if the first is greater, and a negative inte‐
411 ger if the first is smaller (see below for a complete specification).
412 For example, compare is a suitable comparison function. After calling
413 sort , the array is sorted in place in increasing order. sort is guar‐
414 anteed to run in constant heap space and (at most) logarithmic stack
415 space.
416 The current implementation uses Heap Sort. It runs in constant stack
418 space.
419 Specification of the comparison function: Let a be the array and cmp
421 the comparison function. The following must be true for all x , y , z
422 in a :
423 - cmp x y > 0 if and only if cmp y x < 0
425 - if cmp x y >= 0 and cmp y z >= 0 then cmp x z >= 0
427 When sort returns, a contains the same elements as before, reordered in
429 such a way that for all i and j valid indices of a :
430 - cmp a.(i) a.(j) >= 0 if and only if i >= j
432 val stable_sort : ('a -> 'a -> int) -> 'a array -> unit
437 Same as Array.sort , but the sorting algorithm is stable (i.e. ele‐
439 ments that compare equal are kept in their original order) and not
440 guaranteed to run in constant heap space.
441 The current implementation uses Merge Sort. It uses a temporary array
443 of length n/2 , where n is the length of the array. It is usually
444 faster than the current implementation of Array.sort .
445 val fast_sort : ('a -> 'a -> int) -> 'a array -> unit
449 Same as Array.sort or Array.stable_sort , whichever is faster on typi‐
451 cal input.
452 Arrays and Sequences
457 val to_seq : 'a array -> 'a Seq.t
458 Iterate on the array, in increasing order. Modifications of the array
460 during iteration will be reflected in the sequence.
461 Since 4.07
464 val to_seqi : 'a array -> (int * 'a) Seq.t
468 Iterate on the array, in increasing order, yielding indices along ele‐
470 ments. Modifications of the array during iteration will be reflected
471 in the sequence.
472 Since 4.07
475 val of_seq : 'a Seq.t -> 'a array
479 Create an array from the generator
481 Since 4.07
484 Arrays and concurrency safety
489 Care must be taken when concurrently accessing arrays from multiple do‐
490 mains: accessing an array will never crash a program, but unsynchro‐
491 nized accesses might yield surprising (non-sequentially-consistent) re‐
492 sults.
493 Atomicity
496 Every array operation that accesses more than one array element is not
497 atomic. This includes iteration, scanning, sorting, splitting and com‐
498 bining arrays.
499 For example, consider the following program:
501 let size = 100_000_000
502 let a = Array.make size 1
503 let d1 = Domain.spawn (fun () ->
504 Array.iteri (fun i x -> a.(i) <- x + 1) a
505 )
506 let d2 = Domain.spawn (fun () ->
507 Array.iteri (fun i x -> a.(i) <- 2 * x + 1) a
508 )
509 let () = Domain.join d1; Domain.join d2
510 After executing this code, each field of the array a is either 2 , 3 ,
513 4 or 5 . If atomicity is required, then the user must implement their
514 own synchronization (for example, using Mutex.t ).
515 Data races
518 If two domains only access disjoint parts of the array, then the ob‐
519 served behaviour is the equivalent to some sequential interleaving of
520 the operations from the two domains.
521 A data race is said to occur when two domains access the same array el‐
523 ement without synchronization and at least one of the accesses is a
524 write. In the absence of data races, the observed behaviour is equiva‐
525 lent to some sequential interleaving of the operations from different
526 domains.
527 Whenever possible, data races should be avoided by using synchroniza‐
529 tion to mediate the accesses to the array elements.
530 Indeed, in the presence of data races, programs will not crash but the
532 observed behaviour may not be equivalent to any sequential interleaving
533 of operations from different domains. Nevertheless, even in the pres‐
534 ence of data races, a read operation will return the value of some
535 prior write to that location (with a few exceptions for float arrays).
536 Float arrays
539 Float arrays have two supplementary caveats in the presence of data
540 races.
541 First, the blit operation might copy an array byte-by-byte. Data races
543 between such a blit operation and another operation might produce sur‐
544 prising values due to tearing: partial writes interleaved with other
545 operations can create float values that would not exist with a sequen‐
546 tial execution.
547 For instance, at the end of
549 let zeros = Array.make size 0.
550 let max_floats = Array.make size Float.max_float
551 let res = Array.copy zeros
552 let d1 = Domain.spawn (fun () -> Array.blit zeros 0 res 0 size)
553 let d2 = Domain.spawn (fun () -> Array.blit max_floats 0 res 0 size)
554 let () = Domain.join d1; Domain.join d2
555 the res array might contain values that are neither 0. nor max_float .
557 Second, on 32-bit architectures, getting or setting a field involves
559 two separate memory accesses. In the presence of data races, the user
560 may observe tearing on any operation.
561OCamldoc 2023-07-20 Stdlib.Array(3)