Module CCRALSource

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

Sourcetype +'a t

List containing elements of type 'a

Sourceval empty : 'a t

Empty list.

Sourceval is_empty : _ t -> bool

Check whether the list is empty.

Sourceval cons : 'a -> 'a t -> 'a t

Add an element at the front of the list.

Sourceval return : 'a -> 'a t

Singleton.

Sourceval map : f:('a -> 'b) -> 'a t -> 'b t

Map on elements.

Sourceval mapi : f:(int -> 'a -> 'b) -> 'a t -> 'b t

Map with index.

Sourceval hd : 'a t -> 'a

First element of the list, or

Sourceval tl : 'a t -> 'a t

Remove the first element from the list, or

Sourceval front : 'a t -> ('a * 'a t) option

Remove and return the first element of the list.

Sourceval front_exn : 'a t -> 'a * 'a t

Unsafe version of front.

Sourceval length : 'a t -> int

Number of elements. Complexity O(ln n) where n=number of elements.

Sourceval get : 'a t -> int -> 'a option

get l i accesses the i-th element of the list. O(log(n)).

Sourceval get_exn : 'a t -> int -> 'a

Unsafe version of get.

Sourceval set : 'a t -> int -> 'a -> 'a t

set l i v sets the i-th element of the list to v. O(log(n)).

Sourceval remove : 'a t -> int -> 'a t

remove l i removes the i-th element of l.

Sourceval get_and_remove_exn : 'a t -> int -> 'a * 'a t

get_and_remove_exn l i accesses and removes the i-th element of l.

Sourceval append : 'a t -> 'a t -> 'a t
Sourceval filter : f:('a -> bool) -> 'a t -> 'a t
Sourceval filter_map : f:('a -> 'b option) -> 'a t -> 'b t
Sourceval flat_map : ('a -> 'b t) -> 'a t -> 'b t
Sourceval flatten : 'a t t -> 'a t
Sourceval app : ('a -> 'b) t -> 'a t -> 'b t
Sourceval take : int -> 'a t -> 'a t
Sourceval take_while : f:('a -> bool) -> 'a t -> 'a t
Sourceval drop : int -> 'a t -> 'a t
Sourceval drop_while : f:('a -> bool) -> 'a t -> 'a t
Sourceval 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.

Sourceval iter : f:('a -> unit) -> 'a t -> unit

Iterate on the list's elements.

Sourceval iteri : f:(int -> 'a -> unit) -> 'a t -> unit
Sourceval fold : f:('b -> 'a -> 'b) -> x:'b -> 'a t -> 'b

Fold on the list's elements.

Sourceval fold_rev : f:('b -> 'a -> 'b) -> x:'b -> 'a t -> 'b

Fold on the list's elements, in reverse order (starting from the tail).

Sourceval rev_map : f:('a -> 'b) -> 'a t -> 'b t

rev_map f l is the same as map f (rev l).

Sourceval rev : 'a t -> 'a t

Reverse the list.

Sourceval equal : eq:('a -> 'a -> bool) -> 'a t -> 'a t -> bool
Sourceval compare : cmp:('a -> 'a -> int) -> 'a t -> 'a t -> int

Lexicographic comparison.

Utils

Sourceval make : int -> 'a -> 'a t
Sourceval repeat : int -> 'a t -> 'a t

repeat n l is append l (append l ... l) n times.

Sourceval range : int -> int -> int t

range i j is i; i+1; ... ; j or j; j-1; ...; i.

Conversions

Sourcetype 'a iter = ('a -> unit) -> unit
Sourcetype 'a gen = unit -> 'a option
Sourceval add_list : 'a t -> 'a list -> 'a t
Sourceval of_list : 'a list -> 'a t

Convert a list to a RAL. Caution: non tail-rec.

Sourceval to_list : 'a t -> 'a list
Sourceval of_list_map : f:('a -> 'b) -> 'a list -> 'b t

Combination of of_list and map.

Sourceval of_array : 'a array -> 'a t
Sourceval add_array : 'a t -> 'a array -> 'a t
Sourceval to_array : 'a t -> 'a array

More efficient than on usual lists.

Sourceval add_iter : 'a t -> 'a iter -> 'a t
Sourceval of_iter : 'a iter -> 'a t
Sourceval to_iter : 'a t -> 'a iter
Sourceval add_gen : 'a t -> 'a gen -> 'a t
Sourceval of_gen : 'a gen -> 'a t
Sourceval to_gen : 'a t -> 'a gen

Infix

Sourcemodule Infix : sig ... end
include module type of Infix
Sourceval (@+) : 'a -> 'a t -> 'a t

Cons (alias to cons).

Sourceval (>>=) : 'a t -> ('a -> 'b t) -> 'b t

Alias to flat_map.

Sourceval (>|=) : 'a t -> ('a -> 'b) -> 'b t

Alias to map.

Sourceval (<*>) : ('a -> 'b) t -> 'a t -> 'b t

Alias to app.

Sourceval (--) : int -> int -> int t

Alias to range.

Sourceval (--^) : int -> int -> int t

a --^ b is the integer range from a to b, where b is excluded.

  • since 0.17

IO

Sourcetype 'a printer = Format.formatter -> 'a -> unit
Sourceval pp : ?pp_sep:unit printer -> 'a printer -> 'a t printer