package batteries

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

Module BatteriesExceptionless.LazyListSource

include module type of Batteries.LazyList with module Labels := Batteries.LazyList.Labels

Exceptions

Sourceexception Empty_list

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

Sourceexception Invalid_index of int

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

Sourceexception Different_list_size of string

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

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

Sourcetype 'a t = 'a node_t Lazy.t

The type of a lazy list.

Sourceand '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
Sourcetype 'a enumerable = 'a t

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

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

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

Access

Sourceval nil : 'a t

The empty list.

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

Build a list from a head and a tail.

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

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

Sourceval peek : 'a t -> 'a option

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

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

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

List creation

Sourceval from : (unit -> 'a) -> 'a t

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

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

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

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

Sourceval 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.)

Sourceval 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)).

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

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

Sourceval 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

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

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

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

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

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

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

Sourceval 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

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

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

As mem, but with physical equality

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

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

Sourceval 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

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

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

Sourceval 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

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

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

Common functions

Sourceval 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).

Sourceval length : 'a t -> int

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

Causes the evaluation of all the elements of the list.

Sourceval is_empty : 'a t -> bool

Returns true if the list is empty, false otherwise.

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

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

Sourceval hd : 'a t -> 'a

Return the first element of the given list.

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

Sourceval tl : 'a t -> 'a t

Return the given list without its first element.

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

Sourceval first : 'a t -> 'a

As hd

Sourceval last : 'a t -> 'a

Returns the last element of the list.

This function takes linear time and causes the evaluation of all elements of the list

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

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

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

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

As mem_assoc but with physical equality.

Sourceval rev : 'a t -> 'a t

Eager list reversal.

Transformations

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

Sourceval rev_append : 'a t -> 'a t -> 'a t

Eager reverse-and-append

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

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

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

As lazy append

Sourceval concat : 'a t t -> 'a t

Lazy concatenation of a lazy list of lazy lists

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

Lazy concatenation of a list of lazy lists

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

Obsolete. As split_at.

Dropping elements

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

Sourceval 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
Sourceval 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 ( = ).

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

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

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

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

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

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

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

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

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

Sourceval 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

Sourceval 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).

Sourceval 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

Sourceval to_list : 'a t -> 'a list

Eager conversion to string.

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

Lazy conversion to stream.

Sourceval to_array : 'a t -> 'a array

Eager conversion to array.

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

Lazy conversion to enumeration

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

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

Lazy conversion from stream.

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

Lazy conversion from enum.

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

Sourceval of_array : 'a array -> 'a t

Eager conversion from array

Predicates

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

Sourceval 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) || ... .

Sourceval 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) && ... .

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

Sourceval eternity : unit t

An infinite list of nothing

Sorting

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

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

Sourceval stable_sort : ('a -> 'a -> int) -> 'a t -> 'a t

Operations on two lists

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

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

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

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

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

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

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

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

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

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

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

Divide a list of pairs into a pair of lists.

Boilerplate code

Printing

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

Sourcemodule Exceptionless = BatLazyList.Exceptionless

Exceptionless counterparts for error-raising operations

include module type of struct include BatLazyList.Exceptionless end
Sourceval 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.

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

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

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

Sourceval 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

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

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

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

As assoc but with physical equality

Sourcemodule Labels : sig ... end
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