Module LList

module LList: sig .. end

A module for lazy list management.

If you use syntax extension pa_comprehension, you'll probably want to take advantage of the syntax for lazy lists.

In the original syntax, lazy lists may be written as [^ ^] (the empty list), [^ 1;2;3;4;5 ^] (the list containing 1, 2, 3, 4, 5) or 1 ^:^ [^ 2;3;4;5 ^] (again the list containing 1, 2, 3, 4, 5)

In the revised syntax, lazy lists may be written as [^ ^] (the empty list), [^ 1;2;3;4;5 ^] (the list containing 1, 2, 3, 4, 5) or [^ 1 :: [^ 2;3;4;5 ^]] (again the list containing 1, 2, 3, 4, 5).

exception LazyListFailure of string

A failure with lazy lists

Lazyness

type 'a node_t =

`\|`	`Nil`
`\|`	`Cons of 'a * 'a t`

The type of an item in the list.

type 'a t = 'a node_t Lazy.t

The type of a lazy list.

val nil : 'a node_t lazy_t

The empty list.

val iter : ('a -> 'b) -> 'a node_t Lazy.t -> unit

Eeager iteration

LList.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 node_t Lazy.t -> unit

Eeager iteration, with indices

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

LList.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 fold_left : ('a -> 'b -> 'a) -> 'a -> 'b node_t Lazy.t -> 'a

Eager fold_left

LList.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 node_t Lazy.t -> 'b

Eager fold_right

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

Common functions

val length : int node_t Lazy.t -> int

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

Causes the evaluation of all the elements of the list.

val hd : 'a node_t Lazy.t -> 'a

Return the first element of the given list. Raise LazyListFailure "hd" if the list is empty.

val tl : 'a node_t Lazy.t -> 'a t

Return the given list without its first element. Raise LazyListFailure "tl" if the list is empty.

val nth : 'a node_t Lazy.t -> int -> 'a

Return the nth element of the list. The first element is numbered 0. nth l i raises LazyListFailure "nth" if i < 0 or i >= length l.

val rev : 'a node_t Lazy.t -> 'a t

Eager list reversal.

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

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

Lazy concatenation of a list of lazy lists

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

Lazy concatenation of a lazy list of lazy lists

Conversions

val to_list : 'a node_t Lazy.t -> 'a list

Eager conversion to string.

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

Lazy conversion to stream.

val to_array : 'a node_t Lazy.t -> 'a array

Eager conversion to array.

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 eager_of_list : 'a list -> 'a t

Eager conversion from lists

val of_array : 'a array -> 'a t

Lazy conversion from array

Predicates

val filter : ('a -> bool) -> 'a node_t Lazy.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 node_t Lazy.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 node_t Lazy.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 range : int -> int -> int t

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

The range is never empty. If a <= b, the range contains a, a+1 ... b. Otherwise, it contains a, a-1, ..., b.

val map_filter : ('a -> 'b option) -> 'a node_t Lazy.t -> 'b t

Lazily eliminate some elements and transform others.

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