1Stdlib.Seq(3) OCaml library Stdlib.Seq(3)
2
3
4
6 Stdlib.Seq - no description
7
9 Module Stdlib.Seq
10
12 Module Seq
13 : (module Stdlib__Seq)
14
15
16
17
18
19
20
21 type 'a t = unit -> 'a node
22
23
24 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
30
31 type 'a node =
32 | Nil
33 | Cons of 'a * 'a t
34
35
36 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
40
41
42
43 Consuming sequences
44 The functions in this section consume their argument, a sequence, ei‐
45 ther partially or completely:
46
47 - 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
50 - iter , fold_left , length , etc., consume the sequence all the way to
51 its end. They terminate only if the sequence is finite.
52
53 - for_all , exists , find , etc. consume the sequence down to a certain
54 depth, which is a priori unpredictable.
55
56 Similarly, among the functions that consume two sequences, one can dis‐
57 tinguish two groups:
58
59 - iter2 and fold_left2 consume both sequences all the way to the end,
60 provided the sequences have the same length.
61
62 - for_all2 , exists2 , equal , compare consume the sequences down to a
63 certain depth, which is a priori unpredictable.
64
65 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
70 None of the functions in this section is lazy. These functions are con‐
71 sumers: they force some computation to take place.
72
73 val is_empty : 'a t -> bool
74
75
76 is_empty xs determines whether the sequence xs is empty.
77
78 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
83
84 Since 4.14
85
86
87
88 val uncons : 'a t -> ('a * 'a t) option
89
90 If xs is empty, then uncons xs is None .
91
92 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
95 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
99
100 Since 4.14
101
102
103
104 val length : 'a t -> int
105
106
107 length xs is the length of the sequence xs .
108
109 The sequence xs must be finite.
110
111
112 Since 4.14
113
114
115
116 val iter : ('a -> unit) -> 'a t -> unit
117
118
119 iter f xs invokes f x successively for every element x of the sequence
120 xs , from left to right.
121
122 It terminates only if the sequence xs is finite.
123
124
125
126 val fold_left : ('a -> 'b -> 'a) -> 'a -> 'b t -> 'a
127
128
129 fold_left f _ xs invokes f _ x successively for every element x of the
130 sequence xs , from left to right.
131
132 An accumulator of type 'a is threaded through the calls to f .
133
134 It terminates only if the sequence xs is finite.
135
136
137
138 val iteri : (int -> 'a -> unit) -> 'a t -> unit
139
140
141 iteri f xs invokes f i x successively for every element x located at
142 index i in the sequence xs .
143
144 It terminates only if the sequence xs is finite.
145
146
147 iteri f xs is equivalent to iter (fun (i, x) -> f i x) (zip (ints 0)
148 xs) .
149
150
151 Since 4.14
152
153
154
155 val fold_lefti : ('b -> int -> 'a -> 'b) -> 'b -> 'a t -> 'b
156
157
158 fold_lefti f _ xs invokes f _ i x successively for every element x lo‐
159 cated at index i of the sequence xs .
160
161 An accumulator of type 'b is threaded through the calls to f .
162
163 It terminates only if the sequence xs is finite.
164
165
166 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
169
170 Since 4.14
171
172
173
174 val for_all : ('a -> bool) -> 'a t -> bool
175
176
177 for_all p xs determines whether all elements x of the sequence xs sat‐
178 isfy p x .
179
180 The sequence xs must be finite.
181
182
183 Since 4.14
184
185
186
187 val exists : ('a -> bool) -> 'a t -> bool
188
189
190 exists xs p determines whether at least one element x of the sequence
191 xs satisfies p x .
192
193 The sequence xs must be finite.
194
195
196 Since 4.14
197
198
199
200 val find : ('a -> bool) -> 'a t -> 'a option
201
202
203 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
206 It returns None if there is no such element.
207
208 The sequence xs must be finite.
209
210
211 Since 4.14
212
213
214
215 val find_map : ('a -> 'b option) -> 'a t -> 'b option
216
217
218 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
222 It returns None if there is no such element.
223
224 The sequence xs must be finite.
225
226
227 Since 4.14
228
229
230
231 val iter2 : ('a -> 'b -> unit) -> 'a t -> 'b t -> unit
232
233
234 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
237 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
241 Iteration terminates only if at least one of the sequences xs and ys is
242 finite.
243
244
245 iter2 f xs ys is equivalent to iter (fun (x, y) -> f x y) (zip xs ys) .
246
247
248 Since 4.14
249
250
251
252 val fold_left2 : ('a -> 'b -> 'c -> 'a) -> 'a -> 'b t -> 'c t -> 'a
253
254
255 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
258 An accumulator of type 'a is threaded through the calls to f .
259
260 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
264 Iteration terminates only if at least one of the sequences xs and ys is
265 finite.
266
267
268 fold_left2 f accu xs ys is equivalent to fold_left (fun accu (x, y) ->
269 f accu x y) (zip xs ys) .
270
271
272 Since 4.14
273
274
275
276 val for_all2 : ('a -> 'b -> bool) -> 'a t -> 'b t -> bool
277
278
279 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
282 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
288 At least one of the sequences xs and ys must be finite.
289
290
291 for_all2 p xs ys is equivalent to for_all (fun b -> b) (map2 p xs ys) .
292
293
294 Since 4.14
295
296
297
298 val exists2 : ('a -> 'b -> bool) -> 'a t -> 'b t -> bool
299
300
301 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
304 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
308 At least one of the sequences xs and ys must be finite.
309
310
311 exists2 p xs ys is equivalent to exists (fun b -> b) (map2 p xs ys) .
312
313
314 Since 4.14
315
316
317
318 val equal : ('a -> 'b -> bool) -> 'a t -> 'b t -> bool
319
320 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
323 At least one of the sequences xs and ys must be finite.
324
325
326 Since 4.14
327
328
329
330 val compare : ('a -> 'b -> int) -> 'a t -> 'b t -> int
331
332 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
336 For more details on comparison functions, see Array.sort .
337
338 At least one of the sequences xs and ys must be finite.
339
340
341 Since 4.14
342
343
344
345
346 Constructing sequences
347 The functions in this section are lazy: that is, they return sequences
348 whose elements are computed only when demanded.
349
350 val empty : 'a t
351
352
353 empty is the empty sequence. It has no elements. Its length is 0.
354
355
356
357 val return : 'a -> 'a t
358
359
360 return x is the sequence whose sole element is x . Its length is 1.
361
362
363
364 val cons : 'a -> 'a t -> 'a t
365
366
367 cons x xs is the sequence that begins with the element x , followed
368 with the sequence xs .
369
370 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
374
375 Since 4.11
376
377
378
379 val init : int -> (int -> 'a) -> 'a t
380
381
382 init n f is the sequence f 0; f 1; ...; f (n-1) .
383
384
385 n must be nonnegative.
386
387 If desired, the infinite sequence f 0; f 1; ... can be defined as map
388 f (ints 0) .
389
390
391 Since 4.14
392
393
394 Raises Invalid_argument if n is negative.
395
396
397
398 val unfold : ('b -> ('a * 'b) option) -> 'b -> 'a t
399
400
401 unfold constructs a sequence out of a step function and an initial
402 state.
403
404 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
407 For example, unfold (function [] -> None | h :: t -> Some (h, t)) l is
408 equivalent to List.to_seq l .
409
410
411 Since 4.11
412
413
414
415 val repeat : 'a -> 'a t
416
417
418 repeat x is the infinite sequence where the element x is repeated in‐
419 definitely.
420
421
422 repeat x is equivalent to cycle (return x) .
423
424
425 Since 4.14
426
427
428
429 val forever : (unit -> 'a) -> 'a t
430
431
432 forever f is an infinite sequence where every element is produced (on
433 demand) by the function call f() .
434
435 For instance, forever Random.bool is an infinite sequence of random
436 bits.
437
438
439 forever f is equivalent to map f (repeat ()) .
440
441
442 Since 4.14
443
444
445
446 val cycle : 'a t -> 'a t
447
448
449 cycle xs is the infinite sequence that consists of an infinite number
450 of repetitions of the sequence xs .
451
452 If xs is an empty sequence, then cycle xs is empty as well.
453
454 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
458
459 Since 4.14
460
461
462
463 val iterate : ('a -> 'a) -> 'a -> 'a t
464
465
466 iterate f x is the infinite sequence whose elements are x , f x , f (f
467 x) , and so on.
468
469 In other words, it is the orbit of the function f , starting at x .
470
471
472 Since 4.14
473
474
475
476
477 Transforming sequences
478 The functions in this section are lazy: that is, they return sequences
479 whose elements are computed only when demanded.
480
481 val map : ('a -> 'b) -> 'a t -> 'b t
482
483
484 map f xs is the image of the sequence xs through the transformation f .
485
486 If xs is the sequence x0; x1; ... then map f xs is the sequence f x0;
487 f x1; ... .
488
489
490
491 val mapi : (int -> 'a -> 'b) -> 'a t -> 'b t
492
493
494 mapi is analogous to map , but applies the function f to an index and
495 an element.
496
497
498 mapi f xs is equivalent to map2 f (ints 0) xs .
499
500
501 Since 4.14
502
503
504
505 val filter : ('a -> bool) -> 'a t -> 'a t
506
507
508 filter p xs is the sequence of the elements x of xs that satisfy p x .
509
510 In other words, filter p xs is the sequence xs , deprived of the ele‐
511 ments x such that p x is false.
512
513
514
515 val filter_map : ('a -> 'b option) -> 'a t -> 'b t
516
517
518 filter_map f xs is the sequence of the elements y such that f x = Some
519 y , where x ranges over xs .
520
521
522 filter_map f xs is equivalent to map Option.get (filter Option.is_some
523 (map f xs)) .
524
525
526
527 val scan : ('b -> 'a -> 'b) -> 'b -> 'a t -> 'b t
528
529 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
533 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
537 For instance, scan (+) 0 transforms a sequence of integers into the se‐
538 quence of its partial sums.
539
540 If xs has length n then scan f a0 xs has length n+1 .
541
542
543 Since 4.14
544
545
546
547 val take : int -> 'a t -> 'a t
548
549
550 take n xs is the sequence of the first n elements of xs .
551
552 If xs has fewer than n elements, then take n xs is equivalent to xs .
553
554
555 n must be nonnegative.
556
557
558 Since 4.14
559
560
561 Raises Invalid_argument if n is negative.
562
563
564
565 val drop : int -> 'a t -> 'a t
566
567
568 drop n xs is the sequence xs , deprived of its first n elements.
569
570 If xs has fewer than n elements, then drop n xs is empty.
571
572
573 n must be nonnegative.
574
575
576 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
580
581 Since 4.14
582
583
584 Raises Invalid_argument if n is negative.
585
586
587
588 val take_while : ('a -> bool) -> 'a t -> 'a t
589
590
591 take_while p xs is the longest prefix of the sequence xs where every
592 element x satisfies p x .
593
594
595 Since 4.14
596
597
598
599 val drop_while : ('a -> bool) -> 'a t -> 'a t
600
601
602 drop_while p xs is the sequence xs , deprived of the prefix take_while
603 p xs .
604
605
606 Since 4.14
607
608
609
610 val group : ('a -> 'a -> bool) -> 'a t -> 'a t t
611
612 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
616 Every element of group eq xs is a nonempty sequence of equal elements.
617
618 The concatenation concat (group eq xs) is equal to xs .
619
620 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
624
625 Since 4.14
626
627
628
629 val memoize : 'a t -> 'a t
630
631 The sequence memoize xs has the same elements as the sequence xs .
632
633 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
637 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
642
643 Since 4.14
644
645
646
647 exception Forced_twice
648
649
650 This exception is raised when a sequence returned by Seq.once (or a
651 suffix of it) is queried more than once.
652
653
654 Since 4.14
655
656
657
658 val once : 'a t -> 'a t
659
660 The sequence once xs has the same elements as the sequence xs .
661
662 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
668
669 Since 4.14
670
671
672 Raises Forced_twice if once xs , or a suffix of it, is queried more
673 than once.
674
675
676
677 val transpose : 'a t t -> 'a t t
678
679 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
682 The rows of the matrix xss are not required to have the same length.
683
684 The matrix xss is not required to be finite (in either direction).
685
686 The matrix xss must be persistent.
687
688
689 Since 4.14
690
691
692
693
694 Combining sequences
695 val append : 'a t -> 'a t -> 'a t
696
697
698 append xs ys is the concatenation of the sequences xs and ys .
699
700 Its elements are the elements of xs , followed by the elements of ys .
701
702
703 Since 4.11
704
705
706
707 val concat : 'a t t -> 'a t
708
709 If xss is a sequence of sequences, then concat xss is its concatena‐
710 tion.
711
712 If xss is the sequence xs0; xs1; ... then concat xss is the sequence
713 xs0 @ xs1 @ ... .
714
715
716 Since 4.13
717
718
719
720 val flat_map : ('a -> 'b t) -> 'a t -> 'b t
721
722
723 flat_map f xs is equivalent to concat (map f xs) .
724
725
726
727 val concat_map : ('a -> 'b t) -> 'a t -> 'b t
728
729
730 concat_map f xs is equivalent to concat (map f xs) .
731
732
733 concat_map is an alias for flat_map .
734
735
736 Since 4.13
737
738
739
740 val zip : 'a t -> 'b t -> ('a * 'b) t
741
742
743 zip xs ys is the sequence of pairs (x, y) drawn synchronously from the
744 sequences xs and ys .
745
746 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
750
751 zip xs ys is equivalent to map2 (fun a b -> (a, b)) xs ys .
752
753
754 Since 4.14
755
756
757
758 val map2 : ('a -> 'b -> 'c) -> 'a t -> 'b t -> 'c t
759
760
761 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
764 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
768
769 map2 f xs ys is equivalent to map (fun (x, y) -> f x y) (zip xs ys) .
770
771
772 Since 4.14
773
774
775
776 val interleave : 'a t -> 'a t -> 'a t
777
778
779 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
782 When one of the sequences xs and ys is exhausted, interleave xs ys con‐
783 tinues with the rest of the other sequence.
784
785
786 Since 4.14
787
788
789
790 val sorted_merge : ('a -> 'a -> int) -> 'a t -> 'a t -> 'a t
791
792 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
796 For more details on comparison functions, see Array.sort .
797
798
799 Since 4.14
800
801
802
803 val product : 'a t -> 'b t -> ('a * 'b) t
804
805
806 product xs ys is the Cartesian product of the sequences xs and ys .
807
808 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
811 The order in which the pairs appear is unspecified.
812
813 The sequences xs and ys are not required to be finite.
814
815 The sequences xs and ys must be persistent.
816
817
818 Since 4.14
819
820
821
822 val map_product : ('a -> 'b -> 'c) -> 'a t -> 'b t -> 'c t
823
824 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
827 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
830 The order in which these elements appear is unspecified.
831
832 The sequences xs and ys are not required to be finite.
833
834 The sequences xs and ys must be persistent.
835
836
837 map_product f xs ys is equivalent to map (fun (x, y) -> f x y) (product
838 xs ys) .
839
840
841 Since 4.14
842
843
844
845
846 Splitting a sequence into two sequences
847 val unzip : ('a * 'b) t -> 'a t * 'b t
848
849
850 unzip transforms a sequence of pairs into a pair of sequences.
851
852
853 unzip xs is equivalent to (map fst xs, map snd xs) .
854
855 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
860
861 Since 4.14
862
863
864
865 val split : ('a * 'b) t -> 'a t * 'b t
866
867
868 split is an alias for unzip .
869
870
871 Since 4.14
872
873
874
875 val partition_map : ('a -> ('b, 'c) Either.t) -> 'a t -> 'b t * 'c t
876
877
878 partition_map f xs returns a pair of sequences (ys, zs) , where:
879
880
881 - ys is the sequence of the elements y such that f x = Left y , where x
882 ranges over xs ;
883
884
885 - zs is the sequence of the elements z such that f x = Right z , where
886 x ranges over xs .
887
888 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
891 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
896
897 Since 4.14
898
899
900
901 val partition : ('a -> bool) -> 'a t -> 'a t * 'a t
902
903
904 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
908
909 partition p xs is equivalent to filter p xs, filter (fun x -> not (p
910 x)) xs .
911
912 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
918
919 Since 4.14
920
921
922
923
924 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
932 val of_dispenser : (unit -> 'a option) -> 'a t
933
934
935 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
940
941 Since 4.14
942
943
944
945 val to_dispenser : 'a t -> unit -> 'a option
946
947
948 to_dispenser xs is a fresh dispenser on the sequence xs .
949
950 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
953
954 Since 4.14
955
956
957
958
959 Sequences of integers
960 val ints : int -> int t
961
962
963 ints i is the infinite sequence of the integers beginning at i and
964 counting up.
965
966
967 Since 4.14
968
969
970
971
972
973OCamldoc 2022-07-22 Stdlib.Seq(3)