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 length : 'a t -> length

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

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 f is not allowed to write these array segments. When iterating backward, each segment must be traversed in reverse order.

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.

module Iter : ITER with type 'a t := 'a t and type direction := direction

The submodule Iter offers an implementation of iterators on persistent sequences.

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.