(* An (immutable) sequence of elements. *)

type 'a seq

(* The empty sequence. *)

val empty: 'a seq

(* A test for emptiness. Time O(1). *)

val is_empty: 'a seq -> bool

(* The number of elements in a sequence. Time O(log n). *)

val length: 'a seq -> int

(* Inserting an element in front of a sequence. Time O(log n). *)

val cons: 'a -> 'a seq -> 'a seq

(* Extracting and removing the element found in front of a sequence.
   Time O(log n). *)

val uncons: 'a seq -> ('a * 'a seq) option

(* Accessing the [i]-th element for reading. Time O(log n). *)

(* [i] must be comprised between [0] included and [length xs] excluded. *)

val get: int -> 'a seq -> 'a

(* Accessing the [i]-th element for updating. Time O(log n). *)

(* [i] must be comprised between [0] included and [length xs] excluded. *)

val update: int -> 'a -> 'a seq -> 'a seq