Module type Prelude.VECTOR

Fast functional arrays.

NOT thread-safe.

"A fast functional array data structure using reverse diffs. This data structure can be used to translate imperative algorithms into pure functional programs without logarithmic overhead and without any special type system support (no monads or linear types).

Accesses/updates to the latest version of the array are always constant time. Access to older versions of the array have overhead proportional to the age (this can be improved using amortized rearrangement of the diff tree and instantiations of new array copies)."

Derived from code originally written around 1990 for SML/NJ.

Snarfed from: <http://caml.inria.fr/pub/ml-archives/caml-list/2000/07/bf198cc419e4449b856cdb777ff7fb41.en.html>

Hacked by KW:

type 'a t

The type of vectors.

val compare : 'a -> 'a -> int

compare is the version of compare for 'a t's.

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

(make n x) is a vector of size n with all elements equal to x.

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

(init n f) is a vector of size n whose i'th element is (f i).

val random : ?size:(unit -> int) -> (unit -> 'a) -> unit -> 'a t
val get : int -> 'a t -> 'a

(get i v) is the i'th element of v.

val (#!) : 'a t -> int -> 'a

(v #! i) is (get i v).

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

(set i x v) is the vector v with the i'th element changed to x.

val len : 'a t -> int

(len v) is the length of vector v.

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

(update f i v) is the vector v with the i'th element changed to (f (get i v)).

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

(fold f acc v) folds f over vector v.

f is called as (f acc i) where acc is the accumulator and i is the current index.

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

(map f v) is the vector v' such that ∀i: (get i v') = (get i v |> f).

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

(mapi f v) is the vector v' such that ∀i: (get i v') = (get i v |> f i).

val of_list : 'a list -> 'a t

(of_list l) is the vector v such that ∀i: (List.get i l) = (get i v).

val to_list : 'a t -> 'a list

(to_list v) is the list l such that ∀i: (get i v) = (List.get i l).

Ops

module Ops : sig ... end

Infix operators.