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 (x, ys) where x is the head
93 of the sequence and ys its tail.
94
95
96 Since 4.14
97
98
99
100 val length : 'a t -> int
101
102
103 length xs is the length of the sequence xs .
104
105 The sequence xs must be finite.
106
107
108 Since 4.14
109
110
111
112 val iter : ('a -> unit) -> 'a t -> unit
113
114
115 iter f xs invokes f x successively for every element x of the sequence
116 xs , from left to right.
117
118 It terminates only if the sequence xs is finite.
119
120
121
122 val fold_left : ('a -> 'b -> 'a) -> 'a -> 'b t -> 'a
123
124
125 fold_left f _ xs invokes f _ x successively for every element x of the
126 sequence xs , from left to right.
127
128 An accumulator of type 'a is threaded through the calls to f .
129
130 It terminates only if the sequence xs is finite.
131
132
133
134 val iteri : (int -> 'a -> unit) -> 'a t -> unit
135
136
137 iteri f xs invokes f i x successively for every element x located at
138 index i in the sequence xs .
139
140 It terminates only if the sequence xs is finite.
141
142
143 iteri f xs is equivalent to iter (fun (i, x) -> f i x) (zip (ints 0)
144 xs) .
145
146
147 Since 4.14
148
149
150
151 val fold_lefti : ('b -> int -> 'a -> 'b) -> 'b -> 'a t -> 'b
152
153
154 fold_lefti f _ xs invokes f _ i x successively for every element x lo‐
155 cated at index i of the sequence xs .
156
157 An accumulator of type 'b is threaded through the calls to f .
158
159 It terminates only if the sequence xs is finite.
160
161
162 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
165
166 Since 4.14
167
168
169
170 val for_all : ('a -> bool) -> 'a t -> bool
171
172
173 for_all p xs determines whether all elements x of the sequence xs sat‐
174 isfy p x .
175
176 The sequence xs must be finite.
177
178
179 Since 4.14
180
181
182
183 val exists : ('a -> bool) -> 'a t -> bool
184
185
186 exists xs p determines whether at least one element x of the sequence
187 xs satisfies p x .
188
189 The sequence xs must be finite.
190
191
192 Since 4.14
193
194
195
196 val find : ('a -> bool) -> 'a t -> 'a option
197
198
199 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
202 It returns None if there is no such element.
203
204 The sequence xs must be finite.
205
206
207 Since 4.14
208
209
210
211 val find_map : ('a -> 'b option) -> 'a t -> 'b option
212
213
214 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
218 It returns None if there is no such element.
219
220 The sequence xs must be finite.
221
222
223 Since 4.14
224
225
226
227 val iter2 : ('a -> 'b -> unit) -> 'a t -> 'b t -> unit
228
229
230 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
233 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
237 Iteration terminates only if at least one of the sequences xs and ys is
238 finite.
239
240
241 iter2 f xs ys is equivalent to iter (fun (x, y) -> f x y) (zip xs ys) .
242
243
244 Since 4.14
245
246
247
248 val fold_left2 : ('a -> 'b -> 'c -> 'a) -> 'a -> 'b t -> 'c t -> 'a
249
250
251 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
254 An accumulator of type 'a is threaded through the calls to f .
255
256 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
260 Iteration terminates only if at least one of the sequences xs and ys is
261 finite.
262
263
264 fold_left2 f accu xs ys is equivalent to fold_left (fun accu (x, y) ->
265 f accu x y) (zip xs ys) .
266
267
268 Since 4.14
269
270
271
272 val for_all2 : ('a -> 'b -> bool) -> 'a t -> 'b t -> bool
273
274
275 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
278 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
284 At least one of the sequences xs and ys must be finite.
285
286
287 for_all2 p xs ys is equivalent to for_all (fun b -> b) (map2 p xs ys) .
288
289
290 Since 4.14
291
292
293
294 val exists2 : ('a -> 'b -> bool) -> 'a t -> 'b t -> bool
295
296
297 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
300 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
304 At least one of the sequences xs and ys must be finite.
305
306
307 exists2 p xs ys is equivalent to exists (fun b -> b) (map2 p xs ys) .
308
309
310 Since 4.14
311
312
313
314 val equal : ('a -> 'b -> bool) -> 'a t -> 'b t -> bool
315
316 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
319 At least one of the sequences xs and ys must be finite.
320
321
322 Since 4.14
323
324
325
326 val compare : ('a -> 'b -> int) -> 'a t -> 'b t -> int
327
328 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
332 For more details on comparison functions, see Array.sort .
333
334 At least one of the sequences xs and ys must be finite.
335
336
337 Since 4.14
338
339
340
341
342 Constructing sequences
343 The functions in this section are lazy: that is, they return sequences
344 whose elements are computed only when demanded.
345
346 val empty : 'a t
347
348
349 empty is the empty sequence. It has no elements. Its length is 0.
350
351
352
353 val return : 'a -> 'a t
354
355
356 return x is the sequence whose sole element is x . Its length is 1.
357
358
359
360 val cons : 'a -> 'a t -> 'a t
361
362
363 cons x xs is the sequence that begins with the element x , followed
364 with the sequence xs .
365
366 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
370
371 Since 4.11
372
373
374
375 val init : int -> (int -> 'a) -> 'a t
376
377
378 init n f is the sequence f 0; f 1; ...; f (n-1) .
379
380
381 n must be nonnegative.
382
383 If desired, the infinite sequence f 0; f 1; ... can be defined as map
384 f (ints 0) .
385
386
387 Since 4.14
388
389
390 Raises Invalid_argument if n is negative.
391
392
393
394 val unfold : ('b -> ('a * 'b) option) -> 'b -> 'a t
395
396
397 unfold constructs a sequence out of a step function and an initial
398 state.
399
400 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
403 For example, unfold (function [] -> None | h :: t -> Some (h, t)) l is
404 equivalent to List.to_seq l .
405
406
407 Since 4.11
408
409
410
411 val repeat : 'a -> 'a t
412
413
414 repeat x is the infinite sequence where the element x is repeated in‐
415 definitely.
416
417
418 repeat x is equivalent to cycle (return x) .
419
420
421 Since 4.14
422
423
424
425 val forever : (unit -> 'a) -> 'a t
426
427
428 forever f is an infinite sequence where every element is produced (on
429 demand) by the function call f() .
430
431 For instance, forever Random.bool is an infinite sequence of random
432 bits.
433
434
435 forever f is equivalent to map f (repeat ()) .
436
437
438 Since 4.14
439
440
441
442 val cycle : 'a t -> 'a t
443
444
445 cycle xs is the infinite sequence that consists of an infinite number
446 of repetitions of the sequence xs .
447
448 If xs is an empty sequence, then cycle xs is empty as well.
449
450 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
454
455 Since 4.14
456
457
458
459 val iterate : ('a -> 'a) -> 'a -> 'a t
460
461
462 iterate f x is the infinite sequence whose elements are x , f x , f (f
463 x) , and so on.
464
465 In other words, it is the orbit of the function f , starting at x .
466
467
468 Since 4.14
469
470
471
472
473 Transforming sequences
474 The functions in this section are lazy: that is, they return sequences
475 whose elements are computed only when demanded.
476
477 val map : ('a -> 'b) -> 'a t -> 'b t
478
479
480 map f xs is the image of the sequence xs through the transformation f .
481
482 If xs is the sequence x0; x1; ... then map f xs is the sequence f x0;
483 f x1; ... .
484
485
486
487 val mapi : (int -> 'a -> 'b) -> 'a t -> 'b t
488
489
490 mapi is analogous to map , but applies the function f to an index and
491 an element.
492
493
494 mapi f xs is equivalent to map2 f (ints 0) xs .
495
496
497 Since 4.14
498
499
500
501 val filter : ('a -> bool) -> 'a t -> 'a t
502
503
504 filter p xs is the sequence of the elements x of xs that satisfy p x .
505
506 In other words, filter p xs is the sequence xs , deprived of the ele‐
507 ments x such that p x is false.
508
509
510
511 val filter_map : ('a -> 'b option) -> 'a t -> 'b t
512
513
514 filter_map f xs is the sequence of the elements y such that f x = Some
515 y , where x ranges over xs .
516
517
518 filter_map f xs is equivalent to map Option.get (filter Option.is_some
519 (map f xs)) .
520
521
522
523 val scan : ('b -> 'a -> 'b) -> 'b -> 'a t -> 'b t
524
525 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
529 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
533 For instance, scan (+) 0 transforms a sequence of integers into the se‐
534 quence of its partial sums.
535
536 If xs has length n then scan f a0 xs has length n+1 .
537
538
539 Since 4.14
540
541
542
543 val take : int -> 'a t -> 'a t
544
545
546 take n xs is the sequence of the first n elements of xs .
547
548 If xs has fewer than n elements, then take n xs is equivalent to xs .
549
550
551 n must be nonnegative.
552
553
554 Since 4.14
555
556
557 Raises Invalid_argument if n is negative.
558
559
560
561 val drop : int -> 'a t -> 'a t
562
563
564 drop n xs is the sequence xs , deprived of its first n elements.
565
566 If xs has fewer than n elements, then drop n xs is empty.
567
568
569 n must be nonnegative.
570
571
572 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
576
577 Since 4.14
578
579
580 Raises Invalid_argument if n is negative.
581
582
583
584 val take_while : ('a -> bool) -> 'a t -> 'a t
585
586
587 take_while p xs is the longest prefix of the sequence xs where every
588 element x satisfies p x .
589
590
591 Since 4.14
592
593
594
595 val drop_while : ('a -> bool) -> 'a t -> 'a t
596
597
598 drop_while p xs is the sequence xs , deprived of the prefix take_while
599 p xs .
600
601
602 Since 4.14
603
604
605
606 val group : ('a -> 'a -> bool) -> 'a t -> 'a t t
607
608 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
612 Every element of group eq xs is a nonempty sequence of equal elements.
613
614 The concatenation concat (group eq xs) is equal to xs .
615
616 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
620
621 Since 4.14
622
623
624
625 val memoize : 'a t -> 'a t
626
627 The sequence memoize xs has the same elements as the sequence xs .
628
629 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
633 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
638
639 Since 4.14
640
641
642
643 exception Forced_twice
644
645
646 This exception is raised when a sequence returned by Seq.once (or a
647 suffix of it) is queried more than once.
648
649
650 Since 4.14
651
652
653
654 val once : 'a t -> 'a t
655
656 The sequence once xs has the same elements as the sequence xs .
657
658 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
664
665 Since 4.14
666
667
668 Raises Forced_twice if once xs , or a suffix of it, is queried more
669 than once.
670
671
672
673 val transpose : 'a t t -> 'a t t
674
675 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
678 The rows of the matrix xss are not required to have the same length.
679
680 The matrix xss is not required to be finite (in either direction).
681
682 The matrix xss must be persistent.
683
684
685 Since 4.14
686
687
688
689
690 Combining sequences
691 val append : 'a t -> 'a t -> 'a t
692
693
694 append xs ys is the concatenation of the sequences xs and ys .
695
696 Its elements are the elements of xs , followed by the elements of ys .
697
698
699 Since 4.11
700
701
702
703 val concat : 'a t t -> 'a t
704
705 If xss is a sequence of sequences, then concat xss is its concatena‐
706 tion.
707
708 If xss is the sequence xs0; xs1; ... then concat xss is the sequence
709 xs0 @ xs1 @ ... .
710
711
712 Since 4.13
713
714
715
716 val flat_map : ('a -> 'b t) -> 'a t -> 'b t
717
718
719 flat_map f xs is equivalent to concat (map f xs) .
720
721
722
723 val concat_map : ('a -> 'b t) -> 'a t -> 'b t
724
725
726 concat_map f xs is equivalent to concat (map f xs) .
727
728
729 concat_map is an alias for flat_map .
730
731
732 Since 4.13
733
734
735
736 val zip : 'a t -> 'b t -> ('a * 'b) t
737
738
739 zip xs ys is the sequence of pairs (x, y) drawn synchronously from the
740 sequences xs and ys .
741
742 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
746
747 zip xs ys is equivalent to map2 (fun a b -> (a, b)) xs ys .
748
749
750 Since 4.14
751
752
753
754 val map2 : ('a -> 'b -> 'c) -> 'a t -> 'b t -> 'c t
755
756
757 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
760 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
764
765 map2 f xs ys is equivalent to map (fun (x, y) -> f x y) (zip xs ys) .
766
767
768 Since 4.14
769
770
771
772 val interleave : 'a t -> 'a t -> 'a t
773
774
775 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
778 When one of the sequences xs and ys is exhausted, interleave xs ys con‐
779 tinues with the rest of the other sequence.
780
781
782 Since 4.14
783
784
785
786 val sorted_merge : ('a -> 'a -> int) -> 'a t -> 'a t -> 'a t
787
788 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
792 For more details on comparison functions, see Array.sort .
793
794
795 Since 4.14
796
797
798
799 val product : 'a t -> 'b t -> ('a * 'b) t
800
801
802 product xs ys is the Cartesian product of the sequences xs and ys .
803
804 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
807 The order in which the pairs appear is unspecified.
808
809 The sequences xs and ys are not required to be finite.
810
811 The sequences xs and ys must be persistent.
812
813
814 Since 4.14
815
816
817
818 val map_product : ('a -> 'b -> 'c) -> 'a t -> 'b t -> 'c t
819
820 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
823 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
826 The order in which these elements appear is unspecified.
827
828 The sequences xs and ys are not required to be finite.
829
830 The sequences xs and ys must be persistent.
831
832
833 map_product f xs ys is equivalent to map (fun (x, y) -> f x y) (product
834 xs ys) .
835
836
837 Since 4.14
838
839
840
841
842 Splitting a sequence into two sequences
843 val unzip : ('a * 'b) t -> 'a t * 'b t
844
845
846 unzip transforms a sequence of pairs into a pair of sequences.
847
848
849 unzip xs is equivalent to (map fst xs, map snd xs) .
850
851 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
856
857 Since 4.14
858
859
860
861 val split : ('a * 'b) t -> 'a t * 'b t
862
863
864 split is an alias for unzip .
865
866
867 Since 4.14
868
869
870
871 val partition_map : ('a -> ('b, 'c) Either.t) -> 'a t -> 'b t * 'c t
872
873
874 partition_map f xs returns a pair of sequences (ys, zs) , where:
875
876
877 - ys is the sequence of the elements y such that f x = Left y , where x
878 ranges over xs ;
879
880
881 - zs is the sequence of the elements z such that f x = Right z , where
882 x ranges over xs .
883
884 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
887 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
892
893 Since 4.14
894
895
896
897 val partition : ('a -> bool) -> 'a t -> 'a t * 'a t
898
899
900 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
904
905 partition p xs is equivalent to filter p xs, filter (fun x -> not (p
906 x)) xs .
907
908 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
914
915 Since 4.14
916
917
918
919
920 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
928 val of_dispenser : (unit -> 'a option) -> 'a t
929
930
931 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
936
937 Since 4.14
938
939
940
941 val to_dispenser : 'a t -> unit -> 'a option
942
943
944 to_dispenser xs is a fresh dispenser on the sequence xs .
945
946 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
949
950 Since 4.14
951
952
953
954
955 Sequences of integers
956 val ints : int -> int t
957
958
959 ints i is the infinite sequence of the integers beginning at i and
960 counting up.
961
962
963 Since 4.14
964
965
966
967
968
969OCamldoc 2023-07-20 Stdlib.Seq(3)