Previous  Up  Next

Module Batteries_uni.LazyList


module LazyList: BatLazyList

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 BatLazyList.from and BatLazyList.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 BatLazyList.nil and BatLazyList.cons.

type 'a t = 'a node_t Lazy.t
The type of a lazy list.

type 'a node_t =
| Nil
| Cons of 'a * 'a t (*The type of an item in the list.*) 
include BatEnum.Enumerable
include BatInterfaces.Mappable

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. The function may raise 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 from_loop : 'a -> ('a -> 'b * 'a) -> 'b 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
val seq : 'a -> ('a -> 'a) -> ('a -> bool) -> 'a t
seq init step cond creates a sequence of data, which starts from init, extends by step, until the condition cond fails. E.g. seq 1 ((+) 1) ((>) 100) returns ^[1, 2, ... 99]^. If cond init is false, the result is empty.
val unfold : 'a -> ('a -> ('b * 'a) option) -> 'b 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 the function returns None
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)). Raise Invalid_arg "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 a <= b.


Higher-order functions

val iter : ('a -> 'b) -> 'a t -> unit
Eager iteration

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

val iteri : (int -> 'a -> 'b) -> 'a t -> unit
Eager iteration, with indices

iteri f [^ a1; ...; an ^] applies function f in turn to a1 0; ...; an (n - 1). It is equivalent to begin f a1 0; f a2 0; ...; f an (n-1); () 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 [^ a1; ...; an ^] applies function f to a1, ..., an, and builds the list ^ f a1; ...; f an ^ 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

map f [^ a1; ...; an ^] applies function f to a1, ..., an, and builds the list ^ f 0 a1; ...; f ( n - 1) an ^ 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 [^ b1; ...; bn ^] is f (... (f (f a b1) b2) ...) 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 a [^ b1; ...; bn ^] is f ( f (... (f (f a bn) ...) b2) b1. This causes evaluation of all the elements of the list. Not tail-recursive.


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 : ('a -> bool) -> 'a t -> 'a
find p l returns the first element of l such as p x returns true or raises Not_found if such an element has not been found.
val rfind : ('a -> bool) -> 'a t -> 'a
rfind p l returns the last element x of l such as p x returns true or raises Not_found if such element as not been found.
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
find_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 findi : (int -> 'a -> bool) -> 'a t -> int * 'a
findi p e l returns the first element ai of l along with its index i such that p i ai is true, or raises Not_found if no such element has been found.
val rfindi : (int -> 'a -> bool) -> 'a t -> int * 'a
findi p e l returns the last element ai of l along with its index i such that p i ai is true, or raises Not_found if no such element has 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
val next : 'a t -> 'a node_t
Common functions

Compute and return the next value of the list

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. Raise 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. Raise 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, or raise Empty_list if the list is empty. This function takes linear time and causes the evaluation of all elements of the list
val at : 'a t -> int -> 'a
at l n returns the n-th element of the list l or raise Invalid_index is the index is outside of l bounds.
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 assoc : 'a -> ('a * 'b) t -> 'b
assoc a l returns the value associated with key a in the list of pairs l. That is, assoc a [^ ...; (a,b); ...^] = b if (a,b) is the leftmost binding of a in list l. Raise Not_found if there is no value associated with a in the list l.
val assq : 'a -> ('a * 'b) t -> 'b
As BatLazyList.assoc but with physical equality
val mem_assoc : 'a -> ('a * 'b) t -> bool
As BatLazyList.assoc but simply returns true if a binding exists, false otherwise.
val mem_assq : 'a -> ('a * 'b) t -> bool
As BatLazyList.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_at : int -> 'a t -> 'a t * 'a t
split_at n l returns two lists l1 and l2, l1 containing the first n elements of l and l2 the others. Raise Invalid_index if n is outside of l size bounds.
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 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 l x is similar to remove but removes all elements that are equal to x 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.

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 BatLazyList.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 [^ a1; ...; an ^] checks if at least one element of the list satisfies the predicate p. That is, it returns (p a1) || (p a2) || ... || (p an) .

val for_all : ('a -> bool) -> 'a t -> bool
Eager universal.

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

val filter_map : ('a -> 'b option) -> 'a t -> 'b t
Lazily eliminate some elements and transform others.

filter_map f [^ a1; a2; ... ;an ^] applies f to each a1, ..., an. 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 a1 with | Some x1 -> x1 ^:^ (match f a2 with |Some x2 -> x2 ^:^ (match ... (match f an with | Some xn -> [^ xn ^] | 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
val map2 : ('a -> 'b -> 'c) -> 'a t -> 'b t -> 'c t
Operations on two lists

map2 f [^a1; ...; an^] [^b1; ...; bn^] is [f a1 b1; ...; f an bn]. Raise Different_list_size if the two lists have different lengths. Not tail-recursive, lazy.

val iter2 : ('a -> 'b -> unit) -> 'a t -> 'b t -> unit
iter2 f [a1; ...; an] [b1; ...; bn] calls in turn f a1 b1; ...; f an bn. Tail-recursive, eager. Raise 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 [b1; ...; bn] [c1; ...; cn] is f (... (f (f a b1 c1) b2 c2) ...) bn cn. Eager. Raise 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 [a1; ...; an] [b1; ...; bn] c is f a1 b1 (f a2 b2 (... (f an bn c) ...)). Eager. Raise 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 BatLazyList.for_all, but for a two-argument predicate. Raise Different_list_size if the two lists have different lengths.
val exists2 : ('a -> 'b -> bool) -> 'a t -> 'b t -> bool
Same as BatLazyList.exists, but for a two-argument predicate. Raise 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 [a1; ...; an] [b1; ...; bn] is [(a1,b1); ...; (an,bn)]. Raise Different_list_size if the two lists have different lengths. Tail-recursive.
val uncombine : ('a * 'b) t -> 'a t * 'b t
Divide a list of pairs into a pair of lists.

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: sig .. end
Exceptionless counterparts for error-raising operations 
module Labels: sig .. end
Operations on LazyList with labels.