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 (x, ys) where x is the head
93 of the sequence and ys its tail.
94 Since 4.14
97 val length : 'a t -> int
101 length xs is the length of the sequence xs .
104 The sequence xs must be finite.
106 Since 4.14
109 val iter : ('a -> unit) -> 'a t -> unit
113 iter f xs invokes f x successively for every element x of the sequence
116 xs , from left to right.
117 It terminates only if the sequence xs is finite.
119 val fold_left : ('a -> 'b -> 'a) -> 'a -> 'b t -> 'a
123 fold_left f _ xs invokes f _ x successively for every element x of the
126 sequence xs , from left to right.
127 An accumulator of type 'a is threaded through the calls to f .
129 It terminates only if the sequence xs is finite.
131 val iteri : (int -> 'a -> unit) -> 'a t -> unit
135 iteri f xs invokes f i x successively for every element x located at
138 index i in the sequence xs .
139 It terminates only if the sequence xs is finite.
141 iteri f xs is equivalent to iter (fun (i, x) -> f i x) (zip (ints 0)
144 xs) .
145 Since 4.14
148 val fold_lefti : ('b -> int -> 'a -> 'b) -> 'b -> 'a t -> 'b
152 fold_lefti f _ xs invokes f _ i x successively for every element x lo‐
155 cated at index i of the sequence xs .
156 An accumulator of type 'b is threaded through the calls to f .
158 It terminates only if the sequence xs is finite.
160 fold_lefti f accu xs is equivalent to fold_left (fun accu (i, x) -> f
163 accu i x) accu (zip (ints 0) xs) .
164 Since 4.14
167 val for_all : ('a -> bool) -> 'a t -> bool
171 for_all p xs determines whether all elements x of the sequence xs sat‐
174 isfy p x .
175 The sequence xs must be finite.
177 Since 4.14
180 val exists : ('a -> bool) -> 'a t -> bool
184 exists xs p determines whether at least one element x of the sequence
187 xs satisfies p x .
188 The sequence xs must be finite.
190 Since 4.14
193 val find : ('a -> bool) -> 'a t -> 'a option
197 find p xs returns Some x , where x is the first element of the sequence
200 xs that satisfies p x , if there is such an element.
201 It returns None if there is no such element.
203 The sequence xs must be finite.
205 Since 4.14
208 val find_map : ('a -> 'b option) -> 'a t -> 'b option
212 find_map f xs returns Some y , where x is the first element of the se‐
215 quence xs such that f x = Some _ , if there is such an element, and
216 where y is defined by f x = Some y .
217 It returns None if there is no such element.
219 The sequence xs must be finite.
221 Since 4.14
224 val iter2 : ('a -> 'b -> unit) -> 'a t -> 'b t -> unit
228 iter2 f xs ys invokes f x y successively for every pair (x, y) of ele‐
231 ments drawn synchronously from the sequences xs and ys .
232 If the sequences xs and ys have different lengths, then iteration stops
234 as soon as one sequence is exhausted; the excess elements in the other
235 sequence are ignored.
236 Iteration terminates only if at least one of the sequences xs and ys is
238 finite.
239 iter2 f xs ys is equivalent to iter (fun (x, y) -> f x y) (zip xs ys) .
242 Since 4.14
245 val fold_left2 : ('a -> 'b -> 'c -> 'a) -> 'a -> 'b t -> 'c t -> 'a
249 fold_left2 f _ xs ys invokes f _ x y successively for every pair (x, y)
252 of elements drawn synchronously from the sequences xs and ys .
253 An accumulator of type 'a is threaded through the calls to f .
255 If the sequences xs and ys have different lengths, then iteration stops
257 as soon as one sequence is exhausted; the excess elements in the other
258 sequence are ignored.
259 Iteration terminates only if at least one of the sequences xs and ys is
261 finite.
262 fold_left2 f accu xs ys is equivalent to fold_left (fun accu (x, y) ->
265 f accu x y) (zip xs ys) .
266 Since 4.14
269 val for_all2 : ('a -> 'b -> bool) -> 'a t -> 'b t -> bool
273 for_all2 p xs ys determines whether all pairs (x, y) of elements drawn
276 synchronously from the sequences xs and ys satisfy p x y .
277 If the sequences xs and ys have different lengths, then iteration stops
279 as soon as one sequence is exhausted; the excess elements in the other
280 sequence are ignored. In particular, if xs or ys is empty, then
281 for_all2 p xs ys is true. This is where for_all2 and equal differ:
282 equal eq xs ys can be true only if xs and ys have the same length.
283 At least one of the sequences xs and ys must be finite.
285 for_all2 p xs ys is equivalent to for_all (fun b -> b) (map2 p xs ys) .
288 Since 4.14
291 val exists2 : ('a -> 'b -> bool) -> 'a t -> 'b t -> bool
295 exists2 p xs ys determines whether some pair (x, y) of elements drawn
298 synchronously from the sequences xs and ys satisfies p x y .
299 If the sequences xs and ys have different lengths, then iteration must
301 stop as soon as one sequence is exhausted; the excess elements in the
302 other sequence are ignored.
303 At least one of the sequences xs and ys must be finite.
305 exists2 p xs ys is equivalent to exists (fun b -> b) (map2 p xs ys) .
308 Since 4.14
311 val equal : ('a -> 'b -> bool) -> 'a t -> 'b t -> bool
315 Provided the function eq defines an equality on elements, equal eq xs
317 ys determines whether the sequences xs and ys are pointwise equal.
318 At least one of the sequences xs and ys must be finite.
320 Since 4.14
323 val compare : ('a -> 'b -> int) -> 'a t -> 'b t -> int
327 Provided the function cmp defines a preorder on elements, compare cmp
329 xs ys compares the sequences xs and ys according to the lexicographic
330 preorder.
331 For more details on comparison functions, see Array.sort .
333 At least one of the sequences xs and ys must be finite.
335 Since 4.14
338 Constructing sequences
343 The functions in this section are lazy: that is, they return sequences
344 whose elements are computed only when demanded.
345 val empty : 'a t
347 empty is the empty sequence. It has no elements. Its length is 0.
350 val return : 'a -> 'a t
354 return x is the sequence whose sole element is x . Its length is 1.
357 val cons : 'a -> 'a t -> 'a t
361 cons x xs is the sequence that begins with the element x , followed
364 with the sequence xs .
365 Writing cons (f()) xs causes the function call f() to take place imme‐
367 diately. For this call to be delayed until the sequence is queried, one
368 must instead write (fun () -> Cons(f(), xs)) .
369 Since 4.11
372 val init : int -> (int -> 'a) -> 'a t
376 init n f is the sequence f 0; f 1; ...; f (n-1) .
379 n must be nonnegative.
382 If desired, the infinite sequence f 0; f 1; ... can be defined as map
384 f (ints 0) .
385 Since 4.14
388 Raises Invalid_argument if n is negative.
391 val unfold : ('b -> ('a * 'b) option) -> 'b -> 'a t
395 unfold constructs a sequence out of a step function and an initial
398 state.
399 If f u is None then unfold f u is the empty sequence. If f u is Some
401 (x, u') then unfold f u is the nonempty sequence cons x (unfold f u') .
402 For example, unfold (function [] -> None | h :: t -> Some (h, t)) l is
404 equivalent to List.to_seq l .
405 Since 4.11
408 val repeat : 'a -> 'a t
412 repeat x is the infinite sequence where the element x is repeated in‐
415 definitely.
416 repeat x is equivalent to cycle (return x) .
419 Since 4.14
422 val forever : (unit -> 'a) -> 'a t
426 forever f is an infinite sequence where every element is produced (on
429 demand) by the function call f() .
430 For instance, forever Random.bool is an infinite sequence of random
432 bits.
433 forever f is equivalent to map f (repeat ()) .
436 Since 4.14
439 val cycle : 'a t -> 'a t
443 cycle xs is the infinite sequence that consists of an infinite number
446 of repetitions of the sequence xs .
447 If xs is an empty sequence, then cycle xs is empty as well.
449 Consuming (a prefix of) the sequence cycle xs once can cause the se‐
451 quence xs to be consumed more than once. Therefore, xs must be persis‐
452 tent.
453 Since 4.14
456 val iterate : ('a -> 'a) -> 'a -> 'a t
460 iterate f x is the infinite sequence whose elements are x , f x , f (f
463 x) , and so on.
464 In other words, it is the orbit of the function f , starting at x .
466 Since 4.14
469 Transforming sequences
474 The functions in this section are lazy: that is, they return sequences
475 whose elements are computed only when demanded.
476 val map : ('a -> 'b) -> 'a t -> 'b t
478 map f xs is the image of the sequence xs through the transformation f .
481 If xs is the sequence x0; x1; ... then map f xs is the sequence f x0;
483 f x1; ... .
484 val mapi : (int -> 'a -> 'b) -> 'a t -> 'b t
488 mapi is analogous to map , but applies the function f to an index and
491 an element.
492 mapi f xs is equivalent to map2 f (ints 0) xs .
495 Since 4.14
498 val filter : ('a -> bool) -> 'a t -> 'a t
502 filter p xs is the sequence of the elements x of xs that satisfy p x .
505 In other words, filter p xs is the sequence xs , deprived of the ele‐
507 ments x such that p x is false.
508 val filter_map : ('a -> 'b option) -> 'a t -> 'b t
512 filter_map f xs is the sequence of the elements y such that f x = Some
515 y , where x ranges over xs .
516 filter_map f xs is equivalent to map Option.get (filter Option.is_some
519 (map f xs)) .
520 val scan : ('b -> 'a -> 'b) -> 'b -> 'a t -> 'b t
524 If xs is a sequence [x0; x1; x2; ...] , then scan f a0 xs is a se‐
526 quence of accumulators [a0; a1; a2; ...] where a1 is f a0 x0 , a2 is f
527 a1 x1 , and so on.
528 Thus, scan f a0 xs is conceptually related to fold_left f a0 xs . How‐
530 ever, instead of performing an eager iteration and immediately return‐
531 ing the final accumulator, it returns a sequence of accumulators.
532 For instance, scan (+) 0 transforms a sequence of integers into the se‐
534 quence of its partial sums.
535 If xs has length n then scan f a0 xs has length n+1 .
537 Since 4.14
540 val take : int -> 'a t -> 'a t
544 take n xs is the sequence of the first n elements of xs .
547 If xs has fewer than n elements, then take n xs is equivalent to xs .
549 n must be nonnegative.
552 Since 4.14
555 Raises Invalid_argument if n is negative.
558 val drop : int -> 'a t -> 'a t
562 drop n xs is the sequence xs , deprived of its first n elements.
565 If xs has fewer than n elements, then drop n xs is empty.
567 n must be nonnegative.
570 drop is lazy: the first n+1 elements of the sequence xs are demanded
573 only when the first element of drop n xs is demanded. For this reason,
574 drop 1 xs is not equivalent to tail xs , which queries xs immediately.
575 Since 4.14
578 Raises Invalid_argument if n is negative.
581 val take_while : ('a -> bool) -> 'a t -> 'a t
585 take_while p xs is the longest prefix of the sequence xs where every
588 element x satisfies p x .
589 Since 4.14
592 val drop_while : ('a -> bool) -> 'a t -> 'a t
596 drop_while p xs is the sequence xs , deprived of the prefix take_while
599 p xs .
600 Since 4.14
603 val group : ('a -> 'a -> bool) -> 'a t -> 'a t t
607 Provided the function eq defines an equality on elements, group eq xs
609 is the sequence of the maximal runs of adjacent duplicate elements of
610 the sequence xs .
611 Every element of group eq xs is a nonempty sequence of equal elements.
613 The concatenation concat (group eq xs) is equal to xs .
615 Consuming group eq xs , and consuming the sequences that it contains,
617 can cause xs to be consumed more than once. Therefore, xs must be per‐
618 sistent.
619 Since 4.14
622 val memoize : 'a t -> 'a t
626 The sequence memoize xs has the same elements as the sequence xs .
628 Regardless of whether xs is ephemeral or persistent, memoize xs is per‐
630 sistent: even if it is queried several times, xs is queried at most
631 once.
632 The construction of the sequence memoize xs internally relies on sus‐
634 pensions provided by the module Lazy . These suspensions are not
635 thread-safe. Therefore, the sequence memoize xs must not be queried by
636 multiple threads concurrently.
637 Since 4.14
640 exception Forced_twice
644 This exception is raised when a sequence returned by Seq.once (or a
647 suffix of it) is queried more than once.
648 Since 4.14
651 val once : 'a t -> 'a t
655 The sequence once xs has the same elements as the sequence xs .
657 Regardless of whether xs is ephemeral or persistent, once xs is an
659 ephemeral sequence: it can be queried at most once. If it (or a suffix
660 of it) is queried more than once, then the exception Forced_twice is
661 raised. This can be useful, while debugging or testing, to ensure that
662 a sequence is consumed at most once.
663 Since 4.14
666 Raises Forced_twice if once xs , or a suffix of it, is queried more
669 than once.
670 val transpose : 'a t t -> 'a t t
674 If xss is a matrix (a sequence of rows), then transpose xss is the se‐
676 quence of the columns of the matrix xss .
677 The rows of the matrix xss are not required to have the same length.
679 The matrix xss is not required to be finite (in either direction).
681 The matrix xss must be persistent.
683 Since 4.14
686 Combining sequences
691 val append : 'a t -> 'a t -> 'a t
692 append xs ys is the concatenation of the sequences xs and ys .
695 Its elements are the elements of xs , followed by the elements of ys .
697 Since 4.11
700 val concat : 'a t t -> 'a t
704 If xss is a sequence of sequences, then concat xss is its concatena‐
706 tion.
707 If xss is the sequence xs0; xs1; ... then concat xss is the sequence
709 xs0 @ xs1 @ ... .
710 Since 4.13
713 val flat_map : ('a -> 'b t) -> 'a t -> 'b t
717 flat_map f xs is equivalent to concat (map f xs) .
720 val concat_map : ('a -> 'b t) -> 'a t -> 'b t
724 concat_map f xs is equivalent to concat (map f xs) .
727 concat_map is an alias for flat_map .
730 Since 4.13
733 val zip : 'a t -> 'b t -> ('a * 'b) t
737 zip xs ys is the sequence of pairs (x, y) drawn synchronously from the
740 sequences xs and ys .
741 If the sequences xs and ys have different lengths, then the sequence
743 ends as soon as one sequence is exhausted; the excess elements in the
744 other sequence are ignored.
745 zip xs ys is equivalent to map2 (fun a b -> (a, b)) xs ys .
748 Since 4.14
751 val map2 : ('a -> 'b -> 'c) -> 'a t -> 'b t -> 'c t
755 map2 f xs ys is the sequence of the elements f x y , where the pairs
758 (x, y) are drawn synchronously from the sequences xs and ys .
759 If the sequences xs and ys have different lengths, then the sequence
761 ends as soon as one sequence is exhausted; the excess elements in the
762 other sequence are ignored.
763 map2 f xs ys is equivalent to map (fun (x, y) -> f x y) (zip xs ys) .
766 Since 4.14
769 val interleave : 'a t -> 'a t -> 'a t
773 interleave xs ys is the sequence that begins with the first element of
776 xs , continues with the first element of ys , and so on.
777 When one of the sequences xs and ys is exhausted, interleave xs ys con‐
779 tinues with the rest of the other sequence.
780 Since 4.14
783 val sorted_merge : ('a -> 'a -> int) -> 'a t -> 'a t -> 'a t
787 If the sequences xs and ys are sorted according to the total preorder
789 cmp , then sorted_merge cmp xs ys is the sorted sequence obtained by
790 merging the sequences xs and ys .
791 For more details on comparison functions, see Array.sort .
793 Since 4.14
796 val product : 'a t -> 'b t -> ('a * 'b) t
800 product xs ys is the Cartesian product of the sequences xs and ys .
803 For every element x of xs and for every element y of ys , the pair (x,
805 y) appears once as an element of product xs ys .
806 The order in which the pairs appear is unspecified.
808 The sequences xs and ys are not required to be finite.
810 The sequences xs and ys must be persistent.
812 Since 4.14
815 val map_product : ('a -> 'b -> 'c) -> 'a t -> 'b t -> 'c t
819 The sequence map_product f xs ys is the image through f of the Carte‐
821 sian product of the sequences xs and ys .
822 For every element x of xs and for every element y of ys , the element f
824 x y appears once as an element of map_product f xs ys .
825 The order in which these elements appear is unspecified.
827 The sequences xs and ys are not required to be finite.
829 The sequences xs and ys must be persistent.
831 map_product f xs ys is equivalent to map (fun (x, y) -> f x y) (product
834 xs ys) .
835 Since 4.14
838 Splitting a sequence into two sequences
843 val unzip : ('a * 'b) t -> 'a t * 'b t
844 unzip transforms a sequence of pairs into a pair of sequences.
847 unzip xs is equivalent to (map fst xs, map snd xs) .
850 Querying either of the sequences returned by unzip xs causes xs to be
852 queried. Therefore, querying both of them causes xs to be queried
853 twice. Thus, xs must be persistent and cheap. If that is not the
854 case, use unzip (memoize xs) .
855 Since 4.14
858 val split : ('a * 'b) t -> 'a t * 'b t
862 split is an alias for unzip .
865 Since 4.14
868 val partition_map : ('a -> ('b, 'c) Either.t) -> 'a t -> 'b t * 'c t
872 partition_map f xs returns a pair of sequences (ys, zs) , where:
875 - ys is the sequence of the elements y such that f x = Left y , where x
878 ranges over xs ;
879 - zs is the sequence of the elements z such that f x = Right z , where
882 x ranges over xs .
883 partition_map f xs is equivalent to a pair of filter_map Ei‐
885 ther.find_left (map f xs) and filter_map Either.find_right (map f xs) .
886 Querying either of the sequences returned by partition_map f xs causes
888 xs to be queried. Therefore, querying both of them causes xs to be
889 queried twice. Thus, xs must be persistent and cheap. If that is not
890 the case, use partition_map f (memoize xs) .
891 Since 4.14
894 val partition : ('a -> bool) -> 'a t -> 'a t * 'a t
898 partition p xs returns a pair of the subsequence of the elements of xs
901 that satisfy p and the subsequence of the elements of xs that do not
902 satisfy p .
903 partition p xs is equivalent to filter p xs, filter (fun x -> not (p
906 x)) xs .
907 Consuming both of the sequences returned by partition p xs causes xs to
909 be consumed twice and causes the function f to be applied twice to each
910 element of the list. Therefore, f should be pure and cheap. Further‐
911 more, xs should be persistent and cheap. If that is not the case, use
912 partition p (memoize xs) .
913 Since 4.14
916 Converting between sequences and dispensers
921 A dispenser is a representation of a sequence as a function of type
922 unit -> 'a option . Every time this function is invoked, it returns the
923 next element of the sequence. When there are no more elements, it re‐
924 turns None . A dispenser has mutable internal state, therefore is
925 ephemeral: the sequence that it represents can be consumed at most
926 once.
927 val of_dispenser : (unit -> 'a option) -> 'a t
929 of_dispenser it is the sequence of the elements produced by the dis‐
932 penser it . It is an ephemeral sequence: it can be consumed at most
933 once. If a persistent sequence is needed, use memoize (of_dispenser it)
934 .
935 Since 4.14
938 val to_dispenser : 'a t -> unit -> 'a option
942 to_dispenser xs is a fresh dispenser on the sequence xs .
945 This dispenser has mutable internal state, which is not protected by a
947 lock; so, it must not be used by several threads concurrently.
948 Since 4.14
951 Sequences of integers
956 val ints : int -> int t
957 ints i is the infinite sequence of the integers beginning at i and
960 counting up.
961 Since 4.14
964OCamldoc 2023-07-20 Stdlib.Seq(3)