Previous  Up  Next

Module Reins.CatenableList


module CatenableList: sig .. end

Lists with fast concatenation.

This module implements lists with amortized O(1) hd, tl, and append operations.

type 'a t 
val empty : 'a t
The empty list
val is_empty : 'a t -> bool
returns true if the list is empty
val length : 'a t -> int
length t Returns the length of the list t. Runs in O(n) time and O(1) stack space
val rev : 'a t -> 'a t
rev t Returns the list t in reversed order. Runs in O(n) time and O(1) stack space.
val hd : 'a t -> 'a
hd t Return the element at the front of the list. O(1) time and stack space. If the list is empty, it raises Failure "hd".
val tl : 'a t -> 'a t
tl t Return the tail of the list (the list with the first element removed). This operation runs in amortized O(1) time and stack space. If the list is empty, it raises Failure "tl".
val pop : 'a t -> 'a * 'a t
pop t Equivalent to (hd t), (tl t) but is more efficient. Runs in amortized O(1) time and stack space. If the list is empty, it raises Failure "pop".
val cons : 'a -> 'a t -> 'a t
cons x t Adds x onto the front of the list t. Runs in amortized O(1) time and stack space.
val snoc : 'a -> 'a t -> 'a t
snoc t x Adds x onto the back of the list t. Runs in amortized O(1) time and stack space.
val last : 'a t -> 'a
last t Returns the element at the back of the list. If the list is empty, it raises Failure "last". Runs in O(1) stack and O(n) time, but may be more efficient in some circumstances when t has been constructed with several concatenations.
val append : 'a t ->
       'a t -> 'a t
append t1 t2 Appends the list t2 onto the back of list t1. Runs in amortized O(1) time and stack space.
val flatten : 'a t t -> 'a t
flatten l Appends all of the elements of l into a new list. Runs in amortized O(n) time and amortized O(1) stack space where n is the length of l.
val from_list : 'a list -> 'a t
from_list l Convert the standard list l into a CatenableList. Runs in O(n) time and O(1) stack space where n is the number of elements in l.
val to_list : 'a t -> 'a list
to_list t Convert the CatenableList t into a standard list. Runs in O(n) time and O(1) stack space where n is the number of elements in t.
val iter : ('a -> unit) -> 'a t -> unit
iter f t Iterates over each element in the list t in order and applies f to that element. Runs in O(n*ft) where ft is the running time of f and uses O(fs) stack space where fs is the stack space required by f.
val fold : ('a -> 'b -> 'a) -> 'a -> 'b t -> 'a
fold f acc t Accumulates the result acc by applying f acc x for each element x in t. Runs in O(n*ft) where ft is the running time of f and uses O(fs) stack space where fs is the stack space required by f.
val rev_map : ('a -> 'b) -> 'a t -> 'b t
rev_map f t Creates a new list by applying f to each element of t. The resulting list is in reverse order of t. Runs in O(n*ft) time where n is the number of elements in t and ft is the running time of f. It uses O(fs) stack space where fs is the stack space required by f.
val map : ('a -> 'b) -> 'a t -> 'b t
map f t Creates a new list by applying f to each element of t. The resulting list is in the same order as t. Runs in O(n*ft) time where n is the number of elements in t and ft is the running time of f. It uses O(fs) stack space where fs is the stack space required by f. This function is just as efficient as Reins.CatenableList.rev_map (yielding a different ordering) and more efficient than CatenableList.rev (CatenableList.rev_map t).
val to_string : ('a -> string) -> 'a t -> string
to_string to_s t Convert the list t into a string using to_s to individually convert each element into a string. Runs in O(n*st) where st is the running time of to_s and uses O(ss) stack space where ss is the amount of stack required by to_s.
val compare : ('a -> 'a -> int) ->
       'a t -> 'a t -> int
compare f t1 t2 Compares the lists t1 and t2 using f to compare individual elements. Returns 0 if t1 and t2 are equal (under f). Returns <0 if t1 is less than t2 and returns >0 otherwise.
val gen : (?size:int -> Random.State.t -> 'a) ->
       ?size:int -> Random.State.t -> 'a t
gen f ?size rs Generates a random list whose length is bounded by size. Each element in the list is computed by calling f ?size rs. Runs in time O(size * ft) where ft is the running time of f and uses O(fs) stack space where fs is the stack space of f.