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

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