Module Dynarray
: sigend
Dynamic arrays.
The Array module provide arrays of fixed length. Dynarray provides arrays whose length can change over
time, by adding or removing elements at the end of the array.
This is typically used to accumulate elements whose number is not known in advance or changes during
computation, while also providing fast access to elements at arbitrary indices.
letdynarray_of_listli=letarr=Dynarray.create()inList.iter(funv->Dynarray.add_lastarrv)li;arr
The Buffer module provides similar features, but it is specialized for accumulating characters into a
dynamically-resized string.
The Stack module provides a last-in first-out data structure that can be easily implemented on top of
dynamic arrays.
Since 5.2
Alertunsynchronized_access. Unsynchronized accesses to dynamic arrays are a programming error.
Unsynchronized accesses
Concurrent accesses to dynamic arrays must be synchronized (for instance with a Mutex.t ). Unsynchronized
accesses to a dynamic array are a programming error that may lead to an invalid dynamic array state, on
which some operations would fail with an Invalid_argument exception.
Dynamicarraystype!'at
A dynamic array containing values of type 'a .
A dynamic array a provides constant-time get and set operations on indices between 0 and Dynarray.lengtha-1 included. Its Dynarray.length may change over time by adding or removing elements to the end of the
array.
We say that an index into a dynarray a is valid if it is in 0..lengtha-1 and invalid otherwise.
valcreate : unit->'atcreate() is a new, empty array.
valmake : int->'a->'atmakenx is a new array of length n , filled with x .
RaisesInvalid_argument if n<0 or n>Sys.max_array_length .
valinit : int->(int->'a)->'atinitnf is a new array a of length n , such that getai is fi . In other words, the elements of a are
f0 , then f1 , then f2 ... and f(n-1) last, evaluated in that order.
This is similar to Array.init .
RaisesInvalid_argument if n<0 or n>Sys.max_array_length .
valget : 'at->int->'agetai is the i -th element of a , starting with index 0 .
RaisesInvalid_argument if the index is invalid
valset : 'at->int->'a->unitsetaix sets the i -th element of a to be x .
i must be a valid index. set does not add new elements to the array -- see Dynarray.add_last to add an
element.
RaisesInvalid_argument if the index is invalid.
vallength : 'at->intlengtha is the number of elements in the array.
valis_empty : 'at->boolis_emptya is true if a is empty, that is, if lengtha=0 .
valget_last : 'at->'aget_lasta is the element of a at index lengtha-1 .
RaisesInvalid_argument if a is empty.
valfind_last : 'at->'aoptionfind_lasta is None if a is empty and Some(get_lasta) otherwise.
valcopy : 'at->'atcopya is a shallow copy of a , a new array containing the same elements as a .
Addingelements
Note: all operations adding elements raise Invalid_argument if the length needs to grow beyond
Sys.max_array_length .
valadd_last : 'at->'a->unitadd_lastax adds the element x at the end of the array a .
valappend_array : 'at->'aarray->unitappend_arrayab adds all elements of b at the end of a , in the order they appear in b .
For example:
leta=Dynarray.of_list[1;2]inDynarray.append_arraya[|3;4|];assert(Dynarray.to_lista=[1;2;3;4])valappend_list : 'at->'alist->unit
Like Dynarray.append_array but with a list.
valappend : 'at->'at->unitappendab is like append_arrayab , but b is itself a dynamic array instead of a fixed-size array.
Warning: appendaa is a programming error because it iterates on a and adds elements to it at the same
time -- see the Dynarray.iteration section below. It fails with Invalid_argument . If you really want to
append a copy of a to itself, you can use Dynarray.append_arraya(Dynarray.to_arraya) which copies a
into a temporary array.
valappend_seq : 'at->'aSeq.t->unit
Like Dynarray.append_array but with a sequence.
Warning: append_seqa(to_seq_reentranta) simultaneously traverses a and adds element to it; the
ordering of those operations is unspecified, and may result in an infinite loop -- the new elements may
in turn be produced by to_seq_reentranta and get added again and again.
valappend_iter : 'at->(('a->unit)->'x->unit)->'x->unitappend_iteraiterx adds each element of x to the end of a . This is iter(add_lasta)x .
For example, append_iteraList.iter[1;2;3] would add elements 1 , 2 , and then 3 at the end of a .
append_iteraQueue.iterq adds elements from the queue q .
valblit : src:'at->src_pos:int->dst:'at->dst_pos:int->len:int->unitblit~src~src_pos~dst~dst_pos~len copies len elements from a source dynarray src , starting at index
src_pos , to a destination dynarray dst , starting at index dst_pos . It works correctly even if src and
dst are the same array, and the source and destination chunks overlap.
Unlike Array.blit , Dynarray.blit can extend the destination array with new elements: it is valid to call
blit even when dst_pos+len is larger than lengthdst . The only requirement is that dst_pos must be at
most lengthdst (included), so that there is no gap between the current elements and the blit region.
RaisesInvalid_argument if src_pos and len do not designate a valid subarray of src , or if dst_pos is
strictly below 0 or strictly above lengthdst .
Removingelementsvalpop_last_opt : 'at->'aoptionpop_last_opta removes and returns the last element of a , or None if the array is empty.
valpop_last : 'at->'apop_lasta removes and returns the last element of a .
RaisesNot_found on an empty array.
valremove_last : 'at->unitremove_lasta removes the last element of a , if any. It does nothing if a is empty.
valtruncate : 'at->int->unittruncatean truncates a to have at most n elements.
It removes elements whose index is greater or equal to n . It does nothing if n>=lengtha .
truncatean is equivalent to:
ifn<0theninvalid_argument"...";whilelengtha>ndoremove_lastadoneRaisesInvalid_argument if n<0 .
valclear : 'at->unitcleara is truncatea0 , it removes all the elements of a .
Iteration
The iteration functions traverse the elements of a dynamic array. Traversals of a are computed in
increasing index order: from the element of index 0 to the element of index lengtha-1 .
It is a programming error to change the length of an array (by adding or removing elements) during an
iteration on the array. Any iteration function will fail with Invalid_argument if it detects such a
length change.
valiter : ('a->unit)->'at->unititerfa calls f on each element of a .
valiteri : (int->'a->unit)->'at->unititerifa calls fix for each x at index i in a .
valmap : ('a->'b)->'at->'btmapfa is a new array of elements of the form fx for each element x of a .
For example, if the elements of a are x0 , x1 , x2 , then the elements of b are fx0 , fx1 , fx2 .
valmapi : (int->'a->'b)->'at->'btmapifa is a new array of elements of the form fix for each element x of a at index i .
For example, if the elements of a are x0 , x1 , x2 , then the elements of b are f0x0 , f1x1 , f2x2
.
valfold_left : ('acc->'a->'acc)->'acc->'at->'accfold_leftfacca folds f over a in order, starting with accumulator acc .
For example, if the elements of a are x0 , x1 , then foldfacca is
letacc=faccx0inletacc=faccx1inaccvalfold_right : ('a->'acc->'acc)->'at->'acc->'accfold_rightfaacc computes fx0(fx1(...(fxnacc)...)) where x0 , x1 , ..., xn are the elements of
a .
valfilter : ('a->bool)->'at->'atfilterfa is a new array of all the elements of a that satisfy f . In other words, it is an array b
such that, for each element x in a in order, x is added to b if fx is true .
For example, filter(funx->x>=0)a is a new array of all non-negative elements of a , in order.
valfilter_map : ('a->'boption)->'at->'btfilter_mapfa is a new array of elements y such that fx is Somey for an element x of a . In others
words, it is an array b such that, for each element x of a in order:
-if fx=Somey , then y is added to b ,
-if fx=None , then no element is added to b .
For example, filter_mapint_of_string_optinputs returns a new array of integers read from the strings in
inputs , ignoring strings that cannot be converted to integers.
Dynarrayscanningvalexists : ('a->bool)->'at->boolexistsfa is true if some element of a satisfies f .
For example, if the elements of a are x0 , x1 , x2 , then existsfa is fx0||fx1||fx2 .
valfor_all : ('a->bool)->'at->boolfor_allfa is true if all elements of a satisfy f . This includes the case where a is empty.
For example, if the elements of a are x0 , x1 , then existsfa is fx0&&fx1&&fx2 .
valmem : 'a->'at->boolmemaset is true if and only if a is structurally equal to an element of set (i.e. there is an x in set
such that compareax=0 ).
Since 5.3
valmemq : 'a->'at->bool
Same as Dynarray.mem , but uses physical equality instead of structural equality to compare array
elements.
Since 5.3
valfind_opt : ('a->bool)->'at->'aoptionfind_optfa returns the first element of the array a that satisfies the predicate f , or None if there
is no value that satisfies f in the array a .
Since 5.3
valfind_index : ('a->bool)->'at->intoptionfind_indexfa returns Somei , where i is the index of the first element of the array a that satisfies fx , if there is such an element.
It returns None if there is no such element.
Since 5.3
valfind_map : ('a->'boption)->'at->'boptionfind_mapfa applies f to the elements of a in order, and returns the first result of the form Somev ,
or None if none exist.
Since 5.3
valfind_mapi : (int->'a->'boption)->'at->'boption
Same as find_map , but the predicate is applied to the index of the element as first argument (counting
from 0), and the element itself as second argument.
Since 5.3
Comparisonfunctions
Comparison functions iterate over their arguments; it is a programming error to change their length
during the iteration, see the Dynarray.iteration section above.
valequal : ('a->'a->bool)->'at->'at->boolequaleqab holds when a and b have the same length, and for all indices i we have eq(getai)(getbi) .
Since 5.3
valcompare : ('a->'a->int)->'at->'at->int
Provided the function cmp defines a preorder on elements, comparecmpab compares first a and b by their
length, and then, if equal, by their elements according to the lexicographic preorder.
For more details on comparison functions, see Array.sort .
Since 5.3
Conversionstootherdatastructures
Note: the of_* functions raise Invalid_argument if the length needs to grow beyond Sys.max_array_length .
The to_* functions, except those specifically marked "reentrant", iterate on their dynarray argument. In
particular it is a programming error if the length of the dynarray changes during their execution, and
the conversion functions raise Invalid_argument if they observe such a change.
valof_array : 'aarray->'atof_arrayarr returns a dynamic array corresponding to the fixed-sized array a . Operates in O(n) time by
making a copy.
valto_array : 'at->'aarrayto_arraya returns a fixed-sized array corresponding to the dynamic array a . This always allocate a new
array and copies elements into it.
valof_list : 'alist->'atof_listl is the array containing the elements of l in the same order.
valto_list : 'at->'alistto_lista is a list with the elements contained in the array a .
valof_seq : 'aSeq.t->'atof_seqseq is an array containing the same elements as seq .
It traverses seq once and will terminate only if seq is finite.
valto_seq : 'at->'aSeq.tto_seqa is the sequence of elements geta0 , geta1 ... geta(lengtha-1) .
valto_seq_reentrant : 'at->'aSeq.tto_seq_reentranta is a reentrant variant of Dynarray.to_seq , in the sense that one may still access its
elements after the length of a has changed.
Demanding the i -th element of the resulting sequence (which can happen zero, one or several times) will
access the i -th element of a at the time of the demand. The sequence stops if a has less than i elements
at this point.
valto_seq_rev : 'at->'aSeq.tto_seq_reva is the sequence of elements geta(l-1) , geta(l-2) ... geta0 , where l is lengtha
at the time to_seq_rev is invoked.
valto_seq_rev_reentrant : 'at->'aSeq.tto_seq_rev_reentranta is a reentrant variant of Dynarray.to_seq_rev , in the sense that one may still
access its elements after the length of a has changed.
Elements that have been removed from the array by the time they are demanded in the sequence are skipped.
AdvancedtopicsforperformanceBackingarray,capacity
Internally, a dynamic array uses a backing array (a fixed-size array as provided by the Array module)
whose length is greater or equal to the length of the dynamic array. We define the capacity of a
dynamic array as the length of its backing array.
The capacity of a dynamic array is relevant in advanced scenarios, when reasoning about the performance
of dynamic array programs:
-The memory usage of a dynamic array is proportional to its capacity, rather than its length.
-When there is no empty space left at the end of the backing array, adding elements requires allocating a
new, larger backing array.
The implementation uses a standard exponential reallocation strategy which guarantees amortized
constant-time operation; in particular, the total capacity of all backing arrays allocated over the
lifetime of a dynamic array is at worst proportional to the total number of elements added.
In other words, users need not care about capacity and reallocations, and they will get reasonable
behavior by default. However, in some performance-sensitive scenarios the functions below can help
control memory usage or guarantee an optimal number of reallocations.
valcapacity : 'at->intcapacitya is the length of a 's backing array.
valensure_capacity : 'at->int->unitensure_capacityan makes sure that the capacity of a is at least n .
RaisesInvalid_argument if the requested capacity is outside the range 0..Sys.max_array_length .
An example would be to reimplement Dynarray.of_array without using Dynarray.init :
letof_arrayarr=leta=Dynarray.create()inDynarray.ensure_capacitya(Array.lengtharr);Array.iter(funv->add_lastav)arr
Using ensure_capacity guarantees that at most one reallocation will take place, instead of possibly
several.
Without this ensure_capacity hint, the number of resizes would be logarithmic in the length of arr ,
creating a constant-factor slowdown noticeable when arr is large.
valensure_extra_capacity : 'at->int->unitensure_extra_capacityan is ensure_capacitya(lengtha+n) , it makes sure that a has room for n extra
items.
RaisesInvalid_argument if the total requested capacity is outside the range 0..Sys.max_array_length .
A use case would be to implement Dynarray.append_array :
letappend_arrayaarr=ensure_extra_capacitya(Array.lengtharr);Array.iter(funv->add_lastav)arrvalfit_capacity : 'at->unitfit_capacitya reallocates a backing array if necessary, so that the resulting capacity is exactly lengtha , with no additional empty space at the end. This can be useful to make sure there is no memory wasted
on a long-lived array.
Note that calling fit_capacity breaks the amortized complexity guarantees provided by the default
reallocation strategy. Calling it repeatedly on an array may have quadratic complexity, both in time and
in total number of words allocated.
If you know that a dynamic array has reached its final length, which will remain fixed in the future, it
is sufficient to call to_array and only keep the resulting fixed-size array. fit_capacity is useful when
you need to keep a dynamic array for eventual future resizes.
valset_capacity : 'at->int->unitset_capacityan reallocates a backing array if necessary, so that the resulting capacity is exactly n .
In particular, all elements of index n or greater are removed.
Like Dynarray.fit_capacity , this function breaks the amortized complexity guarantees provided by the
reallocation strategy. Calling it repeatedly on an array may have quadratic complexity, both in time and
in total number of words allocated.
This is an advanced function; in particular, Dynarray.ensure_capacity should be preferred to increase the
capacity, as it preserves those amortized guarantees.
RaisesInvalid_argument if n<0 .
valreset : 'at->unitreseta clears a and replaces its backing array by an empty array.
It is equivalent to set_capacitya0 or cleara;fit_capacitya .
Noleaks:preservationofmemoryliveness
The user-provided values reachable from a dynamic array a are exactly the elements in the indices 0 to
lengtha-1 . In particular, no user-provided values are "leaked" by being present in the backing array
at index lengtha or later.
CodeexamplesMin-heapsformutablepriorityqueues
We can use dynamic arrays to implement a mutable priority queue. A priority queue provides a function to
add elements, and a function to extract the minimum element -- according to some comparison function.
(*Wepresentourpriorityqueuesasafunctorparametrizedonthecomparisonfunction.*)moduleHeap(Elem:Map.OrderedType):sigtypetvalcreate:unit->tvaladd:t->Elem.t->unitvalpop_min:t->Elem.toptionend=struct(*Ourpriorityqueuesareimplementedusingthestandard"minheap"datastructure,adynamicarrayrepresentingabinarytree.*)typet=Elem.tDynarray.tletcreate=Dynarray.create(*Thenodeofindex[i]hasaschildrenthenodesofindex[2*i+1]and[2*i+2]--iftheyarevalidindicesinthedynarray.*)letleft_childi=2*i+1letright_childi=2*i+2letparent_nodei=(i-1)/2(*Weuseindexingoperatorsforconvenientnotations.*)let(.!())=Dynarray.getlet(.!()<-)=Dynarray.set(*Auxiliaryfunctionstocompareandswaptwoelementsinthedynamicarray.*)letorderhij=Elem.compareh.!(i)h.!(j)letswaphij=letv=h.!(i)inh.!(i)<-h.!(j);h.!(j)<-v(*Wesaythataheaprespectsthe"heapordering"ifthevalueofeachnodeissmallerthanthevalueofitschildren.Thealgorithmmanipulatesarraysthatrespecttheheapalgorithm,exceptforonenodewhosevaluemaybetoosmallortoolarge.Theauxiliaryfunctions[heap_up]and[heap_down]takesuchamisplacedvalue,andmoveit"up"(respectively:"down")thetreebypermutingitwithitsparentvalue(respectively:achildvalue)untiltheheaporderingisrestored.*)letrecheap_uphi=ifi=0then()elseletparent=parent_nodeiiniforderhiparent<0then(swaphiparent;heap_uphparent)andheap_downh~leni=letleft,right=left_childi,right_childiinifleft>=lenthen()(*nochild,stop*)elseletsmallest=ifright>=lenthenleft(*norightchild*)elseiforderhleftright<0thenleftelserightiniforderhismallest>0then(swaphismallest;heap_downh~lensmallest)letaddhs=leti=Dynarray.lengthhinDynarray.add_lasths;heap_uphiletpop_minh=ifDynarray.is_emptyhthenNoneelsebegin(*Standardtrick:swapthe'best'valueatindex0withthelastvalueofthearray.*)letlast=Dynarray.lengthh-1inswaph0last;(*Atthispoint[pop_last]returnsthe'best'value,andleavesaheapwithonemisplacedelementatindex[0].*)letbest=Dynarray.pop_lasthin(*Restoretheheapordering--doesnothingiftheheapisempty.*)heap_downh~len:last0;Somebestendend
The production code from which this example was inspired includes logic to free the backing array when
the heap becomes empty, only in the case where the capacity is above a certain threshold. This can be
done by calling the following function from pop :
letshrinkh=ifDynarray.lengthh=0&&Dynarray.capacityh>1lsl18thenDynarray.reseth
The Heap functor can be used to implement a sorting function, by adding all elements into a priority
queue and then extracting them in order.
letheap_sort(typea)cmpli=letmoduleHeap=Heap(structtypet=aletcompare=cmpend)inletheap=Heap.create()inList.iter(Heap.addheap)li;List.map(fun_->Heap.pop_minheap|>Option.get)li
OCamldoc 2025-06-12 Dynarray(3o)
Install Now
PNG Icons
