Sequences with element of type 'a *

The empty sequence

cons x xs adds element x at the beginning of sequence xs. x now has index 0 and xs's elements are shifted by 1. Worst-case cost is O(log n), though the amortized cost is O(1).

get i xs access the i'th element of xs in cost O(log i). In particular, access to recent elements is quasi constant.

The operation is only defined if 0 <= i < length xs, and will raise Not_found if i is out of bounds.

O(log i).

set i x xs update the i'th element of xs to value x in cost O(log i).

The operation is only defined if 0 <= i < length xs, and will raise Not_found if i is out of bounds.

O(log i).

update xs i f behaves like set i (f (get i xs)) xs.

O(log i).

n = length xs is the number of elements in xs.

O(log n).

is_empty t iff t = empty (equivalently length t = 0).

O(1).

Revert the effect of the last cons (with the same complexity).

drop n x removes n elements from x. Faster than uncons'ing n times. (TODO: determine complexity)

Returns the sequence of elements, in order (get 0, get 1, ...). O(1) per element on average, O(log n) per element worst case.

Returns the sequence of elements, in reverse order (get (length - 1), get (length - 2), ...). O(1) per element on average, O(log n) per element worst case.