spvec

This library offers semi-persistent vectors.

A semi-persistent vector represents a sequence of elements. It supports reading at an arbitrary index (get) and appending a new element at the end of the vector (push).

A semi-persistent vector apparently offers the API of a persistent data structure, where each push operation produces a new vector. At the same time, it enjoys the efficiency of a mutable data structure, where each push operation modifies the data structure in place.

This is possible because the API is restricted. At every point in time, only the most recent vector and its ancestors are considered valid. get and push must be applied to a valid vector. The call push v x is equivalent to truncate v; push v x: that is, it makes v the most recent valid vector, thereby invalidating all strict descendants of v, then creates and returns a new vector, which is a descendant of v, and is valid.

Documentation

The library offers two modules, Spvec.Safe and Spvec.Unsafe.

Spvec.Safe is safe in the sense that an attempt to use an invalid semi-persistent array is detected at runtime and results in an exception.

Spvec.Unsafe is unsafe in the sense that an attempt to use an invalid semi-persistent array is not detected at runtime and can cause undefined behavior, by which we mean incorrect results or unexpected exceptions.

Spvec.Unsafe is faster and has lower memory usage than Spvec.Safe.

We recommended using Spvec.Safe by default. Switch to Spvec.Unsafe only if superior performance is needed and only after your code has been fully debugged.

Installation and Usage

Type opam install spvec.

In your dune file, add (libraries spvec) to the description of your library or executable.