Module `Pvec`Source

Persistent vectors based on bitwise tries.

This module implements vectors that

store n elements with keys ranging from 0 to n-1 like array,
support efficient random read and write access (almost) like array,
are persistent (= immutable) like list or Map.t, and
and grow dynamically like list or Map.t.

The implementation is based on bitwise tries. Roughly speaking, vector elements are stored in the leaves of a balanced tree and the bitwise representation of an element's index defines the path to the element in the tree. The trie uses a default branching factor of 32 (you can configure something else, see Custom vectors). Thus a vector with n elements implies trie-depth log₃₂(n). This makes lookups and modifications quasi constant time. To further speed up (series of) appends, Pvec.t batches appended elements into groups of 32 before descending into the tree.

If you want to know more, I recommend reading hyPiRion's series of blog posts about this data-type. It was my main source during implementation. Another source was the Java-implementation of Clojure's persistent vectors.

Disclaimer

I'm solo programming for fun and research. Nobody reviewed my code. My tests should cover most parts, but bugs might still be lurking. I think my persistent vectors will be useful for others, but I recommend reviewing the code before putting any stake on it. Luckily, it's only a few lines of code. If you review the code, please consider providing feedback.

Related OCaml stuff

The vector library provides dynamically growing and mutable arrays.
The vec library provides dynamically growing, mutable, and permission controlled arrays.
The containers library provides (among many others) a persistent vector similar to pvec. It's marked «experimental. DO NOT USE (yet)».

Basics

Sourcetype 'a t

Persistent vectors with elements of type 'a.

Sourceval length : 'a t -> int

length v returns the number of elements in vector v.

Sourceval empty : unit -> 'a t

empty () returns a new vector of length 0.

Sourceval init : int -> (int -> 'a) -> 'a t

init n f returns a vector of length n holding the elements f(0), f(1), ... .

Sourceval append : 'a -> 'a t -> 'a t

append x v appends x to the end of vector v and returns the updated vector.

Sourceval set : int -> 'a -> 'a t -> 'a t option

set i x v replaces the i-th element of vector v with x and returns the updated vector. For i = length v, set i x v equals append x v.

Returns None if index i is out of bounds.

Sourceval get : int -> 'a t -> 'a option

get i v reads the i-th element from vector v.

Returns None if index i is out of bounds.

Sourceval peek : 'a t -> 'a option

peek v returns the last element of vector v or None if v is empty.

Sourceval pop : 'a t -> ('a * 'a t) option

pop v removes the last element of vector v and returns the removed element together with the updated vector.

Returns None if v is empty.

Unsafe of get and set

Sourceval get_exn : int -> 'a t -> 'a

get_exn is similar to get but raises Not_found instead of returning None.

Sourceval set_exn : int -> 'a -> 'a t -> 'a t

set_exn is similar to set but raises Invalid_argument _ instead of returning None.

Iterators

Sourceval map : ('a -> 'b) -> 'a t -> 'b t

Like List.map.

Sourceval mapi : (int -> 'a -> 'b) -> 'a t -> 'b t

Like List.mapi.

Sourceval fold_left : ('a -> 'b -> 'a) -> 'a -> 'b t -> 'a

Like List.fold_left.

Sourceval fold_right : ('a -> 'b -> 'b) -> 'a t -> 'b -> 'b

Similar to List.fold_right but does not allocate additional memory.

Sourceval iter : ('a -> unit) -> 'a t -> unit

Like List.iter.

Sourceval rev_iter : ('a -> unit) -> 'a t -> unit

Like iter but in reverse order.

Converters

Sourceval to_seq : 'a t -> 'a Seq.t

to_seq v iterates over vector v front-to-back.

Sourceval rev_to_seq : 'a t -> 'a Seq.t

rev_to_seq v iterates over vector v back-to-front.

Sourceval of_seq : 'a Seq.t -> 'a t

of_seq s stores the elements of sequence s in a vector.

Sourceval to_list : 'a t -> 'a list

to_list v converts vector v to a list.

Sourceval rev_to_list : 'a t -> 'a list

rev_to_list v converts vector v to a list; reverse order.

Sourceval of_list : 'a list -> 'a t

of_list v converts list l to a vector.

Sourceval to_array : 'a t -> 'a array

to_array v converts vector v to an array.

Sourceval rev_to_array : 'a t -> 'a array

rev_to_array v converts vector v to an array; reverse order.

Sourceval of_array : 'a array -> 'a t

of_array v converts array l to a vector.

Custom vectors

The default vector t uses branching factor 32. You may create vectors with custom branching factors. After doing

module V = Pvec.Make (struct
  let branching_factor_log2 = n
end)

module V has the same interface as Pvec but its vectors use branching factor 2ⁿ.

Sourcemodule Make (_ : sig ... end) : sig ... end

Persistent vectors with custom branching factor.

package pvec