package batteries

  1. Overview
  2. Docs
package batteries
Legend:
Library
Module
Module type
Parameter
Class
Class type
include module type of Batteries.LazyList with module Labels := Batteries.LazyList.Labels
Exceptions
exception Empty_list

Empty_list is raised when an operation applied on an empty list is invalid. For instance, hd nil will raise Empty_list.

exception Invalid_index of int

Invalid_index is raised when an indexed access on a list is out of list bounds.

exception Different_list_size of string

Different_list_size is raised when applying functions such as iter2 on two lists having different size.

exception No_more_elements

See from and from_loop for more information on this exception.

Type

Note The types are kept concrete so as to allow pattern-matching. However, it is generally easier to manipulate nil and cons.

type 'a t = 'a node_t Lazy.t

The type of a lazy list.

and 'a node_t = 'a BatLazyList.node_t =
  1. | Nil
  2. | Cons of 'a * 'a t
    (*

    The type of an item in the list.

    *)
include BatEnum.Enumerable with type 'a enumerable = 'a t
type 'a enumerable = 'a t

The data structure, e.g. 'a List.t

include BatInterfaces.Mappable with type 'a mappable = 'a t
type 'a mappable = 'a t

The data structure, e.g. 'a List.t

Access
val nil : 'a t

The empty list.

val cons : 'a -> 'a t -> 'a t

Build a list from a head and a tail.

val (^:^) : 'a -> 'a t -> 'a t

As cons: x^:^l is the lazy list with head x and tail l

val peek : 'a t -> 'a option

peek l returns the first element of l, if it exists.

val get : 'a t -> ('a * 'a t) option

get l returns the head and tail of l, if l is not empty.

List creation
val from : (unit -> 'a) -> 'a t

from next creates a (possibly infinite) lazy list from the successive results of next.

val from_while : (unit -> 'a option) -> 'a t

from next creates a (possibly infinite) lazy list from the successive results of next. The list ends whenever next returns None.

val seq : 'a -> ('a -> 'a) -> ('a -> bool) -> 'a t

seq data next cond creates a lazy list from the successive results of applying next to data, then to the result, etc. The list continues until the condition cond fails. For example, seq 1 ((+) 1) ((>) 100) returns [^1, 2, ... 99^]. If cond init is false, the result is empty. To create an infinite lazy list, pass (fun _ -> true) as cond.

val unfold : 'b -> ('b -> ('a * 'b) option) -> 'a t

unfold data next creates a (possibly infinite) lazy list from the successive results of applying next to data, then to the result, etc. The list ends whenever next returns None. The function next should return a pair option whose first element will be the current value of the sequence; the second element will be passed (lazily) to next in order to compute the following element. One example of a use of unfold is to make each element of the resulting sequence to depend on the previous two elements, as in this Fibonacci sequence definition:

let data = (1, 1)
let next (x, y) = Some (x, (y, x + y))
let fib = unfold data next

The first element x of the pair within Some will be the current value of the sequence; the next value of the sequence, and the one after that, are recorded as y and x + y respectively.

val from_loop : 'b -> ('b -> 'a * 'b) -> 'a t

from_loop data next creates a (possibly infinite) lazy list from the successive results of applying next to data, then to the result, etc. The list ends whenever the function raises LazyList.No_more_elements. (For further information see unfold; ignore references to option and Some.)

val init : int -> (int -> 'a) -> 'a t

Similar to Array.init, init n f returns the lazy list containing the results of (f 0),(f 1).... (f (n-1)).

  • raises Invalid_argument

    "LazyList.init" if n < 0.

val make : int -> 'a -> 'a t

Similar to String.make, make n x returns a list containing n elements x.

val range : int -> int -> int t

Compute lazily a range of integers a .. b as a lazy list.

The range is empty if b <= a.

Higher-order functions
val iter : ('a -> 'b) -> 'a t -> unit

Eager iteration

iter f [^ a0; a1; ...; an ^] applies function f in turn to a0; a1; ...; an. It is equivalent to begin f a0; f a1; ...; f an; () end. In particular, it causes all the elements of the list to be evaluated.

val iteri : (int -> 'a -> unit) -> 'a t -> unit

Eager iteration, with indices

iteri f [^ a0; a1; ...; an ^] applies function f in turn to a0; a1;...; an, along with the corresponding 0,1..n index. It is equivalent to begin f 0 a0; f 1 a1; ...; f n an; () end. In particular, it causes all the elements of the list to be evaluated.

val map : ('a -> 'b) -> 'a t -> 'b t

Lazy map

map f [^ a0; a1; ... ^] builds the list [^ f a0; f a1; ... ^] with the results returned by f. Not tail-recursive. Evaluations of f take place only when the contents of the list are forced.

val mapi : (int -> 'a -> 'b) -> 'a t -> 'b t

Lazy map, with indices

mapi f [^ a0; a1; ... ^] builds the list [^ f 0 a0; f 1 a1; ... ^] with the results returned by f. Not tail-recursive. Evaluations of f take place only when the contents of the list are forced.

val fold_left : ('a -> 'b -> 'a) -> 'a -> 'b t -> 'a

Eager fold_left

LazyList.fold_left f a [^ b0; b1; ...; bn ^] is f (... (f (f a b0) b1) ...) bn. This causes evaluation of all the elements of the list.

val fold_right : ('a -> 'b -> 'b) -> 'b -> 'a t -> 'b

Eager fold_right

fold_right f b [^ a0; a1; ...; an ^] is f a0 (f a1 (... (f an b) ...)). This causes evaluation of all the elements of the list. Not tail-recursive.

Note that the argument order of this function is the same as fold_left above, but inconsistent with other fold_right functions in Batteries. We hope to fix this inconsistency in the next compatibility-breaking release, so you should rather use the more consistent eager_fold_right.

  • since 2.2.0
val eager_fold_right : ('a -> 'b -> 'b) -> 'a t -> 'b -> 'b

Eager fold_right

As fold_right above, but with the usual argument order for a fold_right.

Just as fold_left on a structure 'a t turns an element-level function of type ('b -> 'a -> 'b), with the accumulator argument 'b on the left, into a structure-level function 'b -> 'a t -> 'b, fold_right turns a function ('a -> 'b -> 'b) (accumulator on the right) into a 'a t -> 'b -> 'b.

val lazy_fold_right : ('a -> 'b Lazy.t -> 'b) -> 'a t -> 'b Lazy.t -> 'b Lazy.t

Lazy fold_right lazy_fold_right f (Cons (a0, Cons (a1, Cons (a2, nil)))) b is lazy (f a0 (lazy (f a1 (lazy (f a2 b))))).

Forcing the result of lazy_fold_right forces the first element of the list; the rest is forced only if/when the function f forces its accumulator argument.

  • since 2.1
Finding
val mem : 'a -> 'a t -> bool

mem x l determines if x is part of l. Evaluates all the elements of l which appear before x.

val memq : 'a -> 'a t -> bool

As mem, but with physical equality

val find_exn : ('a -> bool) -> exn -> 'a t -> 'a

find_exn p e l returns the first element of l such as p x returns true or raises e if such an element has not been found.

val rfind_exn : ('a -> bool) -> exn -> 'a t -> 'a

rfind_exn p e l returns the last element of l such as p x returns true or raises e if such an element has not been found.

val index_of : 'a -> 'a t -> int option

index_of e l returns the index of the first occurrence of e in l, or None if there is no occurrence of e in l

val index_ofq : 'a -> 'a t -> int option

index_ofq e l behaves as index_of e l except it uses physical equality

val rindex_of : 'a -> 'a t -> int option

index_of e l returns the index of the last occurrence of e in l, or None if there is no occurrence of e in l

val rindex_ofq : 'a -> 'a t -> int option

rindex_ofq e l behaves as rindex_of e l except it uses physical equality

Common functions
val next : 'a t -> 'a node_t

Compute and return the first node from the list as a Cons. This differs from hd, which returns the first element (the first component of the first node).

val length : 'a t -> int

Return the length (number of elements) of the given list.

Causes the evaluation of all the elements of the list.

val is_empty : 'a t -> bool

Returns true if the list is empty, false otherwise.

val would_at_fail : 'a t -> int -> bool

would_at_fail l n returns true if l contains strictly less than n elements, false otherwise

val hd : 'a t -> 'a

Return the first element of the given list.

  • raises Empty_list

    if the list is empty.

    Note: this function does not comply with the usual exceptionless error-management recommendations, as doing so would essentially render it useless.

val tl : 'a t -> 'a t

Return the given list without its first element.

  • raises Empty_list

    if the list is empty.

    Note: this function does not comply with the usual exceptionless error-management recommendations, as doing so would essentially render it useless.

val first : 'a t -> 'a

As hd

val last : 'a t -> 'a

Returns the last element of the list.

  • raises Empty_list

    if the list is empty. This function takes linear time and causes the evaluation of all elements of the list

val nth : 'a t -> int -> 'a

Obsolete. As at

Association lists

These lists behave essentially as HashMap, although they are typically faster for short number of associations, and much slower for for large number of associations.

val mem_assoc : 'a -> ('a * 'b) t -> bool

As assoc but simply returns true if a binding exists, false otherwise.

val mem_assq : 'a -> ('a * 'b) t -> bool

As mem_assoc but with physical equality.

val rev : 'a t -> 'a t

Eager list reversal.

Transformations
val eager_append : 'a t -> 'a t -> 'a t

Evaluate a list and append another list after this one.

Cost is linear in the length of the first list, not tail-recursive.

val rev_append : 'a t -> 'a t -> 'a t

Eager reverse-and-append

Cost is linear in the length of the first list, tail-recursive.

val append : 'a t -> 'a t -> 'a t

Lazy append

Cost is constant. All evaluation is delayed until the contents of the list are actually read. Reading itself is delayed by a constant.

val (^@^) : 'a t -> 'a t -> 'a t

As lazy append

val concat : 'a t t -> 'a t

Lazy concatenation of a lazy list of lazy lists

val flatten : 'a t list -> 'a t

Lazy concatenation of a list of lazy lists

val split_nth : int -> 'a t -> 'a t * 'a t

Obsolete. As split_at.

Dropping elements
val unique : ?cmp:('a -> 'a -> int) -> 'a t -> 'a t

unique cmp l returns the list l without any duplicate element. Default comparator ( = ) is used if no comparison function specified.

val unique_eq : ?eq:('a -> 'a -> bool) -> 'a t -> 'a t

as unique except only uses an equality function. Use for short lists when comparing is expensive compared to equality testing

  • since 1.3.0
val remove : 'a -> 'a t -> 'a t

remove l x returns the list l without the first element x found or returns l if no element is equal to x. Elements are compared using ( = ).

val remove_if : ('a -> bool) -> 'a t -> 'a t

remove_if cmp l is similar to remove, but with cmp used instead of ( = ).

val remove_all : 'a -> 'a t -> 'a t

remove_all l x is similar to remove but removes all elements that are equal to x and not only the first one.

val remove_all_such : ('a -> bool) -> 'a t -> 'a t

remove_all_such f l is similar to remove but removes all elements that satisfy the predicate f and not only the first one.

val take : int -> 'a t -> 'a t

take n l returns up to the n first elements from list l, if available.

val drop : int -> 'a t -> 'a t

drop n l returns l without the first n elements, or the empty list if l have less than n elements.

val take_while : ('a -> bool) -> 'a t -> 'a t

take_while f xs returns the first elements of list xs which satisfy the predicate f.

val drop_while : ('a -> bool) -> 'a t -> 'a t

drop_while f xs returns the list xs with the first elements satisfying the predicate f dropped.

Combinatorics
val combinations : 'a list -> 'a list t

combinations l yields a list of all combinations of elements of l. Each combination selects a "subset" of the elements of l (duplicates are considered as distinct elements).

val permutations : 'a list -> 'a list t

permutations l yields a lazy list of all permutations of the list l. Every permutation has the same elements as l, but in a different order. There are factorial (length l) permutations.

Conversions
val to_list : 'a t -> 'a list

Eager conversion to string.

val to_stream : 'a t -> 'a Stream.t

Lazy conversion to stream.

val to_array : 'a t -> 'a array

Eager conversion to array.

val enum : 'a t -> 'a BatEnum.t

Lazy conversion to enumeration

val of_list : 'a list -> 'a t

Lazy conversion from lists

Albeit slower than eager conversion, this is the default mechanism for converting from regular lists to lazy lists. This for two reasons : * if you're using lazy lists, total speed probably isn't as much an issue as start-up speed * this will let you convert regular infinite lists to lazy lists.

val of_stream : 'a Stream.t -> 'a t

Lazy conversion from stream.

val of_enum : 'a BatEnum.t -> 'a t

Lazy conversion from enum.

val eager_of_list : 'a list -> 'a t

Eager conversion from lists.

This function is much faster than of_list but will freeze on cyclic lists.

val of_array : 'a array -> 'a t

Eager conversion from array

Predicates
val filter : ('a -> bool) -> 'a t -> 'a t

Lazy filtering.

filter p l returns all the elements of the list l that satisfy the predicate p. The order of the elements in the input list is preserved.

val exists : ('a -> bool) -> 'a t -> bool

Eager existential.

exists p [^ a0; a1; ... ^] checks if at least one element of the list satisfies the predicate p. That is, it returns (p a0) || (p a1) || ... .

val for_all : ('a -> bool) -> 'a t -> bool

Eager universal.

for_all p [^ a0; a1; ... ^] checks if all elements of the list satisfy the predicate p. That is, it returns (p a0) && (p a1) && ... .

val filter_map : ('a -> 'b option) -> 'a t -> 'b t

Lazily eliminate some elements and transform others.

filter_map f [^ a0; a1; ... ^] applies lazily f to each a0, a1... If f ai evaluates to None, the element is not included in the result. Otherwise, if f ai evaluates to Some x, element x is included in the result.

This is equivalent to match f a0 with | Some x0 -> x0 ^:^ (match f a1 with | Some x1 -> x1 ^:^ ... | None -> [^ ^]) | None -> [^ ^] .

Misc.
val eternity : unit t

An infinite list of nothing

Sorting
val sort : ?cmp:('a -> 'a -> int) -> 'a t -> 'a t

Sort the list using optional comparator (by default compare).

val stable_sort : ('a -> 'a -> int) -> 'a t -> 'a t
Operations on two lists
val map2 : ('a -> 'b -> 'c) -> 'a t -> 'b t -> 'c t

map2 f [^ a0; a1; ...^] [^ b0; b1; ... ^] is [^ f a0 b0; f a1 b1; ... ^].

  • raises Different_list_size

    if the two lists have different lengths. Not tail-recursive, lazy. In particular, the exception is raised only after the shortest list has been entirely consumed.

val iter2 : ('a -> 'b -> unit) -> 'a t -> 'b t -> unit

iter2 f [^ a0; ...; an ^] [^ b0; ...; bn ^] calls in turn f a0 b0; ...; f an bn. Tail-recursive, eager.

val fold_left2 : ('a -> 'b -> 'c -> 'a) -> 'a -> 'b t -> 'c t -> 'a

fold_left2 f a [^ b0; b1; ...; bn ^] [^ c0; c1; ...; cn ^] is f (... (f (f a b0 c0) b1 c1) ...) bn cn. Eager.

val fold_right2 : ('a -> 'b -> 'c -> 'c) -> 'a t -> 'b t -> 'c -> 'c

fold_right2 f [^ a0; a1; ...; an ^] [^ b0; b1; ...; bn ^] c is f a0 b0 (f a1 b1 (... (f an bn c) ...)). Eager.

val for_all2 : ('a -> 'b -> bool) -> 'a t -> 'b t -> bool

Same as for_all, but for a two-argument predicate.

val equal : ('a -> 'b -> bool) -> 'a t -> 'b t -> bool

equal eq s1 s2 compares elements of s1 and s2 pairwise using eq and returns true if all elements pass the test and the lists have the same length; otherwise it returns false. Examples:

equal (=) (range 0 4) (range 0 4) (* true *)

(* Make lazy lists of lazy lists: *)
let s1 = init 5 (range 0)
let s2 = init 5 (range 0)
equal (equal (=)) s1 s2 (* true *)

(Calling = directly on a pair of lazy lists may succeed but is not guaranteed to behave consistently.)

Note that on lists of equal length, equal and for_all2 can perform the same function; their intended uses differ, however, as signaled by behavior on lists of different lengths.

val exists2 : ('a -> 'b -> bool) -> 'a t -> 'b t -> bool

Same as exists, but for a two-argument predicate.

val combine : 'a t -> 'b t -> ('a * 'b) t

Transform a pair of lists into a list of pairs: combine [^ a0; a1; ... ^] [^ b0; b1; ... ^] is [^ (a0, b0); (a1, b1); ... ^].

val uncombine : ('a * 'b) t -> 'a t * 'b t

Divide a list of pairs into a pair of lists.

module Infix = BatLazyList.Infix
Boilerplate code
Printing
val print : ?first:string -> ?last:string -> ?sep:string -> ('a BatInnerIO.output -> 'b -> unit) -> 'a BatInnerIO.output -> 'b t -> unit
Override modules

The following modules replace functions defined in LazyList with functions behaving slightly differently but having the same name. This is by design: the functions meant to override the corresponding functions of LazyList.

module Exceptionless = BatLazyList.Exceptionless

Exceptionless counterparts for error-raising operations

include module type of struct include BatLazyList.Exceptionless end

Exceptionless counterparts for error-raising operations

val find : ('a -> bool) -> 'a BatLazyList.t -> 'a option

find p l returns Some x where x is the first element of l such that p x returns true or None if such element as not been found.

val rfind : ('a -> bool) -> 'a BatLazyList.t -> 'a option

rfind p l returns Some x where x is the last element of l such that p x returns true or None if such element as not been found.

val findi : (int -> 'a -> bool) -> 'a BatLazyList.t -> (int * 'a) option

findi p e l returns Some (i, ai) where ai and i are respectively the first element of l and its index, such that p i ai is true, or None if no such element has been found.

val rfindi : (int -> 'a -> bool) -> 'a BatLazyList.t -> (int * 'a) option

rfindi p e l returns Some (i, ai) where ai and i are respectively the last element of l and its index, such that p i ai is true, or None if no such element has been found.

val split_at : int -> 'a BatLazyList.t -> [ `Ok of 'a BatLazyList.t * 'a BatLazyList.t | `Invalid_index of int ]

Whenever n is inside of l size bounds, split_at n l returns `Ok (l1,l2), where l1 contains the first n elements of l and l2 contains the others. Otherwise, returns `Invalid_index n

val at : 'a BatLazyList.t -> int -> [ `Ok of 'a | `Invalid_index of int ]

If n is inside the bounds of l, at l n returns `Ok x, where x is the n-th element of the list l. Otherwise, returns `Invalid_index n.

val assoc : 'a -> ('a * 'b) BatLazyList.t -> 'b option

assoc a l returns Some b where b is the value associated with key a in the list of pairs l. That is, assoc a [ ...; (a,b); ...] = Some b if (a,b) is the leftmost binding of a in list l. Return None if there is no value associated with a in the list l.

val assq : 'a -> ('a * 'b) BatLazyList.t -> 'b option

As assoc but with physical equality

module Labels : sig ... end