Prelude.VECTORFast 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:
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 tval 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 len : 'a t -> int(len v) is the length of vector v.
(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.
(map f v) is the vector v' such that ∀i: (get i v') = (get i v |> f).
(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).
module Ops : sig ... endInfix operators.