1ArrayLabels(3) OCaml library ArrayLabels(3)
2
6 ArrayLabels - Array operations.
7
9 Module ArrayLabels
10
12 Module ArrayLabels
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 -> f:(int -> 'a) -> 'a array
89 init n ~f returns a fresh array of length n , with element number i
92 initialized to the result of f i . In other terms, init n ~f tabulates
93 the 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 : dimx:int -> dimy: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 ArrayLabels.append , but concatenates a list of arrays.
132 val sub : 'a array -> pos:int -> len:int -> 'a array
136 sub a ~pos ~len returns a fresh array of length len , containing the
139 elements 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 -> pos:int -> len: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 : src:'a array -> src_pos:int -> dst:'a array -> dst_pos:int
168 -> len:int -> unit
169 blit ~src ~src_pos ~dst ~dst_pos ~len copies len elements from array
172 src , starting at element number src_pos , to array dst , starting at
173 element number dst_pos . It works correctly even if src and dst are the
174 same array, and the source and destination chunks overlap.
175 Raises Invalid_argument if src_pos and len do not designate a valid
178 subarray of src , or if dst_pos and len do not designate a valid subar‐
179 ray of dst .
180 val to_list : 'a array -> 'a list
184 to_list a returns the list of all the elements of a .
187 val of_list : 'a list -> 'a array
191 of_list l returns a fresh array containing the elements of l .
194 Raises Invalid_argument if the length of l is greater than Sys.max_ar‐
197 ray_length .
198 Iterators
203 val iter : f:('a -> unit) -> 'a array -> unit
204 iter ~f a applies function f in turn to all the elements of a . It is
207 equivalent to f a.(0); f a.(1); ...; f a.(length a - 1); () .
208 val iteri : f:(int -> 'a -> unit) -> 'a array -> unit
212 Same as ArrayLabels.iter , but the function is applied to the index of
214 the element as first argument, and the element itself as second argu‐
215 ment.
216 val map : f:('a -> 'b) -> 'a array -> 'b array
220 map ~f a applies function f to all the elements of a , and builds an
223 array with the results returned by f : [| f a.(0); f a.(1); ...; f
224 a.(length a - 1) |] .
225 val mapi : f:(int -> 'a -> 'b) -> 'a array -> 'b array
229 Same as ArrayLabels.map , but the function is applied to the index of
231 the element as first argument, and the element itself as second argu‐
232 ment.
233 val fold_left : f:('a -> 'b -> 'a) -> init:'a -> 'b array -> 'a
237 fold_left ~f ~init a computes f (... (f (f init a.(0)) a.(1)) ...)
240 a.(n-1) , where n is the length of the array a .
241 val fold_left_map : f:('a -> 'b -> 'a * 'c) -> init:'a -> 'b array ->
245 'a * 'c array
246 fold_left_map is a combination of ArrayLabels.fold_left and ArrayLa‐
249 bels.map that threads an accumulator through calls to f .
250 Since 4.13.0
253 val fold_right : f:('b -> 'a -> 'a) -> 'b array -> init:'a -> 'a
257 fold_right ~f a ~init computes f a.(0) (f a.(1) ( ... (f a.(n-1) init)
260 ...)) , where n is the length of the array a .
261 Iterators on two arrays
266 val iter2 : f:('a -> 'b -> unit) -> 'a array -> 'b array -> unit
267 iter2 ~f a b applies function f to all the elements of a and b .
270 Since 4.05.0
273 Raises Invalid_argument if the arrays are not the same size.
276 val map2 : f:('a -> 'b -> 'c) -> 'a array -> 'b array -> 'c array
280 map2 ~f a b applies function f to all the elements of a and b , and
283 builds an array with the results returned by f : [| f a.(0) b.(0); ...;
284 f a.(length a - 1) b.(length b - 1)|] .
285 Since 4.05.0
288 Raises Invalid_argument if the arrays are not the same size.
291 Array scanning
296 val for_all : f:('a -> bool) -> 'a array -> bool
297 for_all ~f [|a1; ...; an|] checks if all elements of the array satisfy
300 the predicate f . That is, it returns (f a1) && (f a2) && ... && (f an)
301 .
302 Since 4.03.0
305 val exists : f:('a -> bool) -> 'a array -> bool
309 exists ~f [|a1; ...; an|] checks if at least one element of the array
312 satisfies the predicate f . That is, it returns (f a1) || (f a2) || ...
313 || (f an) .
314 Since 4.03.0
317 val for_all2 : f:('a -> 'b -> bool) -> 'a array -> 'b array -> bool
321 Same as ArrayLabels.for_all , but for a two-argument predicate.
323 Since 4.11.0
326 Raises Invalid_argument if the two arrays have different lengths.
329 val exists2 : f:('a -> 'b -> bool) -> 'a array -> 'b array -> bool
333 Same as ArrayLabels.exists , but for a two-argument predicate.
335 Since 4.11.0
338 Raises Invalid_argument if the two arrays have different lengths.
341 val mem : 'a -> set:'a array -> bool
345 mem a ~set is true if and only if a is structurally equal to an element
348 of l (i.e. there is an x in l such that compare a x = 0 ).
349 Since 4.03.0
352 val memq : 'a -> set:'a array -> bool
356 Same as ArrayLabels.mem , but uses physical equality instead of struc‐
358 tural equality to compare list elements.
359 Since 4.03.0
362 val find_opt : f:('a -> bool) -> 'a array -> 'a option
366 find_opt ~f a returns the first element of the array a that satisfies
369 the predicate f , or None if there is no value that satisfies f in the
370 array a .
371 Since 4.13.0
374 val find_map : f:('a -> 'b option) -> 'a array -> 'b option
378 find_map ~f a applies f to the elements of a in order, and returns the
381 first result of the form Some v , or None if none exist.
382 Since 4.13.0
385 Arrays of pairs
390 val split : ('a * 'b) array -> 'a array * 'b array
391 split [|(a1,b1); ...; (an,bn)|] is ([|a1; ...; an|], [|b1; ...; bn|]) .
394 Since 4.13.0
397 val combine : 'a array -> 'b array -> ('a * 'b) array
401 combine [|a1; ...; an|] [|b1; ...; bn|] is [|(a1,b1); ...; (an,bn)|] .
404 Raise Invalid_argument if the two arrays have different lengths.
405 Since 4.13.0
408 Sorting
413 val sort : cmp:('a -> 'a -> int) -> 'a array -> unit
414 Sort an array in increasing order according to a comparison function.
416 The comparison function must return 0 if its arguments compare as
417 equal, a positive integer if the first is greater, and a negative inte‐
418 ger if the first is smaller (see below for a complete specification).
419 For example, compare is a suitable comparison function. After calling
420 sort , the array is sorted in place in increasing order. sort is guar‐
421 anteed to run in constant heap space and (at most) logarithmic stack
422 space.
423 The current implementation uses Heap Sort. It runs in constant stack
425 space.
426 Specification of the comparison function: Let a be the array and cmp
428 the comparison function. The following must be true for all x , y , z
429 in a :
430 - cmp x y > 0 if and only if cmp y x < 0
432 - if cmp x y >= 0 and cmp y z >= 0 then cmp x z >= 0
434 When sort returns, a contains the same elements as before, reordered in
436 such a way that for all i and j valid indices of a :
437 - cmp a.(i) a.(j) >= 0 if and only if i >= j
439 val stable_sort : cmp:('a -> 'a -> int) -> 'a array -> unit
444 Same as ArrayLabels.sort , but the sorting algorithm is stable (i.e.
446 elements that compare equal are kept in their original order) and not
447 guaranteed to run in constant heap space.
448 The current implementation uses Merge Sort. It uses a temporary array
450 of length n/2 , where n is the length of the array. It is usually
451 faster than the current implementation of ArrayLabels.sort .
452 val fast_sort : cmp:('a -> 'a -> int) -> 'a array -> unit
456 Same as ArrayLabels.sort or ArrayLabels.stable_sort , whichever is
458 faster on typical input.
459 Arrays and Sequences
464 val to_seq : 'a array -> 'a Seq.t
465 Iterate on the array, in increasing order. Modifications of the array
467 during iteration will be reflected in the sequence.
468 Since 4.07
471 val to_seqi : 'a array -> (int * 'a) Seq.t
475 Iterate on the array, in increasing order, yielding indices along ele‐
477 ments. Modifications of the array during iteration will be reflected
478 in the sequence.
479 Since 4.07
482 val of_seq : 'a Seq.t -> 'a array
486 Create an array from the generator
488 Since 4.07
491 Arrays and concurrency safety
496 Care must be taken when concurrently accessing arrays from multiple do‐
497 mains: accessing an array will never crash a program, but unsynchro‐
498 nized accesses might yield surprising (non-sequentially-consistent) re‐
499 sults.
500 Atomicity
503 Every array operation that accesses more than one array element is not
504 atomic. This includes iteration, scanning, sorting, splitting and com‐
505 bining arrays.
506 For example, consider the following program:
508 let size = 100_000_000
509 let a = ArrayLabels.make size 1
510 let d1 = Domain.spawn (fun () ->
511 ArrayLabels.iteri ~f:(fun i x -> a.(i) <- x + 1) a
512 )
513 let d2 = Domain.spawn (fun () ->
514 ArrayLabels.iteri ~f:(fun i x -> a.(i) <- 2 * x + 1) a
515 )
516 let () = Domain.join d1; Domain.join d2
517 After executing this code, each field of the array a is either 2 , 3 ,
520 4 or 5 . If atomicity is required, then the user must implement their
521 own synchronization (for example, using Mutex.t ).
522 Data races
525 If two domains only access disjoint parts of the array, then the ob‐
526 served behaviour is the equivalent to some sequential interleaving of
527 the operations from the two domains.
528 A data race is said to occur when two domains access the same array el‐
530 ement without synchronization and at least one of the accesses is a
531 write. In the absence of data races, the observed behaviour is equiva‐
532 lent to some sequential interleaving of the operations from different
533 domains.
534 Whenever possible, data races should be avoided by using synchroniza‐
536 tion to mediate the accesses to the array elements.
537 Indeed, in the presence of data races, programs will not crash but the
539 observed behaviour may not be equivalent to any sequential interleaving
540 of operations from different domains. Nevertheless, even in the pres‐
541 ence of data races, a read operation will return the value of some
542 prior write to that location (with a few exceptions for float arrays).
543 Float arrays
546 Float arrays have two supplementary caveats in the presence of data
547 races.
548 First, the blit operation might copy an array byte-by-byte. Data races
550 between such a blit operation and another operation might produce sur‐
551 prising values due to tearing: partial writes interleaved with other
552 operations can create float values that would not exist with a sequen‐
553 tial execution.
554 For instance, at the end of
556 let zeros = Array.make size 0.
557 let max_floats = Array.make size Float.max_float
558 let res = Array.copy zeros
559 let d1 = Domain.spawn (fun () -> Array.blit zeros 0 res 0 size)
560 let d2 = Domain.spawn (fun () -> Array.blit max_floats 0 res 0 size)
561 let () = Domain.join d1; Domain.join d2
562 the res array might contain values that are neither 0. nor max_float .
564 Second, on 32-bit architectures, getting or setting a field involves
566 two separate memory accesses. In the presence of data races, the user
567 may observe tearing on any operation.
568OCamldoc 2023-07-20 ArrayLabels(3)