Module CCRAL
Random-Access Lists
This is an OCaml implementation of Okasaki's paper "Purely Functional Random Access Lists". It defines a list-like data structure with O(1) cons/tail operations, and O(log(n)) lookup/modification operations.
This module used to be part of containers.misc
status: stable
- since
- 0.13
val empty : 'a t
Empty list.
val is_empty : _ t -> bool
Check whether the list is empty.
val return : 'a -> 'a t
Singleton.
val hd : 'a t -> 'a
First element of the list, or
- raises Invalid_argument
if the list is empty.
val tl : 'a t -> 'a t
Remove the first element from the list, or
- raises Invalid_argument
if the list is empty.
val front_exn : 'a t -> 'a * 'a t
Unsafe version of
front
.- raises Invalid_argument
if the list is empty.
val length : 'a t -> int
Number of elements. Complexity
O(ln n)
where n=number of elements.
val get : 'a t -> int -> 'a option
get l i
accesses thei
-th element of the list.O(log(n))
.
val get_exn : 'a t -> int -> 'a
Unsafe version of
get
.- raises Invalid_argument
if the list has less than
i+1
elements.
val set : 'a t -> int -> 'a -> 'a t
set l i v
sets thei
-th element of the list tov
.O(log(n))
.- raises Invalid_argument
if the list has less than
i+1
elements.
val remove : 'a t -> int -> 'a t
remove l i
removes thei
-th element ofv
.- raises Invalid_argument
if the list has less than
i+1
elements.
val append : 'a t -> 'a t -> 'a t
val filter : f:('a -> bool) -> 'a t -> 'a t
val filter_map : f:('a -> 'b option) -> 'a t -> 'b t
val flat_map : ('a -> 'b t) -> 'a t -> 'b t
val flatten : 'a t t -> 'a t
val app : ('a -> 'b) t -> 'a t -> 'b t
val take : int -> 'a t -> 'a t
val take_while : f:('a -> bool) -> 'a t -> 'a t
val drop : int -> 'a t -> 'a t
val drop_while : f:('a -> bool) -> 'a t -> 'a t
val take_drop : int -> 'a t -> 'a t * 'a t
take_drop n l
splitsl
intoa, b
such thatlength a = n
iflength l >= n
, and such thatappend a b = l
.
val iter : f:('a -> unit) -> 'a t -> unit
Iterate on the list's elements.
val iteri : f:(int -> 'a -> unit) -> 'a t -> unit
val fold : f:('b -> 'a -> 'b) -> x:'b -> 'a t -> 'b
Fold on the list's elements.
val fold_rev : f:('b -> 'a -> 'b) -> x:'b -> 'a t -> 'b
Fold on the list's elements, in reverse order (starting from the tail).
val equal : eq:('a -> 'a -> bool) -> 'a t -> 'a t -> bool
val compare : cmp:('a -> 'a -> int) -> 'a t -> 'a t -> int
Lexicographic comparison.
Utils
val make : int -> 'a -> 'a t
val repeat : int -> 'a t -> 'a t
repeat n l
isappend l (append l ... l)
n
times.
val range : int -> int -> int t
range i j
isi; i+1; ... ; j
orj; j-1; ...; i
.
Conversions
val add_list : 'a t -> 'a list -> 'a t
val of_list : 'a list -> 'a t
Convert a list to a RAL. Caution: non tail-rec.
Infix
module Infix : sig ... end