Previous  Up  Next

Module Kwffa

module Kwffa: sig .. end

Fast functional arrays (Thomas M Breuel)

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.

T h o m a s M. B r e u e l (t m b at n c a l . v e r i o . c o m)

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

Hacked by KW 2011-03-18 <http://www.lib.uchicago.edu/keith/>


Author(s): Thomas M. Breuel
type 'a ffa
The type of fast functional arrays.
val make : int -> 'a -> 'a ffa
make n init: create a fast functional array of size n with initial values set to init.
val length : 'a ffa -> int
length a: return the length of a.
val aget : 'a ffa -> int -> 'a
aget a i: return the value of a.(i).
val aset : 'a ffa -> int -> 'a -> 'a ffa
aset a i v: set a.(i) to v.
val achange : 'a ffa -> int -> ('a -> 'a) -> 'a ffa
achange a i f: set a.(i) to f a.(i).
val foldl : ('a -> int -> 'b -> 'a) -> 'a -> 'b ffa -> 'a
foldl f acc a: fold left over array a.
val map : ('a -> 'a) -> 'a ffa -> 'a ffa
map f a: map f across array a.
val mapi : (int -> 'a -> 'a) -> 'a ffa -> 'a ffa
mapi f a: map f across array a.
val to_list : 'a ffa -> 'a list
to_list a: convert array a to a list.