module SkewBinaryList:`sig`

..`end`

Random access lists based on skew binary numbers

This module implements random access lists with O(1) `hd`

and `tl`

operations and O(log n) `lookup`

and `update`

operations.

`type ``'a`

t

The type of random access lists

`val empty : ``'a t`

The empty list

`val is_empty : ``'a t -> bool`

Returns tree if the list is emtpy.

`val length : ``'a t -> int`

`length t`

returns the lenth of the list `t`

. Runs in O(log n)
time and O(1) stack space where n is the number of elements in
the list.`val rev : ``'a t -> 'a t`

`rev t`

Reverse the list `t`

. Runs in O(n) run and O(1) stack
space where n is the number of elements in the list.`val cons : ``'a -> 'a t -> 'a t`

`cons x t`

Adds the element `x`

to the front of the list `t`

.
Runs in O(1) time and stack space.`val snoc : ``'a -> 'a t -> 'a t`

`snoc x t`

Adds the element `x`

to the back of the list `t`

.
Runs in O(n) time and O(1) stack space where n is the length of
the list.`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(log n) time.`val hd : ``'a t -> 'a`

`hd t`

Returns the element at the front of the list `t`

. Runs
in O(1) time and stack space. Raises `Failure "hd"`

if the list is
empty.`val tl : ``'a t -> 'a t`

`tl t`

Returns the list `t`

with the first element removed.
Runs in O(1) time and stack space. Raises `Failure "tl"`

if the
list is empty.`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 append : ``'a t ->`

'a t -> 'a t

`append t1 t2`

Appends the list `t2`

onto the back of list `t1`

.
Runs in O(n) time and O(1) stack space where n is the number of
elements in `t1`

.`val flatten : ``'a t t -> 'a t`

`flatten t`

Appends all of the elements of `t`

into a new list.
Runs in O(n) time and O(1) stack space where n is the sum of
each of the lists in `t`

.`val from_list : ``'a list -> 'a t`

`from_list l`

Convert the standard list l into a SkewBinaryList.
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 SkewBinaryList `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 * log n) stack space
where fs is the stack space required by `f`

. This function is
slightly more efficient than `Reins.SkewBinaryList.rev_map`

(yielding
a different ordering) and significantly more efficient (by a
constant factor) than ```
SkewBinaryList.rev
(SkewBinaryList.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`

.`val lookup : ``int -> 'a t -> 'a`

`lookup i t`

Returns the element at position `i`

(O-indexed) in
the list `t`

. Raises `Not_found`

if the list contains fewer
than `i-1`

elements. Runs in O(min(i,log n)) time and O(1)
stack space where n is the number of elements in `t`

.`val update : ``int -> 'a -> 'a t -> 'a t`

`update i v t`

Returns a new list where the element in position
`i`

(0-indexed) has been replaced by `v`

. Raises `Not_found`

if
the list contains fewer than `i-1`

elements. Runs in
O(min(i,log n)) time and O(1) stack space where n is the number
of elements in `t`

.