Module Base__Sequence
A sequence of elements that can be produced one at a time, on demand, normally with no sharing.
The elements are computed on demand, possibly repeating work if they are demanded multiple times. A sequence can be built by unfolding from some initial state, which will in practice often be other containers.
Most functions constructing a sequence will not immediately compute any elements of the sequence. These functions will always return in O(1), but traversing the resulting sequence may be more expensive. The most they will do immediately is generate a new internal state and a new step function.
Functions that transform existing sequences sometimes have to reconstruct some suffix of the input sequence, even if it is unmodified. For example, calling drop 1
will return a sequence with a slightly larger state and whose elements all cost slightly more to traverse. Because this is sometimes undesirable (for example, applying drop
1
n times will cost O(n) per element traversed in the result), there are also more eager versions of many functions (whose names are suffixed with _eagerly
) that do more work up front. A function has the _eagerly
suffix iff it matches both of these conditions:
- It might consume an element from an input
t
before returning.
- It only returns a
t
(not paired with something else, not wrapped in anoption
, etc.). If it returns anything other than at
and it has at least onet
input, it's probably demanding elements from the inputt
anyway.
Only *_exn
functions can raise exceptions, except if the function underlying the sequence (the f
passed to unfold
) raises, in which case the exception will cascade.
val compare : ('a -> 'a -> int) -> 'a t -> 'a t -> int
val sexp_of_t : ('a -> Base.Sexp.t) -> 'a t -> Base.Sexp.t
type 'a sequence
= 'a t
include Base.Indexed_container.S1 with type 'a t := 'a t
include Base.Container.S1
val mem : 'a t -> 'a -> equal:('a -> 'a -> bool) -> bool
Checks whether the provided element is there, using
equal
.
val length : 'a t -> int
val is_empty : 'a t -> bool
val iter : 'a t -> f:('a -> unit) -> unit
val fold : 'a t -> init:'accum -> f:('accum -> 'a -> 'accum) -> 'accum
fold t ~init ~f
returnsf (... f (f (f init e1) e2) e3 ...) en
, wheree1..en
are the elements oft
val fold_result : 'a t -> init:'accum -> f:('accum -> 'a -> ('accum, 'e) Base.Result.t) -> ('accum, 'e) Base.Result.t
fold_result t ~init ~f
is a short-circuiting version offold
that runs in theResult
monad. Iff
returns anError _
, that value is returned without any additional invocations off
.
val fold_until : 'a t -> init:'accum -> f:('accum -> 'a -> ('accum, 'final) Base__.Container_intf.Continue_or_stop.t) -> finish:('accum -> 'final) -> 'final
fold_until t ~init ~f ~finish
is a short-circuiting version offold
. Iff
returnsStop _
the computation ceases and results in that value. Iff
returnsContinue _
, the fold will proceed. Iff
never returnsStop _
, the final result is computed byfinish
.Example:
type maybe_negative = | Found_negative of int | All_nonnegative of { sum : int } (** [first_neg_or_sum list] returns the first negative number in [list], if any, otherwise returns the sum of the list. *) let first_neg_or_sum = List.fold_until ~init:0 ~f:(fun sum x -> if x < 0 then Stop (Found_negative x) else Continue (sum + x)) ~finish:(fun sum -> All_nonnegative { sum }) ;; let x = first_neg_or_sum [1; 2; 3; 4; 5] val x : maybe_negative = All_nonnegative {sum = 15} let y = first_neg_or_sum [1; 2; -3; 4; 5] val y : maybe_negative = Found_negative -3
val exists : 'a t -> f:('a -> bool) -> bool
Returns
true
if and only if there exists an element for which the provided function evaluates totrue
. This is a short-circuiting operation.
val for_all : 'a t -> f:('a -> bool) -> bool
Returns
true
if and only if the provided function evaluates totrue
for all elements. This is a short-circuiting operation.
val count : 'a t -> f:('a -> bool) -> int
Returns the number of elements for which the provided function evaluates to true.
val sum : (module Base__.Container_intf.Summable with type t = 'sum) -> 'a t -> f:('a -> 'sum) -> 'sum
Returns the sum of
f i
for alli
in the container.
val find : 'a t -> f:('a -> bool) -> 'a option
Returns as an
option
the first element for whichf
evaluates to true.
val find_map : 'a t -> f:('a -> 'b option) -> 'b option
Returns the first evaluation of
f
that returnsSome
, and returnsNone
if there is no such element.
val to_list : 'a t -> 'a list
val to_array : 'a t -> 'a array
val min_elt : 'a t -> compare:('a -> 'a -> int) -> 'a option
Returns a minimum (resp maximum) element from the collection using the provided
compare
function, orNone
if the collection is empty. In case of a tie, the first element encountered while traversing the collection is returned. The implementation usesfold
so it has the same complexity asfold
.
val max_elt : 'a t -> compare:('a -> 'a -> int) -> 'a option
val foldi : ('a t, 'a, _) Base__.Indexed_container_intf.foldi
val iteri : ('a t, 'a) Base__.Indexed_container_intf.iteri
val existsi : 'a t -> f:(int -> 'a -> bool) -> bool
val for_alli : 'a t -> f:(int -> 'a -> bool) -> bool
val counti : 'a t -> f:(int -> 'a -> bool) -> int
val findi : 'a t -> f:(int -> 'a -> bool) -> (int * 'a) option
val find_mapi : 'a t -> f:(int -> 'a -> 'b option) -> 'b option
include Base.Monad.S with type 'a t := 'a t
include Base__.Monad_intf.S_without_syntax with type 'a t := 'a t
module Monad_infix : Base__.Monad_intf.Infix with type 'a t := 'a t
val return : 'a -> 'a t
return v
returns the (trivial) computation that returns v.
val ignore_m : 'a t -> unit t
ignore_m t
ismap t ~f:(fun _ -> ())
.ignore_m
used to be calledignore
, but we decided that was a bad name, because it shadowed the widely usedCaml.ignore
. Some monads still dolet ignore = ignore_m
for historical reasons.
val empty : _ t
empty
is a sequence with no elements.
val next : 'a t -> ('a * 'a t) option
next
returns the next element of a sequence and the next tail if the sequence is not finished.
module Step : sig ... end
A
Step
describes the next step of the sequence construction.Done
indicates the sequence is finished.Skip
indicates the sequence continues with another state without producing the next element yet.Yield
outputs an element and introduces a new state.
val unfold_step : init:'s -> f:('s -> ('a, 's) Step.t) -> 'a t
unfold_step ~init ~f
constructs a sequence by giving an initial stateinit
and a functionf
explaining how to continue the next step from a given state.
val unfold : init:'s -> f:('s -> ('a * 's) option) -> 'a t
unfold ~init f
is a simplified version ofunfold_step
that does not allowSkip
.
val unfold_with : 'a t -> init:'s -> f:('s -> 'a -> ('b, 's) Step.t) -> 'b t
unfold_with t ~init ~f
folds a state through the sequencet
to create a new sequence
val unfold_with_and_finish : 'a t -> init:'s_a -> running_step:('s_a -> 'a -> ('b, 's_a) Step.t) -> inner_finished:('s_a -> 's_b) -> finishing_step:('s_b -> ('b, 's_b) Step.t) -> 'b t
unfold_with_and_finish t ~init ~running_step ~inner_finished ~finishing_step
folds a state throught
to create a new sequence (likeunfold_with t ~init ~f:running_step
), and then continues the new sequence by unfolding the final state (likeunfold_step ~init:(inner_finished final_state) ~f:finishing_step
).
val nth : 'a t -> int -> 'a option
Returns the nth element.
val nth_exn : 'a t -> int -> 'a
val folding_map : 'a t -> init:'b -> f:('b -> 'a -> 'b * 'c) -> 'c t
folding_map
is a version ofmap
that threads an accumulator through calls tof
.
val folding_mapi : 'a t -> init:'b -> f:(int -> 'b -> 'a -> 'b * 'c) -> 'c t
val mapi : 'a t -> f:(int -> 'a -> 'b) -> 'b t
val filteri : 'a t -> f:(int -> 'a -> bool) -> 'a t
val filter : 'a t -> f:('a -> bool) -> 'a t
val merge : 'a t -> 'a t -> compare:('a -> 'a -> int) -> 'a t
merge t1 t2 ~compare
merges two sorted sequencest1
andt2
, returning a sorted sequence, all according tocompare
. If two elements are equal, the one fromt1
is preferred. The behavior is undefined if the inputs aren't sorted.
module Merge_with_duplicates_element : sig ... end
val merge_with_duplicates : 'a t -> 'b t -> compare:('a -> 'b -> int) -> ('a, 'b) Merge_with_duplicates_element.t t
merge_with_duplicates_element t1 t2 ~compare
is likemerge
, except that for each element it indicates which input(s) the element comes from, usingMerge_with_duplicates_element
.
val hd : 'a t -> 'a option
val hd_exn : 'a t -> 'a
val tl : 'a t -> 'a t option
tl t
andtl_eagerly_exn t
immediately evaluates the first element oft
and returns the unevaluated tail.
val tl_eagerly_exn : 'a t -> 'a t
val find_exn : 'a t -> f:('a -> bool) -> 'a
find_exn t ~f
returns the first element oft
that satisfiesf
. It raises if there is no such element.
val for_alli : 'a t -> f:(int -> 'a -> bool) -> bool
Like
for_all
, but passes the index as an argument.
val append : 'a t -> 'a t -> 'a t
append t1 t2
first produces the elements oft1
, then produces the elements oft2
.
val concat : 'a t t -> 'a t
concat tt
produces the elements of each inner sequence sequentially. If any inner sequences are infinite, elements of subsequent inner sequences will not be reached.
val concat_mapi : 'a t -> f:(int -> 'a -> 'b t) -> 'b t
concat_mapi t ~f
is like concat_map, but passes the index as an argument.
val interleave : 'a t t -> 'a t
interleave tt
produces each element of the inner sequences oftt
eventually, even if any or all of the inner sequences are infinite. The elements of each inner sequence are produced in order with respect to that inner sequence. The manner of interleaving among the separate inner sequences is deterministic but unspecified.
val round_robin : 'a t list -> 'a t
round_robin list
is likeinterleave (of_list list)
, except that the manner of interleaving among the inner sequences is guaranteed to be round-robin. The input sequences may be of different lengths; an empty sequence is dropped from subsequent rounds of interleaving.
val zip : 'a t -> 'b t -> ('a * 'b) t
Transforms a pair of sequences into a sequence of pairs. The length of the returned sequence is the length of the shorter input. The remaining elements of the longer input are discarded.
WARNING: Unlike
List.zip
, this will not error out if the two input sequences are of different lengths, becausezip
may have already returned some elements by the time this becomes apparent.
val zip_full : 'a t -> 'b t -> [ `Left of 'a | `Both of 'a * 'b | `Right of 'b ] t
zip_full
is likezip
, but if one sequence ends before the other, then it keeps producing elements from the other sequence until it has ended as well.
val reduce_exn : 'a t -> f:('a -> 'a -> 'a) -> 'a
reduce_exn f [a1; ...; an]
isf (... (f (f a1 a2) a3) ...) an
. It fails on the empty sequence.
val reduce : 'a t -> f:('a -> 'a -> 'a) -> 'a option
val group : 'a t -> break:('a -> 'a -> bool) -> 'a list t
group l ~break
returns a sequence of lists (i.e., groups) whose concatenation is equal to the original sequence. Each group is broken wherebreak
returns true on a pair of successive elements.Example:
group ~break:(<>) (of_list ['M';'i';'s';'s';'i';'s';'s';'i';'p';'p';'i']) -> of_list [['M'];['i'];['s';'s'];['i'];['s';'s'];['i'];['p';'p'];['i']]
val find_consecutive_duplicate : 'a t -> equal:('a -> 'a -> bool) -> ('a * 'a) option
find_consecutive_duplicate t ~equal
returns the first pair of consecutive elements(a1, a2)
int
such thatequal a1 a2
. They are returned in the same order as they appear int
.
val remove_consecutive_duplicates : 'a t -> equal:('a -> 'a -> bool) -> 'a t
The same sequence with consecutive duplicates removed. The relative order of the other elements is unaffected.
val range : ?stride:int -> ?start:[ `inclusive | `exclusive ] -> ?stop:[ `inclusive | `exclusive ] -> int -> int -> int t
range ?stride ?start ?stop start_i stop_i
is the sequence of integers fromstart_i
tostop_i
, stepping bystride
. Ifstride
< 0 then we needstart_i
>stop_i
for the result to be nonempty (orstart_i
>=stop_i
in the case where both bounds are inclusive).
val init : int -> f:(int -> 'a) -> 'a t
init n ~f
is[(f 0); (f 1); ...; (f (n-1))]
. It is an error ifn < 0
.
val filter_map : 'a t -> f:('a -> 'b option) -> 'b t
filter_map t ~f
produce mapped elements oft
which are notNone
.
val filter_mapi : 'a t -> f:(int -> 'a -> 'b option) -> 'b t
filter_mapi
is just likefilter_map
, but it also passes in the index of each element tof
.
val filter_opt : 'a option t -> 'a t
filter_opt t
produces the elements oft
which are notNone
.filter_opt t
=filter_map t ~f:ident
.
val sub : 'a t -> pos:int -> len:int -> 'a t
sub t ~pos ~len
is thelen
-element subsequence oft
, starting atpos
. If the sequence is shorter thanpos + len
, it returnst[pos] ... t[l-1]
, wherel
is the length of the sequence.
val drop : 'a t -> int -> 'a t
drop t n
produces all elements oft
except the firstn
elements. If there are fewer thann
elements int
, there is no error; the resulting sequence simply produces no elements. Usually you will probably want to usedrop_eagerly
because it can be significantly cheaper.
val drop_eagerly : 'a t -> int -> 'a t
drop_eagerly t n
immediately consumes the firstn
elements oft
and returns the unevaluated tail oft
.
val take_while : 'a t -> f:('a -> bool) -> 'a t
take_while t ~f
produces the longest prefix oft
for whichf
applied to each element istrue
.
val drop_while : 'a t -> f:('a -> bool) -> 'a t
drop_while t ~f
produces the suffix oft
beginning with the first element oft
for whichf
isfalse
. Usually you will probably want to usedrop_while_option
because it can be significantly cheaper.
val drop_while_option : 'a t -> f:('a -> bool) -> ('a * 'a t) option
drop_while_option t ~f
immediately consumes the elements fromt
until the predicatef
fails and returns the first element that failed along with the unevaluated tail oft
. The first element is returned separately because the alternatives would mean forcing the consumer to evaluate the first element again (if the previous state of the sequence is returned) or take on extra cost for each element (if the element is added to the final state of the sequence usingshift_right
).
val split_n : 'a t -> int -> 'a list * 'a t
split_n t n
immediately consumes the firstn
elements oft
and returns the consumed prefix, as a list, along with the unevaluated tail oft
.
val chunks_exn : 'a t -> int -> 'a list t
chunks_exn t n
produces lists of elements oft
, up ton
elements at a time. The last list may contain fewer thann
elements. No list contains zero elements. Ifn
is not positive, it raises.
val shift_right_with_list : 'a t -> 'a list -> 'a t
shift_right_with_list t l
produces the elements ofl
, then produces the elements oft
. It is better to callshift_right_with_list
with a list of size n thanshift_right
n times; the former will require O(1) work per element produced and the latter O(n) work per element produced.
module Infix : sig ... end
val cartesian_product : 'a t -> 'b t -> ('a * 'b) t
Returns a sequence with all possible pairs. The stepper function of the second sequence passed as argument may be applied to the same state multiple times, so be careful using
cartesian_product
with expensive or side-effecting functions. If the second sequence is infinite, some values in the first sequence may not be reached.
val interleaved_cartesian_product : 'a t -> 'b t -> ('a * 'b) t
Returns a sequence that eventually reaches every possible pair of elements of the inputs, even if either or both are infinite. The step function of both inputs may be applied to the same state repeatedly, so be careful using
interleaved_cartesian_product
with expensive or side-effecting functions.
val intersperse : 'a t -> sep:'a -> 'a t
intersperse xs ~sep
producessep
between adjacent elements ofxs
, e.g.,intersperse [1;2;3] ~sep:0 = [1;0;2;0;3]
.
val cycle_list_exn : 'a list -> 'a t
cycle_list_exn xs
repeats the elements ofxs
forever. Ifxs
is empty, it raises.
val repeat : 'a -> 'a t
repeat a
repeatsa
forever.
val singleton : 'a -> 'a t
singleton a
producesa
exactly once.
val delayed_fold : 'a t -> init:'s -> f:('s -> 'a -> k:('s -> 'r) -> 'r) -> finish:('s -> 'r) -> 'r
delayed_fold
allows to do an on-demand fold, while maintaining a state.It is possible to exit early by not calling
k
inf
. It is also possible to callk
multiple times. This results in the rest of the sequence being folded over multiple times, independently.Note that
delayed_fold
, when targeting JavaScript, can result in stack overflow as JavaScript doesn't generally have tail call optimization.
val fold_m : bind:('acc_m -> f:('acc -> 'acc_m) -> 'acc_m) -> return:('acc -> 'acc_m) -> 'elt t -> init:'acc -> f:('acc -> 'elt -> 'acc_m) -> 'acc_m
fold_m
is a monad-friendly version offold
. Supply it with the monad'sreturn
andbind
, and it will chain them through the computation.
val iter_m : bind:('unit_m -> f:(unit -> 'unit_m) -> 'unit_m) -> return:(unit -> 'unit_m) -> 'elt t -> f:('elt -> 'unit_m) -> 'unit_m
iter_m
is a monad-friendly version ofiter
. Supply it with the monad'sreturn
andbind
, and it will chain them through the computation.
val to_list_rev : 'a t -> 'a list
to_list_rev t
returns a list of the elements oft
, in reverse order. It is faster thanto_list
.
val of_list : 'a list -> 'a t
val of_lazy : 'a t Base.Lazy.t -> 'a t
of_lazy t_lazy
produces a sequence that forcest_lazy
the first time it needs to compute an element.
val memoize : 'a t -> 'a t
memoize t
produces each element oft
, but also memoizes them so that if you consume the same element multiple times it is only computed once. It's a non-eager version offorce_eagerly
.
val force_eagerly : 'a t -> 'a t
force_eagerly t
precomputes the sequence. It is behaviorally equivalent toof_list (to_list t)
, but may at some point have a more efficient implementation. It's an eager version ofmemoize
.
val bounded_length : _ t -> at_most:int -> [ `Is of int | `Greater ]
bounded_length ~at_most t
returns`Is len
iflen = length t <= at_most
, and otherwise returns`Greater
. Walks through only as much of the sequence as necessary. Always returns`Greater
ifat_most < 0
.
val length_is_bounded_by : ?min:int -> ?max:int -> _ t -> bool
length_is_bounded_by ~min ~max t
returns true ifmin <= length t
andlength t <= max
Whenmin
ormax
are not provided, the check for that bound is omitted. Walks through only as much of the sequence as necessary.
module Generator : sig ... end
module Expert : sig ... end
The functions in
Expert
expose internal structure which is normally meant to be hidden. For example, at least whenf
is purely functional, it is not intended for client code to distinguish between