module Dlist: sig .. end
Difference list: a list-like data structure with O(1) concatenation.
Every method listed below is tail recursive, so you can use them safely.
The APIs are inspaired by
Core.List.
type 'a t
The abstract type of Dlist.
val to_list : 'a t -> 'a list
Convert a Dlist to an OCaml list. O(N), where N is the number of elements.
val of_list : 'a list -> 'a t
Convert an OCaml list to a Dlist. O(N).
val of_dlist : 'a t -> 'a t
Convert a Dlist to a Dlist by reconstruction. O(N) (strict evaluation).
val empty : unit -> 'a t
Return an empty Dlist. O(1).
val append : 'a t -> 'a t -> 'a t
Concatenate two Dlists. O(1).
val concat : 'a t list -> 'a t
Concatenate a list of Dlists. O(M), where M is the number of Dlists.
val length : 'a t -> int
Return the length of the given Dlist.
O(N).
val rev : 'a t -> 'a t
Reverse a Dlist.
O(1) (lazy evaluation).
val hd : 'a t -> 'a option
Return the first element of the given Dlist.
O(N).
val hd_exn : 'a t -> 'a
Return the first element of the given Dlist.
Raise Failure "hd" if the Dlist is empty.
O(N).
val tl : 'a t -> 'a t option
Return the given Dlist without its first element.
O(N).
val tl_exn : 'a t -> 'a t
Return the given Dlist without its first element.
Raise Failure "tl" if the Dlist is empty.
O(N).
val nth : 'a t -> int -> 'a option
Return the n-th element of the given Dlist.
The first element (head of the Dlist) is at position 0.
O(N).
val nth_exn : 'a t -> int -> 'a
Return the n-th element of the given Dlist.
The first element (head of the Dlist) is at position 0.
Raise Failure "nth" if the Dlist is too short.
Raise Invalid_argument "List.nth" if n is negative.
O(N).
val fold : 'a t -> init:'acc -> f:('acc -> 'a -> 'acc) -> 'acc
Fold the Dlist. O(N).
val fold_left : 'a t -> init:'acc -> f:('acc -> 'a -> 'acc) -> 'acc
Fold the Dlist from left. O(N).
val fold_right : 'a t -> init:'acc -> f:('a -> 'acc -> 'acc) -> 'acc
Fold the Dlist from right. O(N).
val foldi : 'a t -> init:'acc -> f:(int -> 'acc -> 'a -> 'acc) -> 'acc
Fold the Dlist with index. O(N).
val map : 'a t -> f:('a -> 'b) -> 'b t
Map the Dlist. O(1) (lazy evaluation).
val mapi : 'a t -> f:(int -> 'a -> 'b) -> 'b t
Map the Dlist with index. O(1) (lazy evaluation).
val map2 : 'a t -> 'b t -> f:('a -> 'b -> 'c) -> 'c t
Map 2 Dlists. O(1) (lazy evaluation).
Make sure that the 2 Dlists have the same length,
or excpetion will be raised when converting to list.
val iter : 'a t -> f:('a -> unit) -> unit
Iterate the Dlist. O(N).
val iteri : 'a t -> f:(int -> 'a -> unit) -> unit
Iterate the Dlist with index. O(N).