`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 Stdlib.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`.

- raises `LazyList.No_more_elements`

  to denote the end of the list.

`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 Stdlib.Lazy.t -> 'b) -> 'a t -> 'b Stdlib.Lazy.t -> 'b Stdlib.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.

- raises `Different_list_size`

  if the two lists have different lengths.

`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.

- raises `Different_list_size`

  if the two lists have different lengths.

`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.

- raises `Different_list_size`

  if the two lists have different lengths. Tail-recursive.

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

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

- raises `Different_list_size`

  if the two lists have different lengths.

`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.

- raises `Different_list_size`

  if the two lists have different lengths.

`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); ... ^]`.

- raises `Different_list_size`

  if the two lists have different lengths. Tail-recursive, lazy.

`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`
`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`