Module BatSeq

Sequence of elements

A sequence represent a collection of elements, for which you never construct the complete representation.

Basically you should use a sequence when you would prefer using a list or a lazy-list but constructing the whole list explicitly would explode your memory.

All functions returning a sequence operates in time and space O(1).

Note that if you want a ``consumable sequence'', you should prefer using enumerations (from module BatEnum).

type 'a t = 'a Seq.t

A sequence is a computation which returns a list-like node

and 'a node = 'a Seq.node =
| Nil
| Cons of 'a * 'a t
include BatInterfaces.Mappable with type 'a mappable = 'a t
type 'a mappable = 'a t

The data structure, e.g. 'a List.t

val enum : 'a t -> 'a BatEnum.t

enum s returns the enumeration of all element of s.

Since enumerations are consumable and sequence are not, it is not possible to have the inverse operations, i.e. of_enum

Base operations
val length : 'a t -> int

Return the number of elements of the given sequence. This may never return if the sequence is infinite.

val hd : 'a t -> 'a

Returns the first element of the sequence or raise Invalid_argument if the sequence is empty.

val tl : 'a t -> 'a t

Returns the sequence without its first elements or raise Invalid_argument if the sequence is empty.

val is_empty : 'a t -> bool

is_empty e returns true if e does not contains any element.

val first : 'a t -> 'a

Same as hd

val last : 'a t -> 'a

Returns the last element of the sequence, or raise Invalid_argument if the sequence is empty.

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

at l n returns the element at index n (starting from 0) in the sequence l or raise Invalid_argument is the index is outside of l bounds.

val append : 'a t -> 'a t -> 'a t

append s1 s2 returns the sequence which first returns all elements of s1 then all elements of s2.

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

concat s returns the sequence which returns all the elements of all the elements of s, in the same order.

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

Same as concat.

Constructors
val nil : 'a t

nil = fun () -> Nil

val empty : 'a t

the empty sequence, containing no elements

  • since 3.3.0
val return : 'a -> 'a t

the singleton sequence, containing only the given element

  • since 3.3.0
val cons : 'a -> 'a t -> 'a t

cons e s = fun () -> Cons(e, s)

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

make n e returns the sequence of length n where all elements are e

val init : int -> (int -> 'a) -> 'a t

init n f returns the sequence returning the results of f 0, f 1.... f (n-1).

  • raises Invalid_argument

    if n < 0.

val of_list : 'a list -> 'a t

Convenience function to build a seq from a list.

  • since 2.2.0
val unfold : ('b -> ('a * 'b) option) -> 'b -> 'a t

Build a sequence from a step function and an initial value. unfold f u returns empty if f u returns None, or fun () -> Cons (x, unfold f y) if f u returns Some (x, y).

For example, unfold (function [] -> None | h::t -> Some (h,t)) l is equivalent to List.to_seq l.

  • since 3.3.0
val flat_map : ('a -> 'b t) -> 'a t -> 'b t

Map each element to a subsequence, then return each element of this sub-sequence in turn. This transformation is lazy, it only applies when the result is traversed.

  • since 3.3.0
Iterators
val iter : ('a -> unit) -> 'a t -> unit

iter f s applies f to all the elements of the sequence. Eager.

val iteri : (int -> 'a -> unit) -> 'a t -> unit

iteri f s is the same as iter f s, but f is given the index of each element (starting at 0).

  • since 2.2.0
val iter2 : ('a -> 'b -> unit) -> 'a t -> 'b t -> unit

iter2 f s1 s2 iterates on elements of s1 and s2 pairwise, and stops when it meets the end of s1 or s2

  • since 2.2.0
val map : ('a -> 'b) -> 'a t -> 'b t

map f s returns the sequence where elements are elements of s mapped with f. Lazy.

val mapi : (int -> 'a -> 'b) -> 'a t -> 'b t

mapi f s lazily maps elements of s into a new sequence, using f. f is also given elements' indexes.

  • since 2.2.0
val map2 : ('a -> 'b -> 'c) -> 'a t -> 'b t -> 'c t

map2 f s1 s2 returns a sequence of elements, resulting from combininig elements of s1 and s2 at the same index using f. The result is as long as the shortest argument.

  • since 2.2.0
val fold_left : ('a -> 'b -> 'a) -> 'a -> 'b t -> 'a

fold_left f a (cons b0 (... bn)) is f (... (f (f a b0) b1) ...) bn. Tail-recursive, eager.

val fold_right : ('a -> 'b -> 'b) -> 'a t -> 'b -> 'b

fold_right f (cons a0 (cons a1 (cons a2 ...))) b is f a0 (f a1 (f a2 ...)). Not tail-recursive, eager.

val reduce : ('a -> 'a -> 'a) -> 'a t -> 'a

reduce f (cons e s) is fold_left f e s.

  • raises Invalid_argument

    on empty sequences.

val max : 'a t -> 'a

max s returns the largest value in s as judged by Pervasives.compare

  • raises Invalid_argument

    on empty sequences.

val min : 'a t -> 'a

min s returns the smallest value in s as judged by Pervasives.compare

  • raises Invalid_argument

    on empty sequences.

val equal : ?eq:('a -> 'a -> bool) -> 'a t -> 'a t -> bool

equal ~eq s1 s2 compares elements of s1 and s2 pairwise using eq

  • parameter eq

    optional equality function (default Pervasives.(=))

  • since 2.2.0
Sequence scanning

Most functions in the following sections have a shortcut semantic similar to the behavior of the usual (&&) and (||) operators : they will force the sequence until they find an satisfying element, and then return immediately.

For example, for_all will only diverge if the sequence begins with an infinite number of true elements --- elements for which the predicate p returns true.

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

for_all p (cons a0 (cons a1 ...)) checks if all elements of the given sequence satisfy the predicate p. That is, it returns (p a0) && (p a1) && .... Eager, shortcut.

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

exists p (cons a0 (cons a1 ...)) checks if at least one element of the sequence satisfies the predicate p. That is, it returns (p a0) || (p a1) || .... Eager, shortcut.

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

mem a l is true if and only if a is equal to an element of l. Eager, shortcut.

Sequence searching
val find : ('a -> bool) -> 'a t -> 'a option

find p s returns the first element of s such as p e returns true, if any. Eager, shortcut.

val find_map : ('a -> 'b option) -> 'a t -> 'b option

find_map p s finds the first element of s for which p e returns Some r, if any. Eager, short-cut.

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

filter p s returns the sequence of elements of s satisfying p. Lazy.

Note filter is lazy in that it returns a lazy sequence, but each element in the result is eagerly searched in the input sequence. Therefore, the access to a given element in the result will diverge if it is preceded, in the input sequence, by infinitely many false elements (elements on which the predicate p returns false).

Other functions that may drop an unbound number of elements (filter_map, take_while, etc.) have the same behavior.

val filter_map : ('a -> 'b option) -> 'a t -> 'b t

filter_map f s returns the sequence of elements filtered and mapped by f. Lazy.

Association sequences
val assoc : 'a -> ('a * 'b) t -> 'b option

assoc a s returns the value associated with key a in the sequence of pairs s. Eager, shortcut.

Sequence transformations
val take : int -> 'a t -> 'a t

take n s returns up to the n first elements from sequence s, if available. Lazy.

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

drop n s returns s without the first n elements, or the empty sequence if s have less than n elements. Lazy.

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

take_while f s returns the first elements of sequence s which satisfy the predicate f. Lazy.

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

drop_while f s returns the sequence s with the first elements satisfying the predicate f dropped. Lazy.

Sequence of pairs
val split : ('a * 'b) t -> 'a t * 'b t

split s = (map fst s, map snd s). Lazy.

val combine : 'a t -> 'b t -> ('a * 'b) t

Transform a pair of sequences into a sequence of pairs. Lazy.

  • raises Invalid_argument

    if given sequences of different length.

Printing
val print : ?first:string -> ?last:string -> ?sep:string -> ('a BatInnerIO.output -> 'b -> unit) -> 'a BatInnerIO.output -> 'b t -> unit

Print the contents of a sequence

val to_buffer : ?first:string -> ?last:string -> ?sep:string -> ('a -> string) -> Buffer.t -> (unit -> 'a node) -> unit

Convert a sequence to a string in the given buffer; eager.

  • since 2.10.0
val to_string : ?first:string -> ?last:string -> ?sep:string -> ('a -> string) -> 'a t -> string

Convert the sequence to a string; eager.

  • since 2.10.0
val of_string : ?first:string -> ?last:string -> ?sep:string -> (string -> 'a) -> string -> 'a t

Create a sequence by parsing a string.

  • raises Invalid_argument

    if the string is not prefixed by first.

  • raises Invalid_argument

    if the string is not suffixed by last.

  • since 2.10.0
module Infix : sig ... end

Infix operators matching those provided by BatEnum.Infix

include module type of Infix
val (--) : int -> int -> int t
val (--^) : int -> int -> int t
val (--.) : (float * float) -> float -> float t
val (---) : int -> int -> int t
val (--~) : char -> char -> char t
val (//) : 'a t -> ('a -> bool) -> 'a t
val (/@) : 'a t -> ('a -> 'b) -> 'b t
val (@/) : ('a -> 'b) -> 'a t -> 'b t
val (//@) : 'a t -> ('a -> 'b option) -> 'b t
val (@//) : ('a -> 'b option) -> 'a t -> 'b t
module Exceptionless : sig ... end