Previous  Up  Next

Module Batteries.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 Stdlib.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.

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

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.

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.

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.

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

rfind p l returns the last element x of l such as p x returns true.

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

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

rfindi p e l returns the last element ai of l along with its index i such that p i ai is true.

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.

val tl : 'a t -> 'a t

Return the given list without its first element.

val first : 'a t -> 'a

As hd

val last : 'a t -> 'a

Returns the last element of the list.

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

at l n returns the element at index n (starting from 0) in the list l.

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.

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.

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

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.

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

Eager conversion to string.

val to_stream : 'a t -> 'a Stdlib.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 Stdlib.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 [^ 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; ... ^].

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

Infix submodule regrouping all infix operators

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.