module Seq: BatSeq
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 Stdlib.Seq.t
A sequence is a computation which returns a list-like node
type'a
node ='a Stdlib.Seq.node
=
| |
Nil |
| |
Cons of |
include BatInterfaces.Mappable
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
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 BatSeq.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 BatSeq.concat
.
val nil : 'a t
nil = fun () -> Nil
val empty : 'a t
the empty sequence, containing no elements
val return : 'a -> 'a t
the singleton sequence, containing only the given element
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)
.
Invalid_argument
if n < 0
.val of_list : 'a list -> 'a t
Convenience function to build a seq from a list.
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
.
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.
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).
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
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.
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.
val fold_left : ('a -> 'b -> 'a) -> 'a -> 'b t -> 'a
fold_left f a (cons b0 (... bn))
is f (... (f (f a b0) b1) ...)
. Tail-recursive, eager.
bn
val fold_right : ('a -> 'b -> 'b) -> 'a t -> 'b -> 'b
fold_right f (cons a0 (cons a1 (cons a2 ...))) b
is f a0 (f
.
Not tail-recursive, eager.
a1 (f a2 ...))
val reduce : ('a -> 'a -> 'a) -> 'a t -> 'a
reduce f (cons e s)
is fold_left f e s
.
Invalid_argument
on empty sequences.val max : 'a t -> 'a
max s
returns the largest value in s
as judged by
Pervasives.compare
Invalid_argument
on empty sequences.val min : 'a t -> 'a
min s
returns the smallest value in s
as judged by
Pervasives.compare
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
eq
: optional equality function (default Pervasives.(=)
)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.
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.
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.
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.
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.
Invalid_argument
if given sequences of different length.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) -> Stdlib.Buffer.t -> (unit -> 'a node) -> unit
Convert a sequence to a string in the given buffer; eager.
val to_string : ?first:string ->
?last:string -> ?sep:string -> ('a -> string) -> 'a t -> string
Convert the sequence to a string; eager.
val of_string : ?first:string ->
?last:string -> ?sep:string -> (string -> 'a) -> string -> 'a t
Create a sequence by parsing a string.
Invalid_argument
if the string is not prefixed by first
.Invalid_argument
if the string is not suffixed by last
.module Infix:sig
..end
include BatSeq.Infix
module Exceptionless:sig
..end