Library

Module

Module type

Parameter

Class

Class type

sectionYPositions = computeSectionYPositions($el), 10)" x-init="setTimeout(() => sectionYPositions = computeSectionYPositions($el), 10)">

On This Page

Legend:

Library

Module

Module type

Parameter

Class

Class type

Library

Module

Module type

Parameter

Class

Class type

The submodule `Ephemeral`

, also available under the name `E`

, offers an implementation of ephemeral (mutable) sequences. Please follow the link for details.

A sequence `s`

of type `'a t`

is a mutable data structure which represents a mathematical sequence of elements of type `'a`

.

`val create : 'a -> 'a t`

`create default`

constructs and returns a new empty sequence. The default value `default`

is used to fill empty array slots.

Time complexity: *O(K)*.

`val make : 'a -> int -> 'a -> 'a t`

`make default n v`

constructs and returns a fresh sequence whose length is `n`

and which consists of `n`

copies of the value `v`

. It is equivalent to `of_array default (Array.make n v)`

.

Time complexity: *O(n + K)*.

`val init : 'a -> int -> (int -> 'a) -> 'a t`

`init default n f`

constructs and returns a fresh sequence whose length is `n`

and whose elements are the values produced by the calls `f 0`

, `f 1`

, ... `f (n-1)`

, in this order. It is equivalent to `of_array default (Array.init n f)`

.

Time complexity: *O(n + K)*, not counting the cost of the function `f`

.

`val default : 'a t -> 'a`

`default s`

returns the value that is used to fill empty array slots in the sequence `s`

.

Time complexity: *O(1)*.

`val length : 'a t -> int`

`length s`

returns the length of the sequence `s`

.

Time complexity: *O(1)*.

`val is_empty : 'a t -> bool`

`is_empty s`

returns `true`

if the sequence `s`

is empty and `false`

otherwise. It is equivalent to `length s = 0`

.

Time complexity: *O(1)*.

`val clear : 'a t -> unit`

`clear s`

empties the sequence `s`

.

Time complexity: *O(K)*, unless the global parameter `overwrite_empty_slots`

is `false`

, in which case the complexity is *O(1)*.

`copy ~mode s`

constructs and returns a copy `s'`

of the sequence `s`

. The sequences `s`

and `s'`

initially have the same elements, and can thereafter be modified independently of one another. Several copying modes are available, which have the same observable behavior, but offer distinct performance characteristics:

`copy ~mode:`Copy s`

creates a sequence that is physically disjoint from`s`

. All of the elements are copied one by one. It takes linear time, which is slow, but on the upside, it has no latent cost. The sequence`s`

is unaffected, and the sequence`s'`

has unique ownership of its chunks.

`copy ~mode:`Share s`

creates a sequence whose chunks are physically shared with those of`s`

. The copying of individual chunks is delayed until`s`

or`s'`

is actually modified. This operation has complexity*O(K)*, which is fast, but on the downside, there is a latent cost: subsequent update operations on`s`

and`s'`

are more costly.

The default mode is ``Copy`

. That is, `copy s`

is a short-hand for `copy ~mode:`Copy s`

.

Time complexity: *O(n + K)* in ``Share`

mode; *O(K)* in ``Copy`

mode.

If `s1`

and `s2`

are distinct sequences, then `assign s1 s2`

moves `s2`

's elements into `s1`

, overwriting `s1`

's previous content, and clears `s2`

. If `s1`

and `s2`

are the same sequence, then ```
assign s1
s2
```

has no effect.

Time complexity: *O(1)* in the special case where `s2`

is never used afterwards; otherwise *O(K)*.

`push side s x`

pushes the element `x`

onto the front or back end of the sequence `s`

. The parameter `side`

determines which end of the sequence is acted upon.

Time complexity: *O(log n)* in the worst case. That said, in practice, most `push`

operations execute in *O(1)*.

If the sequence `s`

is nonempty, then `pop side s`

pops an element `x`

off the front or back end of the sequence `s`

and returns `x`

. The parameter `side`

determines which end of the sequence is acted upon. If the sequence `s`

is empty, the exception `Empty`

is raised.

Time complexity: same as `push`

.

If the sequence `s`

is nonempty, then `pop_opt side s`

pops an element `x`

off the front or back end of the sequence `s`

and returns `Some x`

. The parameter `side`

determines which end of the sequence is acted upon. If the sequence `s`

is empty, `None`

is returned.

Time complexity: same as `pop`

.

If the sequence `s`

is nonempty, then `peek side s`

reads the element `x`

found at the front or back end of the sequence `s`

and returns `x`

. The parameter `side`

determines which end of the sequence is acted upon. If the sequence `s`

is empty, the exception `Empty`

is raised.

Time complexity: *O(1)*.

If the sequence `s`

is nonempty, then `peek_opt side s`

reads the element `x`

found at the front or back end of the sequence `s`

and returns `Some x`

. The parameter `side`

determines which end of the sequence is acted upon. If the sequence `s`

is empty, `None`

is returned.

Time complexity: *O(1)*.

`val get : 'a t -> int -> 'a`

`get s i`

returns the element `x`

located at index `i`

in the sequence `s`

. The index `i`

must lie in the semi-open interval `[0, length s)`

.

Time complexity: *O(log n)*, or, more precisely, *O(log (min (i, n - i)))*.

`val set : 'a t -> int -> 'a -> unit`

`set s i x`

replaces the element located at index `i`

in the sequence `s`

with the element `x`

. The index `i`

must lie in the semi-open interval `[0, length s)`

. The sequence `s`

is updated in place.

Time complexity: if the `set`

operation hits a chunk that is marked as potentially shared with other sequences, then its complexity is *O(K + log n)*, and this chunk is replaced in the process with one that is not shared with any other sequence. Otherwise, the complexity is *O(log n)*, or, more precisely, *O(log (min (i, n - i)))*.

`concat s1 s2`

creates and returns a new sequence whose content is the concatenation of the sequences `s1`

and `s2`

. The sequences `s1`

and `s2`

are cleared. The sequences `s1`

and `s2`

must be distinct. `concat`

is slightly less efficient than `append`

, whose use should be preferred.

Time complexity: in pathological cases, `concat`

can cost as much as *O(K + log^2 n)*, where *n* is the length of the result of the concatenation. In most cases, however, we expect `concat`

to cost *O(K + log n)*. In the particular case of a concatenation that involves sequences whose chunks have never been shared, a more precise bound is *O(K + log (min(n1, n2)))*, where *n1* and *n2* denote the lengths of the two sequences.

`append back s1 s2`

is equivalent to `assign s1 (concat s1 s2)`

. Thus, `s1`

is assigned the concatenation of the sequences `s1`

and `s2`

, while `s2`

is cleared. In other words, `append back s1 s2`

appends the sequence `s2`

at the back end of the sequence `s1`

.

`append front s1 s2`

is equivalent to `assign s1 (concat s2 s1)`

. Thus, `s1`

is assigned the concatenation of the sequences `s2`

and `s1`

, while `s2`

is cleared. In other words, `append front s1 s2`

prepends the sequence `s2`

at the front end of the sequence `s1`

.

In either case, the sequences `s1`

and `s2`

must be distinct.

Time complexity: same as `concat`

.

`split s i`

splits the sequence `s`

at index `i`

. It returns two new sequences `s1`

and `s2`

such that the length of `s1`

is `i`

and the concatenation of `s1`

and `s2`

is `s`

. The sequence `s`

is cleared. The index `i`

must lie in the closed interval `[0, length s]`

. `split`

is slightly less efficient than `carve`

, whose use should be preferred.

Time complexity: in pathological cases, `split`

can cost as much as *O(K + log^2 n)*, where *n* is the length of the result of the concatenation. In most cases, however, we expect `split`

to cost *O(K + log n)*, or, more precisely, *O(K + log (min (i, n - i)))*. The latter bound holds, in particular, when the operation involves a sequence whose chunks have never been shared.

`carve back s i`

is equivalent to `let s1, s2 = split s i in assign s s1; s2`

. Thus, it splits the sequence `s`

at index `i`

into two parts: the first part is written to `s`

, while the second part is returned.

`carve front s i`

is equivalent to `let s1, s2 = split s i in assign s s2; s1`

. Thus, it splits the sequence `s`

at index `i`

into two parts: the second part is written to `s`

, while the first part is returned.

In either case, the index `i`

must lie in the closed interval `[0, length s]`

.

Time complexity: same as `split`

.

`take side s i`

is equivalent to (and faster than) `ignore (carve side s i)`

. In other words, `take front s i`

truncates the sequence `s`

at index `i`

, and keeps only the front part; `take back s i`

truncates the sequence `s`

at index `i`

, and keeps only the back part. The index `i`

must lie in the closed interval `[0, length s]`

.

Time complexity: same as `split`

.

`drop side s i`

is equivalent to `take (other side) s i`

. The index `i`

must lie in the closed interval `[0, length s]`

.

Time complexity: same as `split`

.

`sub s head size`

extracts the sequence segment defined by the sequence `s`

, the start index `head`

, and the size `size`

. The sequence `s`

is unaffected.

Time complexity: *O(size + K)*.

`iter direction f s`

applies the function `f`

in turn to every element `x`

of the sequence `s`

. The parameter `direction`

determines in what order the elements are presented. The function `f`

is not allowed to modify the sequence `s`

while iteration is ongoing. If the flag `check_iterator_validity`

is enabled (which it is, by default), then an illegal modification is detected at runtime.

Time complexity: *O(n)*, not counting the cost of the function `f`

.

`iteri direction f s`

applies the function `f`

in turn to every index `i`

and matching element `x`

of the sequence `s`

. The parameter `direction`

determines in what order the elements are presented. The function `f`

is not allowed to modify the sequence `s`

while iteration is ongoing. If the flag `check_iterator_validity`

is enabled (which it is, by default), then an illegal modification is detected at runtime.

Time complexity: *O(n)*, not counting the cost of the function `f`

.

`iter_segments direction s f`

applies the function `f`

to a series of nonempty array segments whose concatenation represents the sequence `s`

. The function `f`

is allowed to *read* these array segments. When iterating backward, each segment must be traversed in reverse order. **The function f is not allowed to write these array segments.** The function

`f`

is not allowed to modify the sequence `s`

while iteration is ongoing. If the flag `check_iterator_validity`

is enabled (which it is, by default), then an illegal modification is detected at runtime.Time complexity: *O(n/K)*, not counting the cost of the function `f`

.

`val fold_left : ('a -> 'b -> 'a) -> 'a -> 'b t -> 'a`

`fold_left f a s`

applies the function `f`

in turn to each element of the sequence `s`

, in the forward direction. An accumulator is threaded through the calls to `f`

. The function `f`

is not allowed to modify the sequence `s`

while iteration is ongoing. Subject to this condition, `fold_left f a s`

is equivalent to `List.fold_left f a (to_list s)`

. If the flag `check_iterator_validity`

is enabled (which it is, by default), then an illegal modification is detected at runtime.

Time complexity: *O(n)*, not counting the cost of the function `f`

.

`val fold_right : ('a -> 'b -> 'b) -> 'a t -> 'b -> 'b`

`fold_right f a s`

applies the function `f`

in turn to each element of the sequence `s`

, in the backward direction. An accumulator is threaded through the calls to `f`

. The function `f`

is not allowed to modify the sequence `s`

while iteration is ongoing. Subject to this condition, `fold_right f s a`

is equivalent to `List.fold_right f (to_list s) a`

. If the flag `check_iterator_validity`

is enabled (which it is, by default), then an illegal modification is detected at runtime.

Time complexity: *O(n)*, not counting the cost of the function `f`

.

`module Iter : sig ... end`

The submodule `Iter`

offers an implementation of iterators on ephemeral sequences.

`val to_list : 'a t -> 'a list`

`to_list s`

returns a list whose elements are the elements of the sequence `s`

.

Time complexity: *O(n)*.

`val to_array : 'a t -> 'a array`

`to_array s`

returns a fresh array whose elements are the elements of the sequence `s`

.

Time complexity: *O(n)*.

`to_seq direction s`

returns a fresh sequence whose elements are the elements of the sequence `s`

, enumerated according to `direction`

. The sequence `to_seq direction s`

is ephemeral: it can be consumed only once. This sequence occupies O(log n) space in memory: it is an iterator in disguise.

Time complexity: the creation of a sequence costs *O(1)*; then, demanding each element of the sequence has the same cost as a call to `Iter.get_and_move`

. If *k* elements of the resulting sequence are demanded by the user, then the total cost of producing these elements is *O(k)*.

`val of_list_segment : 'a -> int -> 'a list -> 'a t`

`of_list_segment default n xs`

creates a new sequence out of the `n`

first elements of the list `xs`

. The list `xs`

must have at least `n`

elements.

Time complexity: *O(n + K)*.

`val of_list : 'a -> 'a list -> 'a t`

`of_list default xs`

creates a new sequence out of the list `xs`

. If the length of the list `xs`

is known, then the use of `of_list_segment`

should be preferred.

Time complexity: *O(n + K)*.

`val of_array_segment : 'a -> 'a array -> int -> int -> 'a t`

`of_array_segment default a head size`

creates a new sequence out of the array segment defined by the array `a`

, the start index `head`

, and the size `size`

. The data is copied, so the array `a`

can still be used afterwards.

Time complexity: *O(n + K)*, where *n*, the length of the result, is equal to `size`

.

`val of_array : 'a -> 'a array -> 'a t`

`of_array default a`

creates a new sequence out of the array `a`

. The data is copied, so the array `a`

can still be used afterwards.

Time complexity: *O(n + K)*.

`val of_seq_segment : 'a -> int -> 'a Stdlib.Seq.t -> 'a t`

`of_seq_segment default n xs`

creates a new sequence out of the `n`

first elements of the sequence `xs`

. The sequence `xs`

must have at least `n`

elements. It is consumed once.

Time complexity: *O(n + K)*, not counting the cost of demanding elements from the sequence `xs`

.

`val of_seq : 'a -> 'a Stdlib.Seq.t -> 'a t`

`of_seq d xs`

creates a new sequence out of the sequence `xs`

. The sequence `xs`

must be finite. It is consumed once. If the length of the sequence `xs`

is known, then the use of `of_seq_segment`

should be preferred.

Time complexity: *O(n + K)*, not counting the cost of demanding elements from the sequence `xs`

.

`find direction p s`

finds and returns the first element of the sequence `s`

, along the direction `direction`

, that satisfies the predicate `p`

. If no element of the sequence satisfies `p`

, the exception `Not_found`

is raised.

Time complexity: *O(i)*, where `i`

is the index of the first element that satisfies `p`

, or *n* if no element satisfies `p`

. This does not count the cost of the function `p`

.

`find_opt direction p s`

finds and returns the first element of the sequence `s`

, along the direction `direction`

, that satisfies the predicate `p`

. If no element of the sequence satisfies `p`

, `None`

is returned.

Time complexity: same as `find`

.

`find_map direction f s`

applies `f`

to each element of the sequence `s`

, along the direction `direction`

, and returns the first result other than `None`

. If there is no such result, it returns `None`

. If `f`

is pure, then it is equivalent to ```
find direction (fun o -> o <>
None) (map f s)
```

.

Time complexity: same as `find`

, not counting the cost of the function `f`

.

`val for_all : ('a -> bool) -> 'a t -> bool`

`for_all p s`

tests whether all elements of the sequence `s`

satisfy the predicate `p`

.

Time complexity: *O(i)*, where `i`

is the index of the first element that does not satisfy `p`

, or *n* if every element satisfies `p`

. This does not count the cost of the function `p`

.

`val exists : ('a -> bool) -> 'a t -> bool`

`exists p s`

tests whether some element of the sequence `s`

satisfies the predicate `p`

.

Time complexity: *O(i)*, where `i`

is the index of the first element that satisfies `p`

, or *n* if no element satisfies `p`

. This does not count the cost of the function `p`

.

`val mem : 'a -> 'a t -> bool`

`mem x s`

is equivalent to `exists (fun y -> x = y) s`

.

`val memq : 'a -> 'a t -> bool`

`memq x s`

is equivalent to `exists (fun y -> x == y) s`

.

`map default f s`

applies the function `f`

in turn to each element of the sequence `s`

, in the forward direction, and returns a sequence of the results. The sequence `s`

is unaffected.

Time complexity: *O(n + K)*, not counting the cost of the function `f`

.

`mapi default f s`

applies the function `f`

in turn to each index-and-element pair in the sequence `s`

, in the forward direction, and returns a sequence of the results. The sequence `s`

is unaffected.

Time complexity: *O(n + K)*, not counting the cost of the function `f`

.

`rev s`

returns a sequence whose elements are the elements of the sequence `s`

, in reverse order. The sequence `s`

is unaffected.

Time complexity: *O(n + K)*.

`zip s1 s2`

is a sequence of the pairs `(x1, x2)`

, where `x1`

and `x2`

are drawn *synchronously* from the sequences `s1`

and `s2`

. The lengths of the sequences `s1`

and `s2`

need not be equal: the length of the result is the minimum of the lengths of `s1`

and `s2`

.

Time complexity: *O(n + K)*, where *n* denotes the length of the result sequence.

`unzip s`

is equivalent to `(map _ fst s, map _ snd s)`

.

Time complexity: *O(n + K)*.

`filter p s`

returns a subsequence of the elements of `s`

that satisfy the predicate `p`

. The sequence `s`

is unaffected.

Time complexity: *O(n + K)*, not counting the cost of the function `p`

.

`filter_map default f s`

returns the subsequence of the defined images of the elements of `s`

through the partial function `f`

.

Time complexity: *O(n + K)*, not counting the cost of the function `f`

.

`partition p s`

returns a pair of the subsequence of the elements of `s`

that satisfy the predicate `p`

and those that do not satisfy `p`

. The sequence `s`

is unaffected.

Time complexity: *O(n + K)*, not counting the cost of the function `p`

.

`flatten ss`

returns the iterated concatenation of the sequences in the sequence `ss`

. As a side effect, every sequence in the sequence `ss`

is cleared, and the sequence `ss`

itself is cleared.

Time complexity: same as a series of calls to `append`

.

The following functions perform synchronous iteration on two sequences. Unlike the functions in OCaml's `List`

library, they do not require the two sequences to have the same length. If one of the sequences is strictly longer than the other, then its excess elements are ignored. If this behavior is deemed undesirable, then it is up to the user to check that the sequences have the same length. This can be done in constant time.

`iter2 direction f s1 s2`

repeatedly invokes `f x1 x2`

as long as a pair of elements `(x1, x2)`

can be drawn *synchronously* from the sequences `s1`

and `s2`

. The parameter `direction`

determines on what side iteration must begin and in which direction it must progress. The lengths of the sequences `s1`

and `s2`

need not be equal: iteration stops as soon as the shortest sequence is exhausted.

Time complexity: *O(min(n1,n2))*, where *n1* and *n2* denote the lengths of the arguments `s1`

and `s2`

, not counting the cost of the function `f`

.

```
val iter2_segments :
direction ->
'a t ->
'b t ->
(('a array * int * int) -> ('b array * int * int) -> unit) ->
unit
```

`iter2_segments direction s1 s2 f`

repeatedly invokes `f seg1 seg2`

as long as a pair of nonempty array segments `seg1`

and `seg2`

of matching lengths can be drawn *synchronously* from the sequences `s1`

and `s2`

. The function `f`

is allowed to *read* these array segments. The parameter `direction`

determines on what side iteration must begin and in which direction it must progress. The lengths of the sequences `s1`

and `s2`

need not be equal: iteration stops as soon as the shortest sequence is exhausted.

Time complexity: *O(min(n1,n2)/K)*, where *n1* and *n2* denote the lengths of the arguments `s1`

and `s2`

, not counting the cost of the function `f`

.

`fold_left2`

is analogous to `iter2 forward`

, with the added feature that an accumulator is threaded through the calls to `f`

.

Time complexity: same as `iter2`

.

`fold_right2`

is analogous to `iter2 backward`

, with the added feature that an accumulator is threaded through the calls to `f`

.

Time complexity: same as `iter2`

.

`map2 d f s1 s2`

repeatedly invokes `f x1 x2`

as long as a pair of elements `(x1, x2)`

can be drawn *synchronously* from the sequences `s1`

and `s2`

, and returns the sequence of the results. Iteration is carried out in the forward direction. The lengths of the sequences `s1`

and `s2`

need not be equal: the length of the result is the minimum of the lengths of `s1`

and `s2`

.

Time complexity: *O(n + K)*, where *n* denotes the length of the result, not counting the cost of the function `f`

.

`for_all2 p s1 s2`

tests whether all pairs `(x1, x2)`

drawn synchronously from `s1`

and `s2`

satisfy the predicate `p`

. The sequences `s1`

and `s2`

need not have the same length: any excess elements are ignored.

Time complexity: *O(min(n1,n2))*, where *n1* and *n2* denote the lengths of the arguments `s1`

and `s2`

, not counting the cost of the function `p`

.

`exists2 p s`

tests whether some pair `(x1, x2)`

drawn synchronously from `s1`

and `s2`

satisfies the predicate `p`

. The sequences `s1`

and `s2`

need not have the same length: any excess elements are ignored.

Time complexity: *O(min(n1,n2))*, where *n1* and *n2* denote the lengths of the arguments `s1`

and `s2`

, not counting the cost of the function `p`

.

`equal p s1 s2`

tests whether the sequences `s1`

and `s2`

have the same length and all pairs `(x1, x2)`

drawn synchronously from `s1`

and `s2`

satisfy the predicate `p`

. If `p x1 x2`

compares the elements `x1`

and `x2`

for equality, then `equal p s1 s2`

compares the sequences `s1`

and `s2`

for equality.

Time complexity: *O(1)* if the sequences have distinct lengths; otherwise *O(i)*, where *i* is the index of the first pair that does not satisfy the predicate `p`

, or *n* if all pairs satisfy `p`

. This does not count the cost of the function `p`

.

If `cmp`

implements a preorder on elements, then `compare cmp`

implements the lexicographic preorder on sequences. (A preorder is an antisymmetric and transitive relation. For more details on comparison functions in OCaml, see the documentation of `Array.sort`

.)

Time complexity: same as `equal`

.

`val sort : ('a -> 'a -> int) -> 'a t -> unit`

`sort cmp s`

sorts the sequence `s`

according to the preorder `cmp`

. (For more details, see the documentation of `Array.sort`

.)

Time complexity: *O(n log n + K)*.

The current implementation converts the data to an array and back. A future release may provide a more efficient implementation.

`val stable_sort : ('a -> 'a -> int) -> 'a t -> unit`

`stable_sort cmp s`

sorts the sequence `s`

according to the preorder `cmp`

. (For more details, see the documentation of `Array.sort`

.) The sorting algorithm is stable: two elements that are equal according to `cmp`

are never permuted.

Time complexity: *O(n log n + K)*.

The current implementation converts the data to an array and back. A future release may provide a more efficient implementation.

`uniq cmp s`

returns a copy of the sequence `s`

where adjacent duplicate elements have been filtered out. That is, an element is dropped if it is equal (according to the preorder `cmp`

) to its left neighbor. If the sequence `s`

is sorted with respect to `cmp`

, then the sequence `uniq cmp s`

has no duplicate elements. The sequence `s`

is unaffected.

Time complexity: *O(n + K)*.

`merge cmp s1 s2`

requires the sequences `s1`

and `s2`

to be sorted with respect to the preorder `cmp`

. It constructs a new sequence that is a sorted copy of the sequence `concat s1 s2`

. The sequences `s1`

and `s2`

are unaffected.

Time complexity: *O(n + K)*, where `n`

denotes the sum of the lengths of `s1`

and `s2`

, that is, the length of the result.

`val fill : 'a t -> int -> int -> 'a -> unit`

`fill s i k x`

modifies the sequence `s`

by overwriting the elements in the range `[i, i+k)`

with the element `x`

.

Time complexity: if the sequence involves chunks that may be shared with other sequences, the complexity is *O(k + k/K * log n + K* in the worst case. If none of the chunks that correspond to the range `[i, i+k)`

were ever shared, then the cost is only *O(k + log n)*.

`blit s1 i1 s2 i2 k`

modifies the sequence `s2`

by overwriting the elements of `s2`

in the range `[i2, i2+k)`

with the elements found in the sequence `s1`

in the range `[i1, i1+k)`

. It is permitted for `s1`

and `s2`

to be the same sequence; in that case, all reads appear to take place before any writes.

Time complexity: same as `fill`

.

`val format : Stdlib.Format.formatter -> int t -> unit`

`format`

is a printer for sequences of integers. It can be installed in the OCaml toplevel loop by `#install_printer format`

. It is intended to be used only while debugging the library.

`val check : 'a t -> unit`

In a release build, `check s`

does nothing. In a development build, it checks that the data structure's internal invariant is satisfied.

On This Page