1Stdlib.Seq(3) OCaml library Stdlib.Seq(3)
2
6 Stdlib.Seq - no description
7
9 Module Stdlib.Seq
10
12 Module Seq
13 : (module Stdlib__Seq)
14 type 'a t = unit -> 'a node
22 A sequence xs of type 'a t is a delayed list of elements of type 'a .
25 Such a sequence is queried by performing a function application xs() .
26 This function application returns a node, allowing the caller to deter‐
27 mine whether the sequence is empty or nonempty, and in the latter case,
28 to obtain its head and tail.
29 type 'a node =
32 | Nil
33 | Cons of 'a * 'a t
34 A node is either Nil , which means that the sequence is empty, or Cons
37 (x, xs) , which means that x is the first element of the sequence and
38 that xs is the remainder of the sequence.
39 Consuming sequences
44 The functions in this section consume their argument, a sequence, ei‐
45 ther partially or completely:
46 - is_empty and uncons consume the sequence down to depth 1. That is,
48 they demand the first argument of the sequence, if there is one.
49 - iter , fold_left , length , etc., consume the sequence all the way to
51 its end. They terminate only if the sequence is finite.
52 - for_all , exists , find , etc. consume the sequence down to a certain
54 depth, which is a priori unpredictable.
55 Similarly, among the functions that consume two sequences, one can dis‐
57 tinguish two groups:
58 - iter2 and fold_left2 consume both sequences all the way to the end,
60 provided the sequences have the same length.
61 - for_all2 , exists2 , equal , compare consume the sequences down to a
63 certain depth, which is a priori unpredictable.
64 The functions that consume two sequences can be applied to two se‐
66 quences of distinct lengths: in that case, the excess elements in the
67 longer sequence are ignored. (It may be the case that one excess ele‐
68 ment is demanded, even though this element is not used.)
69 None of the functions in this section is lazy. These functions are con‐
71 sumers: they force some computation to take place.
72 val is_empty : 'a t -> bool
74 is_empty xs determines whether the sequence xs is empty.
77 It is recommended that the sequence xs be persistent. Indeed, is_empty
79 xs demands the head of the sequence xs , so, if xs is ephemeral, it may
80 be the case that xs cannot be used any more after this call has taken
81 place.
82 Since 4.14
85 val uncons : 'a t -> ('a * 'a t) option
89 If xs is empty, then uncons xs is None .
91 If xs is nonempty, then uncons xs is Some (head xs, tail xs) , that is,
93 a pair of the head and tail of the sequence xs .
94 This equivalence holds if xs is persistent. If xs is ephemeral, then
96 uncons must be preferred over separate calls to head and tail , which
97 would cause xs to be queried twice.
98 Since 4.14
101 val length : 'a t -> int
105 length xs is the length of the sequence xs .
108 The sequence xs must be finite.
110 Since 4.14
113 val iter : ('a -> unit) -> 'a t -> unit
117 iter f xs invokes f x successively for every element x of the sequence
120 xs , from left to right.
121 It terminates only if the sequence xs is finite.
123 val fold_left : ('a -> 'b -> 'a) -> 'a -> 'b t -> 'a
127 fold_left f _ xs invokes f _ x successively for every element x of the
130 sequence xs , from left to right.
131 An accumulator of type 'a is threaded through the calls to f .
133 It terminates only if the sequence xs is finite.
135 val iteri : (int -> 'a -> unit) -> 'a t -> unit
139 iteri f xs invokes f i x successively for every element x located at
142 index i in the sequence xs .
143 It terminates only if the sequence xs is finite.
145 iteri f xs is equivalent to iter (fun (i, x) -> f i x) (zip (ints 0)
148 xs) .
149 Since 4.14
152 val fold_lefti : ('b -> int -> 'a -> 'b) -> 'b -> 'a t -> 'b
156 fold_lefti f _ xs invokes f _ i x successively for every element x lo‐
159 cated at index i of the sequence xs .
160 An accumulator of type 'b is threaded through the calls to f .
162 It terminates only if the sequence xs is finite.
164 fold_lefti f accu xs is equivalent to fold_left (fun accu (i, x) -> f
167 accu i x) accu (zip (ints 0) xs) .
168 Since 4.14
171 val for_all : ('a -> bool) -> 'a t -> bool
175 for_all p xs determines whether all elements x of the sequence xs sat‐
178 isfy p x .
179 The sequence xs must be finite.
181 Since 4.14
184 val exists : ('a -> bool) -> 'a t -> bool
188 exists xs p determines whether at least one element x of the sequence
191 xs satisfies p x .
192 The sequence xs must be finite.
194 Since 4.14
197 val find : ('a -> bool) -> 'a t -> 'a option
201 find p xs returns Some x , where x is the first element of the sequence
204 xs that satisfies p x , if there is such an element.
205 It returns None if there is no such element.
207 The sequence xs must be finite.
209 Since 4.14
212 val find_map : ('a -> 'b option) -> 'a t -> 'b option
216 find_map f xs returns Some y , where x is the first element of the se‐
219 quence xs such that f x = Some _ , if there is such an element, and
220 where y is defined by f x = Some y .
221 It returns None if there is no such element.
223 The sequence xs must be finite.
225 Since 4.14
228 val iter2 : ('a -> 'b -> unit) -> 'a t -> 'b t -> unit
232 iter2 f xs ys invokes f x y successively for every pair (x, y) of ele‐
235 ments drawn synchronously from the sequences xs and ys .
236 If the sequences xs and ys have different lengths, then iteration stops
238 as soon as one sequence is exhausted; the excess elements in the other
239 sequence are ignored.
240 Iteration terminates only if at least one of the sequences xs and ys is
242 finite.
243 iter2 f xs ys is equivalent to iter (fun (x, y) -> f x y) (zip xs ys) .
246 Since 4.14
249 val fold_left2 : ('a -> 'b -> 'c -> 'a) -> 'a -> 'b t -> 'c t -> 'a
253 fold_left2 f _ xs ys invokes f _ x y successively for every pair (x, y)
256 of elements drawn synchronously from the sequences xs and ys .
257 An accumulator of type 'a is threaded through the calls to f .
259 If the sequences xs and ys have different lengths, then iteration stops
261 as soon as one sequence is exhausted; the excess elements in the other
262 sequence are ignored.
263 Iteration terminates only if at least one of the sequences xs and ys is
265 finite.
266 fold_left2 f accu xs ys is equivalent to fold_left (fun accu (x, y) ->
269 f accu x y) (zip xs ys) .
270 Since 4.14
273 val for_all2 : ('a -> 'b -> bool) -> 'a t -> 'b t -> bool
277 for_all2 p xs ys determines whether all pairs (x, y) of elements drawn
280 synchronously from the sequences xs and ys satisfy p x y .
281 If the sequences xs and ys have different lengths, then iteration stops
283 as soon as one sequence is exhausted; the excess elements in the other
284 sequence are ignored. In particular, if xs or ys is empty, then
285 for_all2 p xs ys is true. This is where for_all2 and equal differ:
286 equal eq xs ys can be true only if xs and ys have the same length.
287 At least one of the sequences xs and ys must be finite.
289 for_all2 p xs ys is equivalent to for_all (fun b -> b) (map2 p xs ys) .
292 Since 4.14
295 val exists2 : ('a -> 'b -> bool) -> 'a t -> 'b t -> bool
299 exists2 p xs ys determines whether some pair (x, y) of elements drawn
302 synchronously from the sequences xs and ys satisfies p x y .
303 If the sequences xs and ys have different lengths, then iteration must
305 stop as soon as one sequence is exhausted; the excess elements in the
306 other sequence are ignored.
307 At least one of the sequences xs and ys must be finite.
309 exists2 p xs ys is equivalent to exists (fun b -> b) (map2 p xs ys) .
312 Since 4.14
315 val equal : ('a -> 'b -> bool) -> 'a t -> 'b t -> bool
319 Provided the function eq defines an equality on elements, equal eq xs
321 ys determines whether the sequences xs and ys are pointwise equal.
322 At least one of the sequences xs and ys must be finite.
324 Since 4.14
327 val compare : ('a -> 'b -> int) -> 'a t -> 'b t -> int
331 Provided the function cmp defines a preorder on elements, compare cmp
333 xs ys compares the sequences xs and ys according to the lexicographic
334 preorder.
335 For more details on comparison functions, see Array.sort .
337 At least one of the sequences xs and ys must be finite.
339 Since 4.14
342 Constructing sequences
347 The functions in this section are lazy: that is, they return sequences
348 whose elements are computed only when demanded.
349 val empty : 'a t
351 empty is the empty sequence. It has no elements. Its length is 0.
354 val return : 'a -> 'a t
358 return x is the sequence whose sole element is x . Its length is 1.
361 val cons : 'a -> 'a t -> 'a t
365 cons x xs is the sequence that begins with the element x , followed
368 with the sequence xs .
369 Writing cons (f()) xs causes the function call f() to take place imme‐
371 diately. For this call to be delayed until the sequence is queried, one
372 must instead write (fun () -> Cons(f(), xs)) .
373 Since 4.11
376 val init : int -> (int -> 'a) -> 'a t
380 init n f is the sequence f 0; f 1; ...; f (n-1) .
383 n must be nonnegative.
386 If desired, the infinite sequence f 0; f 1; ... can be defined as map
388 f (ints 0) .
389 Since 4.14
392 Raises Invalid_argument if n is negative.
395 val unfold : ('b -> ('a * 'b) option) -> 'b -> 'a t
399 unfold constructs a sequence out of a step function and an initial
402 state.
403 If f u is None then unfold f u is the empty sequence. If f u is Some
405 (x, u') then unfold f u is the nonempty sequence cons x (unfold f u') .
406 For example, unfold (function [] -> None | h :: t -> Some (h, t)) l is
408 equivalent to List.to_seq l .
409 Since 4.11
412 val repeat : 'a -> 'a t
416 repeat x is the infinite sequence where the element x is repeated in‐
419 definitely.
420 repeat x is equivalent to cycle (return x) .
423 Since 4.14
426 val forever : (unit -> 'a) -> 'a t
430 forever f is an infinite sequence where every element is produced (on
433 demand) by the function call f() .
434 For instance, forever Random.bool is an infinite sequence of random
436 bits.
437 forever f is equivalent to map f (repeat ()) .
440 Since 4.14
443 val cycle : 'a t -> 'a t
447 cycle xs is the infinite sequence that consists of an infinite number
450 of repetitions of the sequence xs .
451 If xs is an empty sequence, then cycle xs is empty as well.
453 Consuming (a prefix of) the sequence cycle xs once can cause the se‐
455 quence xs to be consumed more than once. Therefore, xs must be persis‐
456 tent.
457 Since 4.14
460 val iterate : ('a -> 'a) -> 'a -> 'a t
464 iterate f x is the infinite sequence whose elements are x , f x , f (f
467 x) , and so on.
468 In other words, it is the orbit of the function f , starting at x .
470 Since 4.14
473 Transforming sequences
478 The functions in this section are lazy: that is, they return sequences
479 whose elements are computed only when demanded.
480 val map : ('a -> 'b) -> 'a t -> 'b t
482 map f xs is the image of the sequence xs through the transformation f .
485 If xs is the sequence x0; x1; ... then map f xs is the sequence f x0;
487 f x1; ... .
488 val mapi : (int -> 'a -> 'b) -> 'a t -> 'b t
492 mapi is analogous to map , but applies the function f to an index and
495 an element.
496 mapi f xs is equivalent to map2 f (ints 0) xs .
499 Since 4.14
502 val filter : ('a -> bool) -> 'a t -> 'a t
506 filter p xs is the sequence of the elements x of xs that satisfy p x .
509 In other words, filter p xs is the sequence xs , deprived of the ele‐
511 ments x such that p x is false.
512 val filter_map : ('a -> 'b option) -> 'a t -> 'b t
516 filter_map f xs is the sequence of the elements y such that f x = Some
519 y , where x ranges over xs .
520 filter_map f xs is equivalent to map Option.get (filter Option.is_some
523 (map f xs)) .
524 val scan : ('b -> 'a -> 'b) -> 'b -> 'a t -> 'b t
528 If xs is a sequence [x0; x1; x2; ...] , then scan f a0 xs is a se‐
530 quence of accumulators [a0; a1; a2; ...] where a1 is f a0 x0 , a2 is f
531 a1 x1 , and so on.
532 Thus, scan f a0 xs is conceptually related to fold_left f a0 xs . How‐
534 ever, instead of performing an eager iteration and immediately return‐
535 ing the final accumulator, it returns a sequence of accumulators.
536 For instance, scan (+) 0 transforms a sequence of integers into the se‐
538 quence of its partial sums.
539 If xs has length n then scan f a0 xs has length n+1 .
541 Since 4.14
544 val take : int -> 'a t -> 'a t
548 take n xs is the sequence of the first n elements of xs .
551 If xs has fewer than n elements, then take n xs is equivalent to xs .
553 n must be nonnegative.
556 Since 4.14
559 Raises Invalid_argument if n is negative.
562 val drop : int -> 'a t -> 'a t
566 drop n xs is the sequence xs , deprived of its first n elements.
569 If xs has fewer than n elements, then drop n xs is empty.
571 n must be nonnegative.
574 drop is lazy: the first n+1 elements of the sequence xs are demanded
577 only when the first element of drop n xs is demanded. For this reason,
578 drop 1 xs is not equivalent to tail xs , which queries xs immediately.
579 Since 4.14
582 Raises Invalid_argument if n is negative.
585 val take_while : ('a -> bool) -> 'a t -> 'a t
589 take_while p xs is the longest prefix of the sequence xs where every
592 element x satisfies p x .
593 Since 4.14
596 val drop_while : ('a -> bool) -> 'a t -> 'a t
600 drop_while p xs is the sequence xs , deprived of the prefix take_while
603 p xs .
604 Since 4.14
607 val group : ('a -> 'a -> bool) -> 'a t -> 'a t t
611 Provided the function eq defines an equality on elements, group eq xs
613 is the sequence of the maximal runs of adjacent duplicate elements of
614 the sequence xs .
615 Every element of group eq xs is a nonempty sequence of equal elements.
617 The concatenation concat (group eq xs) is equal to xs .
619 Consuming group eq xs , and consuming the sequences that it contains,
621 can cause xs to be consumed more than once. Therefore, xs must be per‐
622 sistent.
623 Since 4.14
626 val memoize : 'a t -> 'a t
630 The sequence memoize xs has the same elements as the sequence xs .
632 Regardless of whether xs is ephemeral or persistent, memoize xs is per‐
634 sistent: even if it is queried several times, xs is queried at most
635 once.
636 The construction of the sequence memoize xs internally relies on sus‐
638 pensions provided by the module Lazy . These suspensions are not
639 thread-safe. Therefore, the sequence memoize xs must not be queried by
640 multiple threads concurrently.
641 Since 4.14
644 exception Forced_twice
648 This exception is raised when a sequence returned by Seq.once (or a
651 suffix of it) is queried more than once.
652 Since 4.14
655 val once : 'a t -> 'a t
659 The sequence once xs has the same elements as the sequence xs .
661 Regardless of whether xs is ephemeral or persistent, once xs is an
663 ephemeral sequence: it can be queried at most once. If it (or a suffix
664 of it) is queried more than once, then the exception Forced_twice is
665 raised. This can be useful, while debugging or testing, to ensure that
666 a sequence is consumed at most once.
667 Since 4.14
670 Raises Forced_twice if once xs , or a suffix of it, is queried more
673 than once.
674 val transpose : 'a t t -> 'a t t
678 If xss is a matrix (a sequence of rows), then transpose xss is the se‐
680 quence of the columns of the matrix xss .
681 The rows of the matrix xss are not required to have the same length.
683 The matrix xss is not required to be finite (in either direction).
685 The matrix xss must be persistent.
687 Since 4.14
690 Combining sequences
695 val append : 'a t -> 'a t -> 'a t
696 append xs ys is the concatenation of the sequences xs and ys .
699 Its elements are the elements of xs , followed by the elements of ys .
701 Since 4.11
704 val concat : 'a t t -> 'a t
708 If xss is a sequence of sequences, then concat xss is its concatena‐
710 tion.
711 If xss is the sequence xs0; xs1; ... then concat xss is the sequence
713 xs0 @ xs1 @ ... .
714 Since 4.13
717 val flat_map : ('a -> 'b t) -> 'a t -> 'b t
721 flat_map f xs is equivalent to concat (map f xs) .
724 val concat_map : ('a -> 'b t) -> 'a t -> 'b t
728 concat_map f xs is equivalent to concat (map f xs) .
731 concat_map is an alias for flat_map .
734 Since 4.13
737 val zip : 'a t -> 'b t -> ('a * 'b) t
741 zip xs ys is the sequence of pairs (x, y) drawn synchronously from the
744 sequences xs and ys .
745 If the sequences xs and ys have different lengths, then the sequence
747 ends as soon as one sequence is exhausted; the excess elements in the
748 other sequence are ignored.
749 zip xs ys is equivalent to map2 (fun a b -> (a, b)) xs ys .
752 Since 4.14
755 val map2 : ('a -> 'b -> 'c) -> 'a t -> 'b t -> 'c t
759 map2 f xs ys is the sequence of the elements f x y , where the pairs
762 (x, y) are drawn synchronously from the sequences xs and ys .
763 If the sequences xs and ys have different lengths, then the sequence
765 ends as soon as one sequence is exhausted; the excess elements in the
766 other sequence are ignored.
767 map2 f xs ys is equivalent to map (fun (x, y) -> f x y) (zip xs ys) .
770 Since 4.14
773 val interleave : 'a t -> 'a t -> 'a t
777 interleave xs ys is the sequence that begins with the first element of
780 xs , continues with the first element of ys , and so on.
781 When one of the sequences xs and ys is exhausted, interleave xs ys con‐
783 tinues with the rest of the other sequence.
784 Since 4.14
787 val sorted_merge : ('a -> 'a -> int) -> 'a t -> 'a t -> 'a t
791 If the sequences xs and ys are sorted according to the total preorder
793 cmp , then sorted_merge cmp xs ys is the sorted sequence obtained by
794 merging the sequences xs and ys .
795 For more details on comparison functions, see Array.sort .
797 Since 4.14
800 val product : 'a t -> 'b t -> ('a * 'b) t
804 product xs ys is the Cartesian product of the sequences xs and ys .
807 For every element x of xs and for every element y of ys , the pair (x,
809 y) appears once as an element of product xs ys .
810 The order in which the pairs appear is unspecified.
812 The sequences xs and ys are not required to be finite.
814 The sequences xs and ys must be persistent.
816 Since 4.14
819 val map_product : ('a -> 'b -> 'c) -> 'a t -> 'b t -> 'c t
823 The sequence map_product f xs ys is the image through f of the Carte‐
825 sian product of the sequences xs and ys .
826 For every element x of xs and for every element y of ys , the element f
828 x y appears once as an element of map_product f xs ys .
829 The order in which these elements appear is unspecified.
831 The sequences xs and ys are not required to be finite.
833 The sequences xs and ys must be persistent.
835 map_product f xs ys is equivalent to map (fun (x, y) -> f x y) (product
838 xs ys) .
839 Since 4.14
842 Splitting a sequence into two sequences
847 val unzip : ('a * 'b) t -> 'a t * 'b t
848 unzip transforms a sequence of pairs into a pair of sequences.
851 unzip xs is equivalent to (map fst xs, map snd xs) .
854 Querying either of the sequences returned by unzip xs causes xs to be
856 queried. Therefore, querying both of them causes xs to be queried
857 twice. Thus, xs must be persistent and cheap. If that is not the
858 case, use unzip (memoize xs) .
859 Since 4.14
862 val split : ('a * 'b) t -> 'a t * 'b t
866 split is an alias for unzip .
869 Since 4.14
872 val partition_map : ('a -> ('b, 'c) Either.t) -> 'a t -> 'b t * 'c t
876 partition_map f xs returns a pair of sequences (ys, zs) , where:
879 - ys is the sequence of the elements y such that f x = Left y , where x
882 ranges over xs ;
883 - zs is the sequence of the elements z such that f x = Right z , where
886 x ranges over xs .
887 partition_map f xs is equivalent to a pair of filter_map Ei‐
889 ther.find_left (map f xs) and filter_map Either.find_right (map f xs) .
890 Querying either of the sequences returned by partition_map f xs causes
892 xs to be queried. Therefore, querying both of them causes xs to be
893 queried twice. Thus, xs must be persistent and cheap. If that is not
894 the case, use partition_map f (memoize xs) .
895 Since 4.14
898 val partition : ('a -> bool) -> 'a t -> 'a t * 'a t
902 partition p xs returns a pair of the subsequence of the elements of xs
905 that satisfy p and the subsequence of the elements of xs that do not
906 satisfy p .
907 partition p xs is equivalent to filter p xs, filter (fun x -> not (p
910 x)) xs .
911 Consuming both of the sequences returned by partition p xs causes xs to
913 be consumed twice and causes the function f to be applied twice to each
914 element of the list. Therefore, f should be pure and cheap. Further‐
915 more, xs should be persistent and cheap. If that is not the case, use
916 partition p (memoize xs) .
917 Since 4.14
920 Converting between sequences and dispensers
925 A dispenser is a representation of a sequence as a function of type
926 unit -> 'a option . Every time this function is invoked, it returns the
927 next element of the sequence. When there are no more elements, it re‐
928 turns None . A dispenser has mutable internal state, therefore is
929 ephemeral: the sequence that it represents can be consumed at most
930 once.
931 val of_dispenser : (unit -> 'a option) -> 'a t
933 of_dispenser it is the sequence of the elements produced by the dis‐
936 penser it . It is an ephemeral sequence: it can be consumed at most
937 once. If a persistent sequence is needed, use memoize (of_dispenser it)
938 .
939 Since 4.14
942 val to_dispenser : 'a t -> unit -> 'a option
946 to_dispenser xs is a fresh dispenser on the sequence xs .
949 This dispenser has mutable internal state, which is not protected by a
951 lock; so, it must not be used by several threads concurrently.
952 Since 4.14
955 Sequences of integers
960 val ints : int -> int t
961 ints i is the infinite sequence of the integers beginning at i and
964 counting up.
965 Since 4.14
968OCamldoc 2022-07-22 Stdlib.Seq(3)