Previous  Up  Next

Module Cf_seq

module Cf_seq: sig .. end
Lazily-evaluated sequences (functional streams).

Overview


This module implements a functional stream type. It's like the built-in list type, but the tail of every element in the list is lazily evaluated. This means it is possible to represent sequences of infinite length, and define functions that operate on sequences in a functional, rather than imperative mode. Many of the other modules in the cf library make extensive use of this type.

The functions for manipulating static lists in the standard List library all have equivalents here in this module. Additionally, there are some convenient functions for converting structures with imperative interfaces into sequences that permit functional algorithms to be applied.

Types

type 'a t = 'a cell Lazy.t
A lazily-evaluated sequence.
type 'a cell =
| P of 'a * 'a t (*Element of a sequence*)
| Z (*End of sequence*)

Exceptions

exception Empty
Operation not possible on an empty list.

Functions

val nil : 'a t
An empty sequence.
val head : 'a t -> 'a
Returns the first element in the sequence. Raises Empty if the sequence has no elements, i.e. if the sequence is Z.
val tail : 'a t -> 'a t
Discards the first element in the sequence and returns the sequence of remaining elements. Raises Empty if the sequence has no elements, i.e. if the sequence is Z.
val concat : 'a t -> 'a t -> 'a t
concat a b returns the sequence of all the elements in a followed by all the elements in b. Adds a constant cost to the evaluation of every element in the resulting sequence prior to the start of elements from b, so it may be worth considering the use of a Cf_deque object in place of a Cf_seq object to avoid cost explosion.
val flatten : 'a t t -> 'a t
flatten a returns the sequence of all the elements in the sequence of sequences by concatenating them.
val limit : ?x:exn -> int -> 'a t -> 'a t
limit n s returns the sequence of all the elements in s, up to n elements in number and no more. Raises Invalid_argument if n < 0. If ?x is provided, then the exception is raised if the sequence is evaluated past the limit.
val shift : int -> 'a t -> 'a t
shift n s returns the sequence of all the elements in s after the first n elements are discarded. Returns the empty sequence if s has fewer than n elements.
val sentinel : exn -> 'a t -> 'a t
sentinel x s returns a sequence identical to s except that x is raised by evaluating to the end. This is intended for use in incremental sequence processing.
val reverse : 'a t -> 'a list
reverse s evaluates the entire sequence and composes a list of the elements in reverse order. Tail recursive.
val length : 'a t -> int
Evaluates the entire sequence and returns the number elements.
val unfold : ('b -> ('a * 'b) option) -> 'b -> 'a t
unfold f a returns the sequence composed of the results of applying f according to the following rule: the first application of f is with a as the argument; if the result is None then the empty sequence is returned; else, the result is Some (hd, tl) and the sequence returned is composed of an element hd followed by the sequence produced by looping through applications of f tl until None is returned to signal the end of the sequence.

The function is defined as follows: 

    let rec unfold f s =

        match f s with

        | Some (hd, tl) -> P (hd, lazy (unfold f tl))

        | None -> Z

    

val unfold2 : ('b -> ('a * 'b) option) -> 'b -> ('a * 'b) t
unfold2 f a is like unfold f a above, except that the sequence returned has elements which are pairs of output values and the input values that correspond to them.

The function is defined as follows: 

    

    let rec unfold2 f s =

        match f s with

        | Some (hd, tl) -> P ((hd, s), lazy (unfold2 f tl))

        | None -> Z

    

val iterate : ('a -> unit) -> 'a t -> unit
iterate f s evaluates the entire sequence s, applying f to each element in order until the end of the sequence is reached. Tail recursive.
val predicate : ('a -> bool) -> 'a t -> bool
predicate f s evaluates as much of the sequence s as necessary to determine that every element satisfy the predicate function f. If any element produces a false result, then false is returned and the remainder of the sequence is not evaluated. Otherwise, the entire sequence is evaluated and true is returned. Tail recursive.
val constrain : ('a -> bool) -> 'a t -> 'a t
constrain f s evaluates the sequence s by applying f to each element while the result is true. The returned sequence is all the elements of s before the first element for which f returns false. Tail recursive.
val search : ('a -> bool) -> 'a t -> int
search f s evaluates the sequence s until the result of applying f is true and returns the number of elements applied that resulted in a false result. Tail recursive.
val fold : ('b -> 'a -> 'b) -> 'b -> 'a t -> 'b
fold f a s is like List.fold_left and is the result of applying f to the elements in sequence, i.e. f (... (f (f a b1) b2) ...) bn, where b1, b2 ... bn are the elements of the sequence. Evaluates the entire sequence s in a tail recursive loop.
val filter : ('a -> bool) -> 'a t -> 'a t
filter f s returns the sequence produced by applying f to every element of s and taking all the elements for which the result is true. The sequence returned evaluates s on demand.
val map : ('a -> 'b) -> 'a t -> 'b t
map f s returns the sequence produced by transforming every element in s by applying it to f. The sequence returned evaluates s on demand.
val optmap : ('a -> 'b option) -> 'a t -> 'b t
optmap f s returns the sequence produced by applying f to every element of s and taking all the Some a results in order. The sequence returned evaluates s on demand.
val listmap : ('a -> 'b list) -> 'a t -> 'b t
listmap f s returns the sequence produced by applying f to every element of s and taking all the resulting lists of elements in order. The sequence returned evaluates s on demand.
val seqmap : ('a -> 'b t) -> 'a t -> 'b t
seqmap f s returns the sequence produced by applying f to every element of s and taking all the resulting sequences of elements in order. The sequence returned evaluates s on demand.
val partition : ('a -> bool) -> 'a t -> 'a t * 'a t
partition f s returns two sequences. The first is the sequence of elements in s for which applying f results in true, and the second is the sequence of elements for which applying f results in false.
val fcmp : ('a -> 'a -> int) -> 'a t -> 'a t -> int
fcmp f a b compares two sequences by applying f to the elements of each sequence in turn until the result is non-zero, or the end of one or both sequences is reached. If the result of f is non-zero, then that is the value returned; otherwise, the value returned is an indication of which sequences have ended. If a ends while b continues, then the result is 1. If b ends while a continues, then the result is (-1). If both sequences end at the same place, then 0 is returned.

The function is defined as follows: 

    let rec fcmp f s0 s1 =

        match s0, s1 with

        | P (x0, y0), P (x1, y1) ->

            let d = f x0 x1 in

            if d <> 0 then d else fcmp f (Lazy.force y0) (Lazy.force y1)

        | P _, Z -> 1

        | Z, P _ -> -1

        | Z, Z -> 0

    

val cmp : 'a t -> 'a t -> int
cmp a b is the same as fcmp Pervasives.compare a b.
val equal : 'a t -> 'a t -> bool
equal a b returns true, if every element in both sequences a and b are logically equivalent, as with the built-in (=) comparison operator. Both sequences are evaluated until one of the sequences reaches the end, or the elements in each are found to be inequivalent.
val first : ('a * 'b) t -> 'a t
first s returns the sequence of elements composed by taking only the first object in an element pair. Evaluates s on demand.
val second : ('a * 'b) t -> 'b t
second s returns the sequence of elements composed by taking only the second object in an element pair. Evaluates s on demand.
val split : ('a * 'b) t -> 'a t * 'b t
split s is equivalent to (first s, second s).
val combine : 'a t -> 'b t -> ('a * 'b) t
combine a b returns the sequence composed of the pairs of elements produced by combining each element from a and the corresponding element from b in a pair (a, b) until all the elements from one or both sequences are exhausted. The sequences a and b are evaluated on demand. The resulting sequence is only as long as the shorter of the two input sequences.
val iterate2 : ('a -> 'b -> unit) -> 'a t -> 'b t -> unit
iterate2 f a b is like iterate f s, except it operates on a pair of sequences simultaneously, until one or both sequences reaches its end.
val predicate2 : ('a -> 'b -> bool) -> 'a t -> 'b t -> bool
predicate2 f a b is like predicate f s, except it operates on a pair of sequences simultaneously, until one or both sequences reaches its end. If the sequences are not the same length, then the result is always false.
val constrain2 : ('a -> 'b -> bool) -> 'a t -> 'b t -> ('a * 'b) t
constrain2 f a b is like constrain f s, except it operates on a pair of sequences simultaneously, until one or both sequences reaches its end or the constrain returns false.
val fold2 : ('c -> 'a -> 'b -> 'c) -> 'c -> 'a t -> 'b t -> 'c
fold2 f a s1 s2 is like fold f a s, except it operates on a pair of sequences simultaneously, until one or both sequences reaches its end.
val filter2 : ('a -> 'b -> bool) -> 'a t -> 'b t -> ('a * 'b) t
filter2 f a b is like filter f s, except it operates on a pair of sequences simultaneously, until one or both sequences reaches its end.
val map2 : ('a -> 'b -> 'c) -> 'a t -> 'b t -> 'c t
map2 f a b is like map f s, except it operates on a pair of sequences simultaneously, until one or both sequences reaches its end.
val optmap2 : ('a -> 'b -> 'c option) -> 'a t -> 'b t -> 'c t
optmap2 f a b is like optmap f s, except it operates on a pair of sequences simultaneously, until one or both sequences reaches its end.
val listmap2 : ('a -> 'b -> 'c list) -> 'a t -> 'b t -> 'c t
listmap2 f a b is like listmap f s, except it operates on a pair of sequences simultaneously, until one or both sequences reaches its end.
val seqmap2 : ('a -> 'b -> 'c t) -> 'a t -> 'b t -> 'c t
seqmap2 f a b is like seqmap f s, except it operates on a pair of sequences simultaneously, until one or both sequences reaches its end.
val of_channel : Pervasives.in_channel -> char t
of_channel c returns the sequence of characters produced by reading them on demand from the channel c. (Note: this means that dueling char t sequences reading from the same in_channel object may interfere with one another.) The sequence returned ends when EOF happens on the channel.
val of_string : string -> char t
of_string s returns the sequence of characters produced by extracting them on demand from the string s with String.unsafe_get. Since the contents of strings are mutable, be advised that the character extracted from the string is determined at the time the position in the sequence is evaluated, and that subsequent changes to the string will not be reflected in the sequence.
val of_substring : string -> int -> char t
of_substring s pos returns the sequence of characters produced by extracting them on demand from the string s with String.unsafe_get. Returns Invalid_argument if pos < 0 or pos >= String.length s. The sequence ends when the end of the string is reached. If a shorter substring is desired, use the limit function in conjunction.
val of_array : 'a array -> 'a t
of_array v is like of_string s, except that it operates on an 'a array value instead of a string value.
val of_subarray : 'a array -> int -> 'a t
of_subarray v pos is like of_substring s pos, except that it operates on an 'a array value instead of a string value.
val of_list : 'a list -> 'a t
of_list s converts a 'a list value into a sequence.
val of_function : (unit -> 'a) -> 'a t
of_function f returns a sequence produced by applying f () repeatedly until Not_found is raised.
val to_channel : char t -> Pervasives.out_channel -> unit
to_channel s c evaluates the entire character sequence s and puts each character produced into the out_channel object in a tail-recursive loop.
val to_string : char t -> string
to_string s evaluates the entire character sequence s and composes a string value containing the characters in order. Tail-recursive.
val to_substring : char t -> string -> int -> int -> char t
to_substring s str pos len overwrites the substring of str starting at pos and running for len characters, with the first len characters from the sequence s. If the sequence is shorter than len characters, then the rest of the substring is not overwritten. If pos and len do not describe a valid substring of str, then Invalid_argument is raised. The unused portion of the character sequence is returned.
val to_array : 'a t -> 'a array
to_array v is like to_string s, except that it constructs an 'a array value instead of a string value.
val to_subarray : 'a t -> 'a array -> int -> int -> 'a t
to_subarray s v pos len is like to_substring s str pos len, except that it overwrites an 'a array value instead of a string value.
val to_list : 'a t -> 'a list
to_list s is the same as List.rev (reverse s).
val to_buffer : char t -> Buffer.t -> unit
to_buffer s b is like to_channel s c except that characters are output to a Buffer object, instead of an out_channel object.
val to_function : 'a t -> unit -> 'a
to_function s returns a function that evaluates the next value in the sequence each time it's called. When the sequence completes, End_of_file is raised.

Monad Functions

val writeC : 'x -> ('x t, unit) Cf_cmonad.t
Use write x to compose a continuation monad that puts x into the sequence produced by evaluation and returns the unit value.
val evalC : ('x t, unit) Cf_cmonad.t -> 'x t
Use evalC m to evaluate the continuation monad m to compute the sequence it encapsulates.
val writeSC : 'x -> ('s, 'x t, unit) Cf_scmonad.t
Use writeSC x to compose a state-continuation monad that puts x into the sequence produced by evaluation and returns the unit value.
val evalSC : ('s, 'x t, unit) Cf_scmonad.t -> 's -> 'x t
Use evalSC m s to evaluate the state-continuation monad m with the initial state s, computing the encapsulated sequence.
module S: sig .. end
The module containing the sequence and accumulate functions for the state monad. 
module C: sig .. end
The module containing the sequence and accumulate functions for the continuation monad. 
module SC: sig .. end
The module containing the sequence and accumulate functions for the state-continuation monad.