pvec 0.1.1 · OCaml Package

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

type 'a t

Persistent vectors with elements of type 'a.

val length : 'a t -> int

length v returns the number of elements in vector v.

val empty : unit -> 'a t

empty () returns a new vector of length 0.

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

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

val append : 'a -> 'a t -> 'a t

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

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

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

val peek : 'a t -> 'a option

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

val 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

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

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

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

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

Iterators

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

Like List.map.

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

Like List.mapi.

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

Like List.fold_left.

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

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

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

Like List.iter.

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

Like iter but in reverse order.

Converters

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

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

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

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

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

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

val to_list : 'a t -> 'a list

to_list v converts vector v to a list.

val rev_to_list : 'a t -> 'a list

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

val of_list : 'a list -> 'a t

of_list v converts list l to a vector.

val to_array : 'a t -> 'a array

to_array v converts vector v to an array.

val rev_to_array : 'a t -> 'a array

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

val 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ⁿ.

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

Persistent vectors with custom branching factor.

package pvec

Basics

Unsafe of get and set

Iterators

Converters

Custom vectors