package containers

  1. Overview
  2. Docs
package containers
Legend:
Page
Library
Module
Module type
Parameter
Class
Class type
Source

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

  • since 0.13
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 v.

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 sequence = ('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_seq : 'a t -> 'a sequence -> 'a t
Sourceval of_seq : 'a sequence -> 'a t
Sourceval to_seq : 'a t -> 'a sequence
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 : ?sep:string -> 'a printer -> 'a t printer
OCaml

Innovation. Community. Security.

GitHub Discord Twitter Peertube RSS
About
Changelog Releases Industrial Users Academic Users Why OCaml
Ecosystem
Packages Community Events OCaml Planet Jobs
Resources
Install OCaml Get Started Platform Tools Language Manual Standard Library API Books Exercises Papers OCaml Playground Logo
Policies
Carbon Footprint Governance Privacy Code of Conduct