1StdLabels.Array(3) OCaml library StdLabels.Array(3)
2
6 StdLabels.Array - no description
7
9 Module StdLabels.Array
10
12 Module Array
13 : (module ArrayLabels)
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 -> f:(int -> 'a) -> 'a array
85 init n ~f returns a fresh array of length n , with element number i
88 initialized to the result of f i . In other terms, init n ~f tabulates
89 the 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 : dimx:int -> dimy: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 ArrayLabels.append , but concatenates a list of arrays.
128 val sub : 'a array -> pos:int -> len:int -> 'a array
132 sub a ~pos ~len returns a fresh array of length len , containing the
135 elements 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 -> pos:int -> len: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 : src:'a array -> src_pos:int -> dst:'a array -> dst_pos:int
164 -> len:int -> unit
165 blit ~src ~src_pos ~dst ~dst_pos ~len copies len elements from array
168 src , starting at element number src_pos , to array dst , starting at
169 element number dst_pos . It works correctly even if src and dst are the
170 same array, and the source and destination chunks overlap.
171 Raises Invalid_argument if src_pos and len do not designate a valid
174 subarray of src , or if dst_pos and len do not designate a valid subar‐
175 ray of dst .
176 val to_list : 'a array -> 'a list
180 to_list a returns the list of all the elements of a .
183 val of_list : 'a list -> 'a array
187 of_list l returns a fresh array containing the elements of l .
190 Raises Invalid_argument if the length of l is greater than Sys.max_ar‐
193 ray_length .
194 Iterators
199 val iter : f:('a -> unit) -> 'a array -> unit
200 iter ~f a applies function f in turn to all the elements of a . It is
203 equivalent to f a.(0); f a.(1); ...; f a.(length a - 1); () .
204 val iteri : f:(int -> 'a -> unit) -> 'a array -> unit
208 Same as ArrayLabels.iter , but the function is applied to the index of
210 the element as first argument, and the element itself as second argu‐
211 ment.
212 val map : f:('a -> 'b) -> 'a array -> 'b array
216 map ~f a applies function f to all the elements of a , and builds an
219 array with the results returned by f : [| f a.(0); f a.(1); ...; f
220 a.(length a - 1) |] .
221 val mapi : f:(int -> 'a -> 'b) -> 'a array -> 'b array
225 Same as ArrayLabels.map , but the function is applied to the index of
227 the element as first argument, and the element itself as second argu‐
228 ment.
229 val fold_left : f:('a -> 'b -> 'a) -> init:'a -> 'b array -> 'a
233 fold_left ~f ~init a computes f (... (f (f init a.(0)) a.(1)) ...)
236 a.(n-1) , where n is the length of the array a .
237 val fold_left_map : f:('a -> 'b -> 'a * 'c) -> init:'a -> 'b array ->
241 'a * 'c array
242 fold_left_map is a combination of ArrayLabels.fold_left and ArrayLa‐
245 bels.map that threads an accumulator through calls to f .
246 Since 4.13.0
249 val fold_right : f:('b -> 'a -> 'a) -> 'b array -> init:'a -> 'a
253 fold_right ~f a ~init computes f a.(0) (f a.(1) ( ... (f a.(n-1) init)
256 ...)) , where n is the length of the array a .
257 Iterators on two arrays
262 val iter2 : f:('a -> 'b -> unit) -> 'a array -> 'b array -> unit
263 iter2 ~f a b applies function f to all the elements of a and b .
266 Since 4.05.0
269 Raises Invalid_argument if the arrays are not the same size.
272 val map2 : f:('a -> 'b -> 'c) -> 'a array -> 'b array -> 'c array
276 map2 ~f a b applies function f to all the elements of a and b , and
279 builds an array with the results returned by f : [| f a.(0) b.(0); ...;
280 f a.(length a - 1) b.(length b - 1)|] .
281 Since 4.05.0
284 Raises Invalid_argument if the arrays are not the same size.
287 Array scanning
292 val for_all : f:('a -> bool) -> 'a array -> bool
293 for_all ~f [|a1; ...; an|] checks if all elements of the array satisfy
296 the predicate f . That is, it returns (f a1) && (f a2) && ... && (f an)
297 .
298 Since 4.03.0
301 val exists : f:('a -> bool) -> 'a array -> bool
305 exists ~f [|a1; ...; an|] checks if at least one element of the array
308 satisfies the predicate f . That is, it returns (f a1) || (f a2) || ...
309 || (f an) .
310 Since 4.03.0
313 val for_all2 : f:('a -> 'b -> bool) -> 'a array -> 'b array -> bool
317 Same as ArrayLabels.for_all , but for a two-argument predicate.
319 Since 4.11.0
322 Raises Invalid_argument if the two arrays have different lengths.
325 val exists2 : f:('a -> 'b -> bool) -> 'a array -> 'b array -> bool
329 Same as ArrayLabels.exists , but for a two-argument predicate.
331 Since 4.11.0
334 Raises Invalid_argument if the two arrays have different lengths.
337 val mem : 'a -> set:'a array -> bool
341 mem a ~set is true if and only if a is structurally equal to an element
344 of l (i.e. there is an x in l such that compare a x = 0 ).
345 Since 4.03.0
348 val memq : 'a -> set:'a array -> bool
352 Same as ArrayLabels.mem , but uses physical equality instead of struc‐
354 tural equality to compare list elements.
355 Since 4.03.0
358 val find_opt : f:('a -> bool) -> 'a array -> 'a option
362 find_opt ~f a returns the first element of the array a that satisfies
365 the predicate f , or None if there is no value that satisfies f in the
366 array a .
367 Since 4.13.0
370 val find_map : f:('a -> 'b option) -> 'a array -> 'b option
374 find_map ~f a applies f to the elements of a in order, and returns the
377 first result of the form Some v , or None if none exist.
378 Since 4.13.0
381 Arrays of pairs
386 val split : ('a * 'b) array -> 'a array * 'b array
387 split [|(a1,b1); ...; (an,bn)|] is ([|a1; ...; an|], [|b1; ...; bn|]) .
390 Since 4.13.0
393 val combine : 'a array -> 'b array -> ('a * 'b) array
397 combine [|a1; ...; an|] [|b1; ...; bn|] is [|(a1,b1); ...; (an,bn)|] .
400 Raise Invalid_argument if the two arrays have different lengths.
401 Since 4.13.0
404 Sorting
409 val sort : cmp:('a -> 'a -> int) -> 'a array -> unit
410 Sort an array in increasing order according to a comparison function.
412 The comparison function must return 0 if its arguments compare as
413 equal, a positive integer if the first is greater, and a negative inte‐
414 ger if the first is smaller (see below for a complete specification).
415 For example, compare is a suitable comparison function. After calling
416 sort , the array is sorted in place in increasing order. sort is guar‐
417 anteed to run in constant heap space and (at most) logarithmic stack
418 space.
419 The current implementation uses Heap Sort. It runs in constant stack
421 space.
422 Specification of the comparison function: Let a be the array and cmp
424 the comparison function. The following must be true for all x , y , z
425 in a :
426 - cmp x y > 0 if and only if cmp y x < 0
428 - if cmp x y >= 0 and cmp y z >= 0 then cmp x z >= 0
430 When sort returns, a contains the same elements as before, reordered in
432 such a way that for all i and j valid indices of a :
433 - cmp a.(i) a.(j) >= 0 if and only if i >= j
435 val stable_sort : cmp:('a -> 'a -> int) -> 'a array -> unit
440 Same as ArrayLabels.sort , but the sorting algorithm is stable (i.e.
442 elements that compare equal are kept in their original order) and not
443 guaranteed to run in constant heap space.
444 The current implementation uses Merge Sort. It uses a temporary array
446 of length n/2 , where n is the length of the array. It is usually
447 faster than the current implementation of ArrayLabels.sort .
448 val fast_sort : cmp:('a -> 'a -> int) -> 'a array -> unit
452 Same as ArrayLabels.sort or ArrayLabels.stable_sort , whichever is
454 faster on typical input.
455 Arrays and Sequences
460 val to_seq : 'a array -> 'a Seq.t
461 Iterate on the array, in increasing order. Modifications of the array
463 during iteration will be reflected in the sequence.
464 Since 4.07
467 val to_seqi : 'a array -> (int * 'a) Seq.t
471 Iterate on the array, in increasing order, yielding indices along ele‐
473 ments. Modifications of the array during iteration will be reflected
474 in the sequence.
475 Since 4.07
478 val of_seq : 'a Seq.t -> 'a array
482 Create an array from the generator
484 Since 4.07
487 Arrays and concurrency safety
492 Care must be taken when concurrently accessing arrays from multiple do‐
493 mains: accessing an array will never crash a program, but unsynchro‐
494 nized accesses might yield surprising (non-sequentially-consistent) re‐
495 sults.
496 Atomicity
499 Every array operation that accesses more than one array element is not
500 atomic. This includes iteration, scanning, sorting, splitting and com‐
501 bining arrays.
502 For example, consider the following program:
504 let size = 100_000_000
505 let a = ArrayLabels.make size 1
506 let d1 = Domain.spawn (fun () ->
507 ArrayLabels.iteri ~f:(fun i x -> a.(i) <- x + 1) a
508 )
509 let d2 = Domain.spawn (fun () ->
510 ArrayLabels.iteri ~f:(fun i x -> a.(i) <- 2 * x + 1) a
511 )
512 let () = Domain.join d1; Domain.join d2
513 After executing this code, each field of the array a is either 2 , 3 ,
516 4 or 5 . If atomicity is required, then the user must implement their
517 own synchronization (for example, using Mutex.t ).
518 Data races
521 If two domains only access disjoint parts of the array, then the ob‐
522 served behaviour is the equivalent to some sequential interleaving of
523 the operations from the two domains.
524 A data race is said to occur when two domains access the same array el‐
526 ement without synchronization and at least one of the accesses is a
527 write. In the absence of data races, the observed behaviour is equiva‐
528 lent to some sequential interleaving of the operations from different
529 domains.
530 Whenever possible, data races should be avoided by using synchroniza‐
532 tion to mediate the accesses to the array elements.
533 Indeed, in the presence of data races, programs will not crash but the
535 observed behaviour may not be equivalent to any sequential interleaving
536 of operations from different domains. Nevertheless, even in the pres‐
537 ence of data races, a read operation will return the value of some
538 prior write to that location (with a few exceptions for float arrays).
539 Float arrays
542 Float arrays have two supplementary caveats in the presence of data
543 races.
544 First, the blit operation might copy an array byte-by-byte. Data races
546 between such a blit operation and another operation might produce sur‐
547 prising values due to tearing: partial writes interleaved with other
548 operations can create float values that would not exist with a sequen‐
549 tial execution.
550 For instance, at the end of
552 let zeros = Array.make size 0.
553 let max_floats = Array.make size Float.max_float
554 let res = Array.copy zeros
555 let d1 = Domain.spawn (fun () -> Array.blit zeros 0 res 0 size)
556 let d2 = Domain.spawn (fun () -> Array.blit max_floats 0 res 0 size)
557 let () = Domain.join d1; Domain.join d2
558 the res array might contain values that are neither 0. nor max_float .
560 Second, on 32-bit architectures, getting or setting a field involves
562 two separate memory accesses. In the presence of data races, the user
563 may observe tearing on any operation.
564OCamldoc 2023-07-20 StdLabels.Array(3)