1Stdlib.ArrayLabels(3) OCaml library Stdlib.ArrayLabels(3)
2
3
4
6 Stdlib.ArrayLabels - no description
7
9 Module Stdlib.ArrayLabels
10
12 Module ArrayLabels
13 : (module Stdlib__ArrayLabels)
14
15
16
17
18
19
20
21 type 'a t = 'a array
22
23
24 An alias for the type of arrays.
25
26
27
28 val length : 'a array -> int
29
30 Return the length (number of elements) of the given array.
31
32
33
34 val get : 'a array -> int -> 'a
35
36
37 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
41
42 Raises Invalid_argument if n is outside the range 0 to (length a - 1) .
43
44
45
46 val set : 'a array -> int -> 'a -> unit
47
48
49 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
52
53 Raises Invalid_argument if n is outside the range 0 to length a - 1 .
54
55
56
57 val make : int -> 'a -> 'a array
58
59
60 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
66
67 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
71
72
73 val create_float : int -> float array
74
75
76 create_float n returns a fresh float array of length n , with unini‐
77 tialized data.
78
79
80 Since 4.03
81
82
83
84 val init : int -> f:(int -> 'a) -> 'a array
85
86
87 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
91
92 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
96
97
98 val make_matrix : dimx:int -> dimy:int -> 'a -> 'a array array
99
100
101 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
106
107 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
111
112
113 val append : 'a array -> 'a array -> 'a array
114
115
116 append v1 v2 returns a fresh array containing the concatenation of the
117 arrays v1 and v2 .
118
119
120 Raises Invalid_argument if length v1 + length v2 > Sys.max_array_length
121 .
122
123
124
125 val concat : 'a array list -> 'a array
126
127 Same as ArrayLabels.append , but concatenates a list of arrays.
128
129
130
131 val sub : 'a array -> pos:int -> len:int -> 'a array
132
133
134 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
137
138 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
141
142
143 val copy : 'a array -> 'a array
144
145
146 copy a returns a copy of a , that is, a fresh array containing the same
147 elements as a .
148
149
150
151 val fill : 'a array -> pos:int -> len:int -> 'a -> unit
152
153
154 fill a ~pos ~len x modifies the array a in place, storing x in elements
155 number pos to pos + len - 1 .
156
157
158 Raises Invalid_argument if pos and len do not designate a valid subar‐
159 ray of a .
160
161
162
163 val blit : src:'a array -> src_pos:int -> dst:'a array -> dst_pos:int
164 -> len:int -> unit
165
166
167 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
172
173 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
177
178
179 val to_list : 'a array -> 'a list
180
181
182 to_list a returns the list of all the elements of a .
183
184
185
186 val of_list : 'a list -> 'a array
187
188
189 of_list l returns a fresh array containing the elements of l .
190
191
192 Raises Invalid_argument if the length of l is greater than Sys.max_ar‐
193 ray_length .
194
195
196
197
198 Iterators
199 val iter : f:('a -> unit) -> 'a array -> unit
200
201
202 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
205
206
207 val iteri : f:(int -> 'a -> unit) -> 'a array -> unit
208
209 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
213
214
215 val map : f:('a -> 'b) -> 'a array -> 'b array
216
217
218 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
222
223
224 val mapi : f:(int -> 'a -> 'b) -> 'a array -> 'b array
225
226 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
230
231
232 val fold_left : f:('a -> 'b -> 'a) -> init:'a -> 'b array -> 'a
233
234
235 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
238
239
240 val fold_left_map : f:('a -> 'b -> 'a * 'c) -> init:'a -> 'b array ->
241 'a * 'c array
242
243
244 fold_left_map is a combination of ArrayLabels.fold_left and ArrayLa‐
245 bels.map that threads an accumulator through calls to f .
246
247
248 Since 4.13.0
249
250
251
252 val fold_right : f:('b -> 'a -> 'a) -> 'b array -> init:'a -> 'a
253
254
255 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
258
259
260
261 Iterators on two arrays
262 val iter2 : f:('a -> 'b -> unit) -> 'a array -> 'b array -> unit
263
264
265 iter2 ~f a b applies function f to all the elements of a and b .
266
267
268 Since 4.05.0
269
270
271 Raises Invalid_argument if the arrays are not the same size.
272
273
274
275 val map2 : f:('a -> 'b -> 'c) -> 'a array -> 'b array -> 'c array
276
277
278 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
282
283 Since 4.05.0
284
285
286 Raises Invalid_argument if the arrays are not the same size.
287
288
289
290
291 Array scanning
292 val for_all : f:('a -> bool) -> 'a array -> bool
293
294
295 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
299
300 Since 4.03.0
301
302
303
304 val exists : f:('a -> bool) -> 'a array -> bool
305
306
307 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
311
312 Since 4.03.0
313
314
315
316 val for_all2 : f:('a -> 'b -> bool) -> 'a array -> 'b array -> bool
317
318 Same as ArrayLabels.for_all , but for a two-argument predicate.
319
320
321 Since 4.11.0
322
323
324 Raises Invalid_argument if the two arrays have different lengths.
325
326
327
328 val exists2 : f:('a -> 'b -> bool) -> 'a array -> 'b array -> bool
329
330 Same as ArrayLabels.exists , but for a two-argument predicate.
331
332
333 Since 4.11.0
334
335
336 Raises Invalid_argument if the two arrays have different lengths.
337
338
339
340 val mem : 'a -> set:'a array -> bool
341
342
343 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
346
347 Since 4.03.0
348
349
350
351 val memq : 'a -> set:'a array -> bool
352
353 Same as ArrayLabels.mem , but uses physical equality instead of struc‐
354 tural equality to compare list elements.
355
356
357 Since 4.03.0
358
359
360
361 val find_opt : f:('a -> bool) -> 'a array -> 'a option
362
363
364 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
368
369 Since 4.13.0
370
371
372
373 val find_map : f:('a -> 'b option) -> 'a array -> 'b option
374
375
376 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
379
380 Since 4.13.0
381
382
383
384
385 Arrays of pairs
386 val split : ('a * 'b) array -> 'a array * 'b array
387
388
389 split [|(a1,b1); ...; (an,bn)|] is ([|a1; ...; an|], [|b1; ...; bn|]) .
390
391
392 Since 4.13.0
393
394
395
396 val combine : 'a array -> 'b array -> ('a * 'b) array
397
398
399 combine [|a1; ...; an|] [|b1; ...; bn|] is [|(a1,b1); ...; (an,bn)|] .
400 Raise Invalid_argument if the two arrays have different lengths.
401
402
403 Since 4.13.0
404
405
406
407
408 Sorting
409 val sort : cmp:('a -> 'a -> int) -> 'a array -> unit
410
411 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
420 The current implementation uses Heap Sort. It runs in constant stack
421 space.
422
423 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
427 - cmp x y > 0 if and only if cmp y x < 0
428
429 - if cmp x y >= 0 and cmp y z >= 0 then cmp x z >= 0
430
431 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
434 - cmp a.(i) a.(j) >= 0 if and only if i >= j
435
436
437
438
439 val stable_sort : cmp:('a -> 'a -> int) -> 'a array -> unit
440
441 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
445 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
449
450
451 val fast_sort : cmp:('a -> 'a -> int) -> 'a array -> unit
452
453 Same as ArrayLabels.sort or ArrayLabels.stable_sort , whichever is
454 faster on typical input.
455
456
457
458
459 Arrays and Sequences
460 val to_seq : 'a array -> 'a Seq.t
461
462 Iterate on the array, in increasing order. Modifications of the array
463 during iteration will be reflected in the sequence.
464
465
466 Since 4.07
467
468
469
470 val to_seqi : 'a array -> (int * 'a) Seq.t
471
472 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
476
477 Since 4.07
478
479
480
481 val of_seq : 'a Seq.t -> 'a array
482
483 Create an array from the generator
484
485
486 Since 4.07
487
488
489
490
491 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
497
498 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
503 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
514
515 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
519
520 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
525 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
531 Whenever possible, data races should be avoided by using synchroniza‐
532 tion to mediate the accesses to the array elements.
533
534 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
540
541 Float arrays
542 Float arrays have two supplementary caveats in the presence of data
543 races.
544
545 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
551 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
559 the res array might contain values that are neither 0. nor max_float .
560
561 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.
564
565OCamldoc 2023-07-20 Stdlib.ArrayLabels(3)