# Module `SEK.Persistent`

The submodule `Persistent`

, also available under the name `P`

, offers an implementation of persistent (immutable) sequences. Please follow the link for details.

`type 'a t`

A sequence

`s`

of type`'a t`

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

.

### Construction

`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(1)*.

`val make : 'a -> length -> '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: for short sequences,

*O(n)*; for long sequences,*O(n/K + K)*.

`val init : 'a -> length -> (index -> '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)*, not counting the cost of the function`f`

.

### Accessors

`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 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)*.

### Stack Operations

`val push : side -> 'a t -> 'a -> 'a t`

`push side s x`

constructs and returns a new sequence obtained by pushing 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: for short sequences,

*O(n)*; for long sequences,*O(K + log n)*. For long sequences, the total cost of*m*successive`push`

operations (performed in a single-threaded fashion) is*O(K + log n + m)*. This means that one can consider that the first`push`

operation costs*O(K + log n)*and that each of the successive calls has amortized cost*O(1)*.

`val pop : side -> 'a t -> 'a * 'a t`

If the sequence

`s`

is nonempty, then`pop side s`

returns a pair of the element`x`

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

and of the sequence`s`

deprived of`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: for short sequences,

*O(n)*; for long sequences,*O(log n)*. For long sequences, the total cost of*m*successive`pop`

operations is*O(log n + m)*. This means that one can consider that the first`pop`

operation costs*O(log n)*and that each of the successive calls has amortized cost*O(1)*.

`val pop_opt : side -> 'a t -> 'a option * 'a t`

If the sequence

`s`

is nonempty, then`pop_opt side s`

returns a pair`(Some x, s')`

where`x`

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

and`s'`

is the sequence`s`

deprived of`x`

. The parameter`side`

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

is empty, the pair`(None, s)`

is returned.Time complexity: same as

`pop`

.

`val peek : side -> 'a t -> 'a`

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)*.

`val peek_opt : side -> 'a t -> 'a option`

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)*.

### Random Access

`val get : 'a t -> index -> '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: for short sequences,

*O(1)*; for long sequences,*O(log n)*, or, more precisely,*O(log (min (i, n - i)))*.

`val set : 'a t -> index -> 'a -> 'a t`

`set s i x`

returns a new sequence obtained by replacing 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 not affected.Time complexity: for short sequences,

*O(n)*; for long sequences,*O(K + log n)*, or, more precisely,*O(K + log (min (i, n - i)))*.

### Concatenation and Splitting

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

`concat s1 s2`

returns a new sequence obtained by concatenating the sequences`s1`

and`s2`

.Time complexity: for short sequences,

*O(n)*, where*n*is the length of the result of the concatenation. For long sequences, in pathological cases,`concat`

can cost as much as*O(K + log^2 n)*. In most cases, however, we expect`concat`

to cost*O(K + log n)*.

`val split : 'a t -> index -> 'a t * 'a t`

`split s i`

splits the sequence`s`

at index`i`

. It returns two sequences`s1`

and`s2`

such that the length of`s1`

is`i`

and the concatenation of`s1`

and`s2`

is`s`

. The index`i`

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

.Time complexity: if

`s1`

or`s2`

is short,*O(log n + min(|s1|, |s2|))*; otherwise*O(K + log^2 n)*, in the worst case, but in most cases, we expect`split`

to cost*O(K + log n)*, or, more precisely,*O(K + log (min (i, n - i)))*.

`val take : side -> 'a t -> index -> 'a t`

`take front s i`

splits the sequence`s`

at index`i`

and returns the first part. It is equivalent to`fst (split s i)`

.`take back s i`

also splits the sequence`s`

at index`i`

, and returns the second part. It is equivalent to`snd (split s i)`

. In either case, the index`i`

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

.Time complexity: same as

`split`

.

`val drop : side -> 'a t -> index -> 'a t`

`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`

.

`val sub : 'a t -> index -> length -> 'a t`

`sub s head size`

extracts the sequence segment defined by the sequence`s`

, the start index`head`

, and the size`size`

.Time complexity: if

`size`

is at most*T*, then`sub`

has complexity*O(size + log n)*, or, more precisely*O(size + log (min (head, n - head)))*. Otherwise,`sub`

has complexity*O(log n)*, or, more precisely,*O(log size + log (min (head, n - head)))*.

### Iteration

`val iter : direction -> ('a -> unit) -> 'a t -> unit`

`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.Time complexity:

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

.

`val iteri : direction -> (index -> 'a -> unit) -> 'a t -> unit`

`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.Time complexity:

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

.

`val iter_segments : direction -> 'a t -> 'a segments`

`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.**The function**When iterating backward, each segment must be traversed in reverse order.`f`

is not allowed to write these array segments.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`

.`fold_left f a s`

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

.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`

.`fold_right f s a`

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

.Time complexity:

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

.

### Conversion To

`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)*.

`val to_seq : direction -> 'a t -> 'a Stdlib.Seq.t`

`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)*.

### Conversion From

`val of_list_segment : 'a -> length -> '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)*. Remark: if*n > T*then the cost is*O(n + K)*, but this bound is equivalent to*O(n)*under our assumption that*K*is*O(T)*.

`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)*.

`val of_array_segment : 'a -> 'a array -> index -> length -> '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)*, where*n*, the length of the result sequence, 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.`of_array`

is*O(n)*.

`val of_seq_segment : 'a -> length -> '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)*, 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)*, not counting the cost of demanding elements from the sequence`xs`

.

### Searching

`val find : direction -> ('a -> bool) -> 'a t -> 'a`

`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`

.

`val find_opt : direction -> ('a -> bool) -> 'a t -> 'a option`

`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`

.

`val find_map : direction -> ('a -> 'b option) -> 'a t -> 'b option`

`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 that`f`

is pure, 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`

.

### Transformation

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

`map default f s`

applies the function`f`

in turn to each element of the sequence`s`

, in the forward direction, and returns the sequence of the results.Time complexity:

*O(n)*.

`val mapi : 'b -> (index -> 'a -> 'b) -> 'a t -> 'b t`

`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 the sequence of the results.Time complexity:

*O(n)*.

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

`rev s`

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

, in reverse order.Time complexity:

*O(n)*.

`val zip : 'a t -> 'b t -> ('a * 'b) t`

`zip s1 s2`

is the 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)*, where*n*denotes the length of the result sequence.

`val unzip : ('a * 'b) t -> 'a t * 'b t`

`unzip s`

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

.Time complexity:

*O(n)*.

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

`filter p s`

returns the subsequence of the elements of`s`

that satisfy the predicate`p`

.Time complexity:

*O(n)*, not counting the cost of the function`p`

.

`val filter_map : 'b -> ('a -> 'b option) -> 'a t -> 'b t`

`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)*, not counting the cost of the function`f`

.

`val partition : ('a -> bool) -> 'a t -> 'a t * 'a t`

`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`

.Time complexity:

*O(n)*, not counting the cost of the function`p`

.

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

`flatten ss`

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

.Time complexity: same as a series of calls to

`append`

.

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

`flatten_map d f s`

returns the concatenation of the images of the elements of`s`

through the function`f`

.Time complexity: the current implementation is

*O(n + K)*, where*n*denotes the length of the output sequence, not counting the cost of the function`f`

.

### Iteration over Two Sequences

`val iter2 : direction -> ('a -> 'b -> unit) -> 'a t -> 'b t -> unit`

`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, 'b) segments2`

`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`

.

`val fold_left2 : ('c -> 'a -> 'b -> 'c) -> 'c -> 'a t -> 'b t -> 'c`

`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`

.

`val fold_right2 : ('a -> 'b -> 'c -> 'c) -> 'a t -> 'b t -> 'c -> 'c`

`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`

.

`val map2 : 'c -> ('a -> 'b -> 'c) -> 'a t -> 'b t -> 'c t`

`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)*, where*n*denotes the length of the result, not counting the cost of the function`f`

.

`val for_all2 : ('a -> 'b -> bool) -> 'a t -> 'b t -> bool`

`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`

.

`val exists2 : ('a -> 'b -> bool) -> 'a t -> 'b t -> bool`

`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`

.

### Comparison

`val equal : ('a -> 'b -> bool) -> 'a t -> 'b t -> bool`

`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`

.

`val compare : ('a -> 'b -> comparison) -> 'a t -> 'b t -> comparison`

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`

.

### Sorting

`val sort : ('a -> 'a -> comparison) -> 'a t -> 'a t`

`sort cmp s`

returns a copy of the sequence`s`

that is sorted 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 -> comparison) -> 'a t -> 'a t`

`stable_sort cmp s`

returns a copy of the sequence`s`

that is sorted 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.

`val uniq : ('a -> 'a -> comparison) -> 'a t -> 'a t`

`uniq cmp s`

filters the sequence`s`

by removing adjacent duplicate elements. 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.Time complexity:

*O(n)*.

`val merge : ('a -> 'a -> comparison) -> 'a t -> 'a t -> 'a t`

`merge cmp s1 s2`

requires the sequences`s1`

and`s2`

to be sorted with respect to the preorder`cmp`

. It returns the sorted sequence`sort cmp (concat s1 s2)`

.`merge`

has complexity*O(n + K)*, where`n`

denotes the length of the result.Time complexity:

*O(n + K)*, where`n`

denotes the sum of the lengths of`s1`

and`s2`

, that is, the length of the result.

### Miscellaneous

`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.