package orsetto

  1. Overview
  2. Docs
Legend:
Library
Module
Module type
Parameter
Class
Class type

Functional progressive sequences

Overview

This module provides useful extensions to the OCaml standard sequence library (which appeared in OCaml 4.07 and which is provided for OCaml 4.06 by an external compatibility shim).

A common use for sequences is to iterate the values in a container or an I/O stream. Higher-order functions are provided in the standard library for composing sequences with map, filter and fold functions. Additional higher- order functions are provided here.

A sequence that is guaranteed to terminate is said here to be a "finite" sequence, whereas a sequence guaranteed never to terminate is said to be an "infinite" sequence. An additional third possibility exists, called here "contextually limited" sequences: those which may or may not terminate depending on the evolution of enclosed state, or on the side effects of computation.

Also, a sequence is said to be "confluently persistent" if its repeated computation always produces the same values in the same order every time. Furthermore, a confluently persistent sequence is said to be "concurrently persistent" if more than one preemptively multitasked thread of execution can compute the sequence at the same time to produce the same values in the same order. A sequence that is not persistent is said to be a "volatile" sequence.

Finally, a sequence is said to be "exception safe" if it computation never raises an exception.

The type system is not used to differentiate the limit, persistence and exception safety properties of sequences.

Interface

A type alias is provided for transitional purposes.

type progress =
  1. | Rdy
  2. | Fin

A generic type to indicate whether an event sequence is A) ready to produce another step or B) finished with all production.

Generation

All the sequences constructed by the functions described in this section follow the convention described above, by releasing all references to enclosed data at the earliest opportunity.

The limit, persistence and exception safety properties of the generated sequences are listed inside parentheses for each function in this section.

val repeat : 'a -> 'a Seq.t

Use repeat v to make a sequence that always produces v. (finite, concurrently persistent, exception safe)

val compose : ('s -> ('s * 'a) option) -> 's -> 'a Seq.t

Use compose f i to make a sequence that encloses the composing function f and the initial cursor i. On each step of the sequence, the current cursor is applied to f and if Some (i, _ as v) is returned the step is P (v, compose f i), otherwise if None is returned, then the step is Z.

Accordingly, if applying f never returns None then the resulting sequence is an infinite sequence, and otherwise if f is guaranteed eventually to return None then the resulting sequence is a finite sequence. If neither is guaranteed by f, then the resulting sequence is a contextually limited sequence.

The result is a concurrently persistent sequence only if s is immutable and f is pure, i.e. it has no side effects.

The result is exception safe if f never raises an exception.

val zipcompose : ('s -> ('s * 'v) as 'a option) -> 's -> 'a Seq.t

Use zipcompose f i to make a sequence as with compose, but zipped at each step with the current cursor value.

val range : int -> int -> int Seq.t

Use range a b to make a sequence that produces on each successive step the integers starting at a and ending at b, thereafter produces no further values. If b < a then Invalid_argument is raised immediately. (finite, concurrently persistent, exception safe)

val of_option : 'a option -> 'a Seq.t

Use of_option s to make a sequence equivalent to match p with None -> nil | Some v -> one v. (finite, concurrently persistent, exception safe)

val of_list : 'a list -> 'a Seq.t

Use of_list s to make a sequence that produces each value in s beginning at the head. At each successive step only the remaining elements of the list are enclosed in the sequence. (finite, concurrently persistent, exception safe)

val of_subbytes : bytes -> int -> int -> char Seq.t

Use of_subbytes b pos len to make a sequence that produces each of the len bytes in b starting at position pos, one by one on each successive step. Immediately raises Invalid_argument if b does not contain at least len bytes starting at position pos. A reference to b is retained until the final step of the sequence. (finite, exception safe)

val of_bytes : bytes -> char Seq.t

Use of_bytes b to make a sequence that produces each of the bytes in b one by one on each successive step. A reference to b is retained until the final step of the sequence. (finite, exception safe)

val of_substring : string -> int -> int -> char Seq.t

Use of_substring s pos len to make a sequence that operates like of_subbytes does but using input of type string instead of bytes. (finite, concurrently persistent, exception safe)

val of_string : string -> char Seq.t

Use of_string s to make a sequence that operates like of_bytes does but using input of type string instead of bytes. (finite, concurrently persistent, exception safe)

val of_subarray : 'a array -> int -> int -> 'a Seq.t

Use of_subarray a pos len to make a sequence that produces each of the len values in a starting at position pos, one by one on each successive step. Immediately raises Invalid_argument if a not contain at least len values starting at position pos. A reference to a is retained until the final step of the sequence. (finite, exception safe)

val of_array : 'a array -> 'a Seq.t

Use of_array a to make a sequence that produces each of the values in a one by one on each successive step. A reference to a is retained until the final step of the sequence. (finite, exception safe)

val of_channel : in_channel -> char Seq.t

Use of_channel inc to make a contextually limited sequence that produces each byte by reading them on successive steps from the input channel inc, and by catching the End_of_file exception that signals no further bytes can be produced. A reference to inc is retained until the final step of the sequence.

If reading from inc is guaranteed eventually to raise End_of_file then the result is a finite sequence. The result is not confluently persistent because reading from a channel is a side effect. The result is also not exception safe because reading an I/O channel can raise the Sys_error exception.

val of_buffered_channel : int -> in_channel -> char Seq.t

Use of_buffered_channel n inc is an efficient shortcut implementation of of_channel inc |> buffermap n. See buffermap below.

Transformation

A transformer is a sequence that consumes one or more other sequences. All the transformers described in this section are confluently or concurrently persistent if and only if all the sequences provided as arguments are confluently or concurrently persistent, respectively. Likewise, they are exception safe only if all the sequences provided as arguments are exception safe.

None of the functions in this section consume any values from the sequences provided as arguments in order to compose the result. (See, however, the Consumption section below.)

val cons : 'a -> 'a Seq.t -> 'a Seq.t

Use cons v s to compose a sequence that produces v followed by the sequence s. (Compare to

ist.cons

in the standard library.)

val exnsafe : 'a Seq.t -> ('a, exn) result Seq.t

Use exnsafe s to make an exception safe transformer that progressively tries to consume a value v from s and produces Ok v, unless an exception x is caught, in which case produces Error x before terminating.

val peek : 'a Seq.t -> ('a * progress) Seq.t

Use peek s to make a transformer that progressively consumes from s an additional value ahead of the one it produces, which is annotated with Rdy if it can produce further values and Fin if no further values can be produced.

The result is finite, infinite or contextually limited according to whether s is finite, infinite or contextually limited.

val optlift : 'a Seq.t -> 'a option Seq.t

Use optlift s to make an infinite transformer that progressively tries to consume a value v from s at each step, and produces Some v if possible. Otherwise, discards s and produces None every time thereafter.

val optdown : 'a option Seq.t -> 'a Seq.t

Use optdown s to make a contextually limited transformer that progressively produces each value v while Some v is produced by s. Upon the first None produced by s, the result terminates.

val limit : int -> 'a Seq.t -> 'a Seq.t

Use limit n s to make a finite transformer that produces only the first n values consumed from s.

val concat : 'a Seq.t -> 'a Seq.t -> 'a Seq.t

Use concat s1 s2 to make a transformer that first produces all the values consumed from s1, then all the values consumed from s2.

If both s1 and s2 are finite, then the result is finite. If either s1 or s2 is infinite, then the result is infinite. If s1 is infinite, then s2 will never be evaluated, yet its enclosing state will remain live until the resulting sequence is discarded.

val buffermap : int -> char Seq.t -> string Seq.t

Use buffermap n s to make a transformer that conceptually encloses a buffer b of size n, adding characters consumed from s to produce a persistent sequence of strings of size n. (The last string in the resulting sequence is of non-zero length less than or equal to n.)

val zip : 'a Seq.t -> 'b Seq.t -> ('a * 'b) Seq.t

Use zip s1 s2 to make a transformer that produces pairs of values (a, b) by first consuming a from s1, then consuming b from s2. If either s1 or s2 terminates, the remaining values of the unterminated sequence are discarded.

If either s1 or s2 is finite, then the result is finite, else if both s1 and s2 are infinite, then the result is infinite. Otherwise, neither s1 nor s2 is finite, and one or both of s1 and s2 are contextually limited, therefore the result is contextually limited.

val persist : 'a Seq.t -> 'a Seq.t

Use persist s to make a confluently persistent transformer that produces values lazily consumed from a volatile sequence s.

val gate : < syn : unit ; fin : unit.. > -> 'a Seq.t -> 'a Seq.t

Use gate g s to make a transformer that precedes each consumption of s by calling g#syn and follows each consumption by calling g#fin.

val join : 'a Seq.t Seq.t -> 'a Seq.t

Use join s to make a sequence that produces its values by consuming them in turn from each sequence produced by s.

If s and all of the sequences it produces are finite, then the result is finite. If either p or any of the sequences it produces are infinite, then the result is infinite. Otherwise, the result is contextually limited.

val unzip : ('a * 'b) Seq.t -> 'a Seq.t * 'b Seq.t

Use unzip s as an abbreviation of map fst s, map snd s. Consuming each resulting stream entails consuming s independently. If s is not a confluently persistent stream, then only one of the results may safely be consumed. If s is not a concurrently persistent stream, then both results may only be consumed in the same thread of execution.

Consumption

All the functions in this section consume one or more values from a sequence provided as an argument. In the cases where the result is a sequence, the distinction between these functions and those in the Transformers section is that values are always consumed from one or more of the sequence arguments to compose the result.

Utility functions that consume some or all of the values produced by a sequence.

val run : 'a Seq.t -> unit

Use run s to consume and ignore all the values from s. Neverreturns if s never termiantes.

val empty : 'a Seq.t -> bool

Use empty s to attempt to consume and discard a value. Returns false if successful, otherwise returns true.

val tryopt : 'a Seq.t -> 'a option

Use tryopt s to obtain Some v if a value is produced by s and otherwise None.

val head : 'a Seq.t -> 'a

Use head s to obtain the first value produced by s. Raises Not_found if no value is produced.

val tail : 'a Seq.t -> 'a Seq.t

Use tail s to discard the first value produced by s returning the sequence of remaining values. Raises Not_found if no value is produced. The result has the same limitation and persistence properties as s does.

val length : 'a Seq.t -> int

Use length s to consume and ignore all the values from s and return the number of values produced. Never returns if s never terminates.

val canshift : int -> 'a Seq.t -> bool

Use canshift n s to consume and ignore the next n values from s. Returns false if s has fewer than n values. Otherwise returns true. Raises Invalid_argument if n < 0.

val shift : int -> 'a Seq.t -> 'a Seq.t

Use shift n s to make a sequence that starts after consuming the next n values from s. Raises Invalid_argument if n < 0. The result has the same limitation and persistence properties as s does.

val predicate : ('a -> bool) -> 'a Seq.t -> bool

Use predicate f s to consume values v from s while f v is true. Returns false on the first step that f v is false. Otherwise, if s is finite, then returns true. Never returns if s does not terminate, and applying f never returns false.

val memf : ('a -> 'a -> bool) -> 'a -> 'a Seq.t -> bool

Use memf f v s to consume values v' from s until the first step is encountered from which eq v v' returns true. Returns false if the sequence is exhausted before f returns true, otherwise returns true.

val mem : 'a -> 'a Seq.t -> bool

Use mem v s as an abbreviation for memf Pervasives.(=) v s.

val find : ('a -> bool) -> 'a Seq.t -> 'a

Use find f s to consume values v from s until the first step is encountered for which f v returns true, returning v. Raises Not_found if s is exhausted before f returns true.

Use search f s to consume values v from s until the first step is encountered for which f v returns false. Returns None if f returns false for every step in the sequence. Otherwise, returns Some (v, s') where s' is the sequence of the remaining steps. Never returns if s does not terminate, and applying f never returns true. When the result is Some (_, s'), the sequence s' has the same limitation and persistence properties as s does.

val searchmap : ('a -> 'b option) -> 'a Seq.t -> ('b * 'a Seq.t) option

Use searchmap f s to consume values v from s until the first step is encountered for which f v returns Some v. Returns None if f returns None for every step in the sequence. Otherwise, returns Some (v, s') where s' is the sequence of the remaining steps. Never returns if s does not terminate, and applying f always returns None. When the result is Some (_, s'), the sequence p' has the same limitation and persistence properties as s does.

val eqf : ('a -> 'a -> bool) -> 'a Seq.t -> 'a Seq.t -> bool

Use eqf f s1 s2 with an equality comparison function f to compare sequences s1 and s2.

Returns true if both s1 and s2 terminate at the same step. Returns false if either s1 or s2 terminates before the other.

Returns false on the first step where v1 consumed from s1 and v2 is consumed from s2, and the result r of applying f v1 v2 isfalse.

Never returns if neither s1 nor s2 terminate and f v1 v2 always returns true.

val cmpf : ('a -> 'a -> int) -> 'a Seq.t -> 'a Seq.t -> int

Use cmpf f s1 s2 with a total ordering function f to compare the sequences s1 and s2.

Returns 0 if both s1 and s2 terminate at the same step. Returns -1 if s1 terminates before s2 does. Returns 1 if s2 terminates before s1 does.

On the first step where v1 consumed from s1 and v2 is consumed from s2, and the result r of applying f v1 v2 is not zero, returns r.

Never returns if neither s1 nor s2 terminate and f v1 v2 always returns 0.

val equal : 'a Seq.t -> 'a Seq.t -> bool

Use equal s1 s2 as an abbreviation for eqf Pervasives.equal s1 s2.

val compare : 'a Seq.t -> 'a Seq.t -> int

Use compare s1 s2 as an abbreviation for cmpf Pervasives.compare s1 s2.

val phyeq : 'a Seq.t -> 'a Seq.t -> bool

Use phyeq s1 s2 as an abbreviation for eqf (==) s1 s2.

val reverse : 'a Seq.t -> 'a list

Use reverse s to produce a list of the all values, in reverse order, of that consumed from the finite sequence s. Never returns and exhausts all memory if s never terminates.

val to_list : 'a Seq.t -> 'a list

Use to_list s as an abbreviation for reverse p |> List.rev.

val to_array : int -> 'a Seq.t -> 'a array

Use to_array n s to make an array comprising the first n values in the sequence s. Raises Failure if s terminates before all n elements are consumed.

val to_buffer : Buffer.t -> char Seq.t -> unit

Use to_buffer b s to consume all the characters in the finite sequence s and add them in sequence to the buffer b. Note well: if s is not finite, then to_buffer may exhaust all available memory.

val to_channel : out_channel -> char Seq.t -> unit

Use to_channel outc s to consume all the bytes from the sequence s and write them to the standard output channel outc. Note well: if s is not finite and outc is a communication channel that never closes, then to_channel may never terminate.

val to_string : int -> char Seq.t -> string

Use to_string n s to make a string comprising all the bytes in the finite sequence s. Raises Failure if s terminates before all n elements are consumed.

val to_bytes : int -> char Seq.t -> bytes

Use to_bytes s to produce a mutable byte array containing all the characters produced by the finite sequence s. Raises Failure if s terminates before all n elements are consumed.

val to_subarray : 'a array -> int -> int -> 'a Seq.t -> unit

Use to_subarray a pos len s to consume values from s and copy them into the mutable slice of the array a from position pos with length len, raising Invalid_argument if the position and length do not specify a valid slice. Raises Failure if the sequence does not provide enough values to fill the slice specified.

val to_subbytes : bytes -> int -> int -> char Seq.t -> unit

Use to_subbytes b pos len s to consume characters from s and copy them into the mutable slice of the bytes b from position pos with length len, raising Invalid_argument if the position and length do not specify a valid slice. Raises Failure if the sequence does not provide enough values to fill the slice specified.

val string_pipe : (char Seq.t -> char Seq.t) -> string -> string

Use string_pipe f s to apply f to the sequence of characters in s and consume the result to produce a new string.

val bytes_pipe : (char Seq.t -> char Seq.t) -> bytes -> bytes

Use bytes_pipe f s to apply f to the sequence of characters in s and consume the result to produce a new bytes array.

val array_pipe : ('a Seq.t -> 'a Seq.t) -> 'a array -> 'a array

Use array_pipe f a to apply f to the sequence of values in a and consume the result to produce a new array.

module Infix : sig ... end