Up — package containers 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
type +'a t
List containing elements of type 'a
val is_empty : _ t ‑> bool
Check whether the list is empty.
val cons : 'a ‑> 'a t ‑> 'a t
Add an element at the front of the list.
val map : f:('a ‑> 'b ) ‑> 'a t ‑> 'b t
val mapi : f:(int ‑> 'a ‑> 'b ) ‑> 'a t ‑> 'b t
First element of the list, or
Raises Invalid_argument : if the list is empty.Remove the first element from the list, or
Raises Invalid_argument : if the list is empty.val front : 'a t ‑> ('a * 'a t ) option
Remove and return the first element of the list.
val front_exn : 'a t ‑> 'a * 'a t
Unsafe version of front .
Raises Invalid_argument : if the list is empty.Number of elements. Complexity O(ln n)
where n=number of elements.
val get : 'a t ‑> int ‑> 'a option
get l i
accesses the i
-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 the i
-th element of the list to v
. 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 the i
-th element of v
.
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
splits l
into a, b
such that length a = n
if length l >= n
, and such that append 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 rev_map : f:('a ‑> 'b ) ‑> 'a t ‑> 'b t
rev_map f l
is the same as map f (rev l)
.
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
is append l (append l ... l)
n
times.
val range : int ‑> int ‑> int t
range i j
is i; i+1; ... ; j
or j; j-1; ...; i
.
Conversions type 'a sequence
= ('a ‑> unit) ‑> unit
type 'a gen
= unit ‑> 'a option
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.
val to_list : 'a t ‑> 'a list
val of_list_map : f:('a ‑> 'b ) ‑> 'a list ‑> 'b t
val of_array : 'a array ‑> 'a t
val add_array : 'a t ‑> 'a array ‑> 'a t
val to_array : 'a t ‑> 'a array
More efficient than on usual lists.
val add_gen : 'a t ‑> 'a gen ‑> 'a t
val of_gen : 'a gen ‑> 'a t
val to_gen : 'a t ‑> 'a gen
Infix module Infix : sig ... end
include module type of Infix
val (@+) : 'a ‑> 'a t ‑> 'a t
val (>>=) : 'a t ‑> ('a ‑> 'b t ) ‑> 'b t
val (>|=) : 'a t ‑> ('a ‑> 'b ) ‑> 'b t
val (<*>) : ('a ‑> 'b ) t ‑> 'a t ‑> 'b t
val (--) : int ‑> int ‑> int t
val (--^) : int ‑> int ‑> int t
a --^ b
is the integer range from a
to b
, where b
is excluded.
IO type 'a printer
= Format.formatter ‑> 'a ‑> unit