1Seq(3) OCaml library Seq(3)
2
3
4
6 Seq - Sequences.
7
9 Module Seq
10
12 Module Seq
13 : sig end
14
15
16 Sequences.
17
18 A sequence of type 'a Seq.t can be thought of as a delayed list, that
19 is, a list whose elements are computed only when they are demanded by a
20 consumer. This allows sequences to be produced and transformed lazily
21 (one element at a time) rather than eagerly (all elements at once).
22 This also allows constructing conceptually infinite sequences.
23
24 The type 'a Seq.t is defined as a synonym for unit -> 'a Seq.node .
25 This is a function type: therefore, it is opaque. The consumer can
26 query a sequence in order to request the next element (if there is
27 one), but cannot otherwise inspect the sequence in any way.
28
29 Because it is opaque, the type 'a Seq.t does not reveal whether a se‐
30 quence is:
31
32 -persistent, which means that the sequence can be used as many times as
33 desired, producing the same elements every time, just like an immutable
34 list; or
35
36 -ephemeral, which means that the sequence is not persistent. Querying
37 an ephemeral sequence might have an observable side effect, such as in‐
38 crementing a mutable counter. As a common special case, an ephemeral
39 sequence can be affine, which means that it must be queried at most
40 once.
41
42 It also does not reveal whether the elements of the sequence are:
43
44
45 -pre-computed and stored in memory, which means that querying the se‐
46 quence is cheap;
47
48 -computed when first demanded and then stored in memory, which means
49 that querying the sequence once can be expensive, but querying the same
50 sequence again is cheap; or
51
52 -re-computed every time they are demanded, which may or may not be
53 cheap.
54
55 It is up to the programmer to keep these distinctions in mind so as to
56 understand the time and space requirements of sequences.
57
58 For the sake of simplicity, most of the documentation that follows is
59 written under the implicit assumption that the sequences at hand are
60 persistent. We normally do not point out when or how many times each
61 function is invoked, because that would be too verbose. For instance,
62 in the description of map , we write: "if xs is the sequence x0; x1;
63 ... then map f xs is the sequence f x0; f x1; ... ". If we wished to
64 be more explicit, we could point out that the transformation takes
65 place on demand: that is, the elements of map f xs are computed only
66 when they are demanded. In other words, the definition let ys = map f
67 xs terminates immediately and does not invoke f . The function call f
68 x0 takes place only when the first element of ys is demanded, via the
69 function call ys() . Furthermore, calling ys() twice causes f x0 to be
70 called twice as well. If one wishes for f to be applied at most once to
71 each element of xs , even in scenarios where ys is queried more than
72 once, then one should use let ys = memoize (map f xs) .
73
74 As a general rule, the functions that build sequences, such as map ,
75 filter , scan , take , etc., produce sequences whose elements are com‐
76 puted only on demand. The functions that eagerly consume sequences,
77 such as is_empty , find , length , iter , fold_left , etc., are the
78 functions that force computation to take place.
79
80 When possible, we recommend using sequences rather than dispensers
81 (functions of type unit -> 'a option that produce elements upon de‐
82 mand). Whereas sequences can be persistent or ephemeral, dispensers are
83 always ephemeral, and are typically more difficult to work with than
84 sequences. Two conversion functions, Seq.to_dispenser and Seq.of_dis‐
85 penser , are provided.
86
87
88 Since 4.07
89
90
91
92
93
94 type 'a t = unit -> 'a node
95
96
97 A sequence xs of type 'a t is a delayed list of elements of type 'a .
98 Such a sequence is queried by performing a function application xs() .
99 This function application returns a node, allowing the caller to deter‐
100 mine whether the sequence is empty or nonempty, and in the latter case,
101 to obtain its head and tail.
102
103
104 type 'a node =
105 | Nil
106 | Cons of 'a * 'a t
107
108
109 A node is either Nil , which means that the sequence is empty, or Cons
110 (x, xs) , which means that x is the first element of the sequence and
111 that xs is the remainder of the sequence.
112
113
114
115
116 Consuming sequences
117 The functions in this section consume their argument, a sequence, ei‐
118 ther partially or completely:
119
120 - is_empty and uncons consume the sequence down to depth 1. That is,
121 they demand the first argument of the sequence, if there is one.
122
123 - iter , fold_left , length , etc., consume the sequence all the way to
124 its end. They terminate only if the sequence is finite.
125
126 - for_all , exists , find , etc. consume the sequence down to a certain
127 depth, which is a priori unpredictable.
128
129 Similarly, among the functions that consume two sequences, one can dis‐
130 tinguish two groups:
131
132 - iter2 and fold_left2 consume both sequences all the way to the end,
133 provided the sequences have the same length.
134
135 - for_all2 , exists2 , equal , compare consume the sequences down to a
136 certain depth, which is a priori unpredictable.
137
138 The functions that consume two sequences can be applied to two se‐
139 quences of distinct lengths: in that case, the excess elements in the
140 longer sequence are ignored. (It may be the case that one excess ele‐
141 ment is demanded, even though this element is not used.)
142
143 None of the functions in this section is lazy. These functions are con‐
144 sumers: they force some computation to take place.
145
146 val is_empty : 'a t -> bool
147
148
149 is_empty xs determines whether the sequence xs is empty.
150
151 It is recommended that the sequence xs be persistent. Indeed, is_empty
152 xs demands the head of the sequence xs , so, if xs is ephemeral, it may
153 be the case that xs cannot be used any more after this call has taken
154 place.
155
156
157 Since 4.14
158
159
160
161 val uncons : 'a t -> ('a * 'a t) option
162
163 If xs is empty, then uncons xs is None .
164
165 If xs is nonempty, then uncons xs is Some (head xs, tail xs) , that is,
166 a pair of the head and tail of the sequence xs .
167
168 This equivalence holds if xs is persistent. If xs is ephemeral, then
169 uncons must be preferred over separate calls to head and tail , which
170 would cause xs to be queried twice.
171
172
173 Since 4.14
174
175
176
177 val length : 'a t -> int
178
179
180 length xs is the length of the sequence xs .
181
182 The sequence xs must be finite.
183
184
185 Since 4.14
186
187
188
189 val iter : ('a -> unit) -> 'a t -> unit
190
191
192 iter f xs invokes f x successively for every element x of the sequence
193 xs , from left to right.
194
195 It terminates only if the sequence xs is finite.
196
197
198
199 val fold_left : ('a -> 'b -> 'a) -> 'a -> 'b t -> 'a
200
201
202 fold_left f _ xs invokes f _ x successively for every element x of the
203 sequence xs , from left to right.
204
205 An accumulator of type 'a is threaded through the calls to f .
206
207 It terminates only if the sequence xs is finite.
208
209
210
211 val iteri : (int -> 'a -> unit) -> 'a t -> unit
212
213
214 iteri f xs invokes f i x successively for every element x located at
215 index i in the sequence xs .
216
217 It terminates only if the sequence xs is finite.
218
219
220 iteri f xs is equivalent to iter (fun (i, x) -> f i x) (zip (ints 0)
221 xs) .
222
223
224 Since 4.14
225
226
227
228 val fold_lefti : ('b -> int -> 'a -> 'b) -> 'b -> 'a t -> 'b
229
230
231 fold_lefti f _ xs invokes f _ i x successively for every element x lo‐
232 cated at index i of the sequence xs .
233
234 An accumulator of type 'b is threaded through the calls to f .
235
236 It terminates only if the sequence xs is finite.
237
238
239 fold_lefti f accu xs is equivalent to fold_left (fun accu (i, x) -> f
240 accu i x) accu (zip (ints 0) xs) .
241
242
243 Since 4.14
244
245
246
247 val for_all : ('a -> bool) -> 'a t -> bool
248
249
250 for_all p xs determines whether all elements x of the sequence xs sat‐
251 isfy p x .
252
253 The sequence xs must be finite.
254
255
256 Since 4.14
257
258
259
260 val exists : ('a -> bool) -> 'a t -> bool
261
262
263 exists xs p determines whether at least one element x of the sequence
264 xs satisfies p x .
265
266 The sequence xs must be finite.
267
268
269 Since 4.14
270
271
272
273 val find : ('a -> bool) -> 'a t -> 'a option
274
275
276 find p xs returns Some x , where x is the first element of the sequence
277 xs that satisfies p x , if there is such an element.
278
279 It returns None if there is no such element.
280
281 The sequence xs must be finite.
282
283
284 Since 4.14
285
286
287
288 val find_map : ('a -> 'b option) -> 'a t -> 'b option
289
290
291 find_map f xs returns Some y , where x is the first element of the se‐
292 quence xs such that f x = Some _ , if there is such an element, and
293 where y is defined by f x = Some y .
294
295 It returns None if there is no such element.
296
297 The sequence xs must be finite.
298
299
300 Since 4.14
301
302
303
304 val iter2 : ('a -> 'b -> unit) -> 'a t -> 'b t -> unit
305
306
307 iter2 f xs ys invokes f x y successively for every pair (x, y) of ele‐
308 ments drawn synchronously from the sequences xs and ys .
309
310 If the sequences xs and ys have different lengths, then iteration stops
311 as soon as one sequence is exhausted; the excess elements in the other
312 sequence are ignored.
313
314 Iteration terminates only if at least one of the sequences xs and ys is
315 finite.
316
317
318 iter2 f xs ys is equivalent to iter (fun (x, y) -> f x y) (zip xs ys) .
319
320
321 Since 4.14
322
323
324
325 val fold_left2 : ('a -> 'b -> 'c -> 'a) -> 'a -> 'b t -> 'c t -> 'a
326
327
328 fold_left2 f _ xs ys invokes f _ x y successively for every pair (x, y)
329 of elements drawn synchronously from the sequences xs and ys .
330
331 An accumulator of type 'a is threaded through the calls to f .
332
333 If the sequences xs and ys have different lengths, then iteration stops
334 as soon as one sequence is exhausted; the excess elements in the other
335 sequence are ignored.
336
337 Iteration terminates only if at least one of the sequences xs and ys is
338 finite.
339
340
341 fold_left2 f accu xs ys is equivalent to fold_left (fun accu (x, y) ->
342 f accu x y) (zip xs ys) .
343
344
345 Since 4.14
346
347
348
349 val for_all2 : ('a -> 'b -> bool) -> 'a t -> 'b t -> bool
350
351
352 for_all2 p xs ys determines whether all pairs (x, y) of elements drawn
353 synchronously from the sequences xs and ys satisfy p x y .
354
355 If the sequences xs and ys have different lengths, then iteration stops
356 as soon as one sequence is exhausted; the excess elements in the other
357 sequence are ignored. In particular, if xs or ys is empty, then
358 for_all2 p xs ys is true. This is where for_all2 and equal differ:
359 equal eq xs ys can be true only if xs and ys have the same length.
360
361 At least one of the sequences xs and ys must be finite.
362
363
364 for_all2 p xs ys is equivalent to for_all (fun b -> b) (map2 p xs ys) .
365
366
367 Since 4.14
368
369
370
371 val exists2 : ('a -> 'b -> bool) -> 'a t -> 'b t -> bool
372
373
374 exists2 p xs ys determines whether some pair (x, y) of elements drawn
375 synchronously from the sequences xs and ys satisfies p x y .
376
377 If the sequences xs and ys have different lengths, then iteration must
378 stop as soon as one sequence is exhausted; the excess elements in the
379 other sequence are ignored.
380
381 At least one of the sequences xs and ys must be finite.
382
383
384 exists2 p xs ys is equivalent to exists (fun b -> b) (map2 p xs ys) .
385
386
387 Since 4.14
388
389
390
391 val equal : ('a -> 'b -> bool) -> 'a t -> 'b t -> bool
392
393 Provided the function eq defines an equality on elements, equal eq xs
394 ys determines whether the sequences xs and ys are pointwise equal.
395
396 At least one of the sequences xs and ys must be finite.
397
398
399 Since 4.14
400
401
402
403 val compare : ('a -> 'b -> int) -> 'a t -> 'b t -> int
404
405 Provided the function cmp defines a preorder on elements, compare cmp
406 xs ys compares the sequences xs and ys according to the lexicographic
407 preorder.
408
409 For more details on comparison functions, see Array.sort .
410
411 At least one of the sequences xs and ys must be finite.
412
413
414 Since 4.14
415
416
417
418
419 Constructing sequences
420 The functions in this section are lazy: that is, they return sequences
421 whose elements are computed only when demanded.
422
423 val empty : 'a t
424
425
426 empty is the empty sequence. It has no elements. Its length is 0.
427
428
429
430 val return : 'a -> 'a t
431
432
433 return x is the sequence whose sole element is x . Its length is 1.
434
435
436
437 val cons : 'a -> 'a t -> 'a t
438
439
440 cons x xs is the sequence that begins with the element x , followed
441 with the sequence xs .
442
443 Writing cons (f()) xs causes the function call f() to take place imme‐
444 diately. For this call to be delayed until the sequence is queried, one
445 must instead write (fun () -> Cons(f(), xs)) .
446
447
448 Since 4.11
449
450
451
452 val init : int -> (int -> 'a) -> 'a t
453
454
455 init n f is the sequence f 0; f 1; ...; f (n-1) .
456
457
458 n must be nonnegative.
459
460 If desired, the infinite sequence f 0; f 1; ... can be defined as map
461 f (ints 0) .
462
463
464 Since 4.14
465
466
467 Raises Invalid_argument if n is negative.
468
469
470
471 val unfold : ('b -> ('a * 'b) option) -> 'b -> 'a t
472
473
474 unfold constructs a sequence out of a step function and an initial
475 state.
476
477 If f u is None then unfold f u is the empty sequence. If f u is Some
478 (x, u') then unfold f u is the nonempty sequence cons x (unfold f u') .
479
480 For example, unfold (function [] -> None | h :: t -> Some (h, t)) l is
481 equivalent to List.to_seq l .
482
483
484 Since 4.11
485
486
487
488 val repeat : 'a -> 'a t
489
490
491 repeat x is the infinite sequence where the element x is repeated in‐
492 definitely.
493
494
495 repeat x is equivalent to cycle (return x) .
496
497
498 Since 4.14
499
500
501
502 val forever : (unit -> 'a) -> 'a t
503
504
505 forever f is an infinite sequence where every element is produced (on
506 demand) by the function call f() .
507
508 For instance, forever Random.bool is an infinite sequence of random
509 bits.
510
511
512 forever f is equivalent to map f (repeat ()) .
513
514
515 Since 4.14
516
517
518
519 val cycle : 'a t -> 'a t
520
521
522 cycle xs is the infinite sequence that consists of an infinite number
523 of repetitions of the sequence xs .
524
525 If xs is an empty sequence, then cycle xs is empty as well.
526
527 Consuming (a prefix of) the sequence cycle xs once can cause the se‐
528 quence xs to be consumed more than once. Therefore, xs must be persis‐
529 tent.
530
531
532 Since 4.14
533
534
535
536 val iterate : ('a -> 'a) -> 'a -> 'a t
537
538
539 iterate f x is the infinite sequence whose elements are x , f x , f (f
540 x) , and so on.
541
542 In other words, it is the orbit of the function f , starting at x .
543
544
545 Since 4.14
546
547
548
549
550 Transforming sequences
551 The functions in this section are lazy: that is, they return sequences
552 whose elements are computed only when demanded.
553
554 val map : ('a -> 'b) -> 'a t -> 'b t
555
556
557 map f xs is the image of the sequence xs through the transformation f .
558
559 If xs is the sequence x0; x1; ... then map f xs is the sequence f x0;
560 f x1; ... .
561
562
563
564 val mapi : (int -> 'a -> 'b) -> 'a t -> 'b t
565
566
567 mapi is analogous to map , but applies the function f to an index and
568 an element.
569
570
571 mapi f xs is equivalent to map2 f (ints 0) xs .
572
573
574 Since 4.14
575
576
577
578 val filter : ('a -> bool) -> 'a t -> 'a t
579
580
581 filter p xs is the sequence of the elements x of xs that satisfy p x .
582
583 In other words, filter p xs is the sequence xs , deprived of the ele‐
584 ments x such that p x is false.
585
586
587
588 val filter_map : ('a -> 'b option) -> 'a t -> 'b t
589
590
591 filter_map f xs is the sequence of the elements y such that f x = Some
592 y , where x ranges over xs .
593
594
595 filter_map f xs is equivalent to map Option.get (filter Option.is_some
596 (map f xs)) .
597
598
599
600 val scan : ('b -> 'a -> 'b) -> 'b -> 'a t -> 'b t
601
602 If xs is a sequence [x0; x1; x2; ...] , then scan f a0 xs is a se‐
603 quence of accumulators [a0; a1; a2; ...] where a1 is f a0 x0 , a2 is f
604 a1 x1 , and so on.
605
606 Thus, scan f a0 xs is conceptually related to fold_left f a0 xs . How‐
607 ever, instead of performing an eager iteration and immediately return‐
608 ing the final accumulator, it returns a sequence of accumulators.
609
610 For instance, scan (+) 0 transforms a sequence of integers into the se‐
611 quence of its partial sums.
612
613 If xs has length n then scan f a0 xs has length n+1 .
614
615
616 Since 4.14
617
618
619
620 val take : int -> 'a t -> 'a t
621
622
623 take n xs is the sequence of the first n elements of xs .
624
625 If xs has fewer than n elements, then take n xs is equivalent to xs .
626
627
628 n must be nonnegative.
629
630
631 Since 4.14
632
633
634 Raises Invalid_argument if n is negative.
635
636
637
638 val drop : int -> 'a t -> 'a t
639
640
641 drop n xs is the sequence xs , deprived of its first n elements.
642
643 If xs has fewer than n elements, then drop n xs is empty.
644
645
646 n must be nonnegative.
647
648
649 drop is lazy: the first n+1 elements of the sequence xs are demanded
650 only when the first element of drop n xs is demanded. For this reason,
651 drop 1 xs is not equivalent to tail xs , which queries xs immediately.
652
653
654 Since 4.14
655
656
657 Raises Invalid_argument if n is negative.
658
659
660
661 val take_while : ('a -> bool) -> 'a t -> 'a t
662
663
664 take_while p xs is the longest prefix of the sequence xs where every
665 element x satisfies p x .
666
667
668 Since 4.14
669
670
671
672 val drop_while : ('a -> bool) -> 'a t -> 'a t
673
674
675 drop_while p xs is the sequence xs , deprived of the prefix take_while
676 p xs .
677
678
679 Since 4.14
680
681
682
683 val group : ('a -> 'a -> bool) -> 'a t -> 'a t t
684
685 Provided the function eq defines an equality on elements, group eq xs
686 is the sequence of the maximal runs of adjacent duplicate elements of
687 the sequence xs .
688
689 Every element of group eq xs is a nonempty sequence of equal elements.
690
691 The concatenation concat (group eq xs) is equal to xs .
692
693 Consuming group eq xs , and consuming the sequences that it contains,
694 can cause xs to be consumed more than once. Therefore, xs must be per‐
695 sistent.
696
697
698 Since 4.14
699
700
701
702 val memoize : 'a t -> 'a t
703
704 The sequence memoize xs has the same elements as the sequence xs .
705
706 Regardless of whether xs is ephemeral or persistent, memoize xs is per‐
707 sistent: even if it is queried several times, xs is queried at most
708 once.
709
710 The construction of the sequence memoize xs internally relies on sus‐
711 pensions provided by the module Lazy . These suspensions are not
712 thread-safe. Therefore, the sequence memoize xs must not be queried by
713 multiple threads concurrently.
714
715
716 Since 4.14
717
718
719
720 exception Forced_twice
721
722
723 This exception is raised when a sequence returned by Seq.once (or a
724 suffix of it) is queried more than once.
725
726
727 Since 4.14
728
729
730
731 val once : 'a t -> 'a t
732
733 The sequence once xs has the same elements as the sequence xs .
734
735 Regardless of whether xs is ephemeral or persistent, once xs is an
736 ephemeral sequence: it can be queried at most once. If it (or a suffix
737 of it) is queried more than once, then the exception Forced_twice is
738 raised. This can be useful, while debugging or testing, to ensure that
739 a sequence is consumed at most once.
740
741
742 Since 4.14
743
744
745 Raises Forced_twice if once xs , or a suffix of it, is queried more
746 than once.
747
748
749
750 val transpose : 'a t t -> 'a t t
751
752 If xss is a matrix (a sequence of rows), then transpose xss is the se‐
753 quence of the columns of the matrix xss .
754
755 The rows of the matrix xss are not required to have the same length.
756
757 The matrix xss is not required to be finite (in either direction).
758
759 The matrix xss must be persistent.
760
761
762 Since 4.14
763
764
765
766
767 Combining sequences
768 val append : 'a t -> 'a t -> 'a t
769
770
771 append xs ys is the concatenation of the sequences xs and ys .
772
773 Its elements are the elements of xs , followed by the elements of ys .
774
775
776 Since 4.11
777
778
779
780 val concat : 'a t t -> 'a t
781
782 If xss is a sequence of sequences, then concat xss is its concatena‐
783 tion.
784
785 If xss is the sequence xs0; xs1; ... then concat xss is the sequence
786 xs0 @ xs1 @ ... .
787
788
789 Since 4.13
790
791
792
793 val flat_map : ('a -> 'b t) -> 'a t -> 'b t
794
795
796 flat_map f xs is equivalent to concat (map f xs) .
797
798
799
800 val concat_map : ('a -> 'b t) -> 'a t -> 'b t
801
802
803 concat_map f xs is equivalent to concat (map f xs) .
804
805
806 concat_map is an alias for flat_map .
807
808
809 Since 4.13
810
811
812
813 val zip : 'a t -> 'b t -> ('a * 'b) t
814
815
816 zip xs ys is the sequence of pairs (x, y) drawn synchronously from the
817 sequences xs and ys .
818
819 If the sequences xs and ys have different lengths, then the sequence
820 ends as soon as one sequence is exhausted; the excess elements in the
821 other sequence are ignored.
822
823
824 zip xs ys is equivalent to map2 (fun a b -> (a, b)) xs ys .
825
826
827 Since 4.14
828
829
830
831 val map2 : ('a -> 'b -> 'c) -> 'a t -> 'b t -> 'c t
832
833
834 map2 f xs ys is the sequence of the elements f x y , where the pairs
835 (x, y) are drawn synchronously from the sequences xs and ys .
836
837 If the sequences xs and ys have different lengths, then the sequence
838 ends as soon as one sequence is exhausted; the excess elements in the
839 other sequence are ignored.
840
841
842 map2 f xs ys is equivalent to map (fun (x, y) -> f x y) (zip xs ys) .
843
844
845 Since 4.14
846
847
848
849 val interleave : 'a t -> 'a t -> 'a t
850
851
852 interleave xs ys is the sequence that begins with the first element of
853 xs , continues with the first element of ys , and so on.
854
855 When one of the sequences xs and ys is exhausted, interleave xs ys con‐
856 tinues with the rest of the other sequence.
857
858
859 Since 4.14
860
861
862
863 val sorted_merge : ('a -> 'a -> int) -> 'a t -> 'a t -> 'a t
864
865 If the sequences xs and ys are sorted according to the total preorder
866 cmp , then sorted_merge cmp xs ys is the sorted sequence obtained by
867 merging the sequences xs and ys .
868
869 For more details on comparison functions, see Array.sort .
870
871
872 Since 4.14
873
874
875
876 val product : 'a t -> 'b t -> ('a * 'b) t
877
878
879 product xs ys is the Cartesian product of the sequences xs and ys .
880
881 For every element x of xs and for every element y of ys , the pair (x,
882 y) appears once as an element of product xs ys .
883
884 The order in which the pairs appear is unspecified.
885
886 The sequences xs and ys are not required to be finite.
887
888 The sequences xs and ys must be persistent.
889
890
891 Since 4.14
892
893
894
895 val map_product : ('a -> 'b -> 'c) -> 'a t -> 'b t -> 'c t
896
897 The sequence map_product f xs ys is the image through f of the Carte‐
898 sian product of the sequences xs and ys .
899
900 For every element x of xs and for every element y of ys , the element f
901 x y appears once as an element of map_product f xs ys .
902
903 The order in which these elements appear is unspecified.
904
905 The sequences xs and ys are not required to be finite.
906
907 The sequences xs and ys must be persistent.
908
909
910 map_product f xs ys is equivalent to map (fun (x, y) -> f x y) (product
911 xs ys) .
912
913
914 Since 4.14
915
916
917
918
919 Splitting a sequence into two sequences
920 val unzip : ('a * 'b) t -> 'a t * 'b t
921
922
923 unzip transforms a sequence of pairs into a pair of sequences.
924
925
926 unzip xs is equivalent to (map fst xs, map snd xs) .
927
928 Querying either of the sequences returned by unzip xs causes xs to be
929 queried. Therefore, querying both of them causes xs to be queried
930 twice. Thus, xs must be persistent and cheap. If that is not the
931 case, use unzip (memoize xs) .
932
933
934 Since 4.14
935
936
937
938 val split : ('a * 'b) t -> 'a t * 'b t
939
940
941 split is an alias for unzip .
942
943
944 Since 4.14
945
946
947
948 val partition_map : ('a -> ('b, 'c) Either.t) -> 'a t -> 'b t * 'c t
949
950
951 partition_map f xs returns a pair of sequences (ys, zs) , where:
952
953
954 - ys is the sequence of the elements y such that f x = Left y , where x
955 ranges over xs ;
956
957
958 - zs is the sequence of the elements z such that f x = Right z , where
959 x ranges over xs .
960
961 partition_map f xs is equivalent to a pair of filter_map Ei‐
962 ther.find_left (map f xs) and filter_map Either.find_right (map f xs) .
963
964 Querying either of the sequences returned by partition_map f xs causes
965 xs to be queried. Therefore, querying both of them causes xs to be
966 queried twice. Thus, xs must be persistent and cheap. If that is not
967 the case, use partition_map f (memoize xs) .
968
969
970 Since 4.14
971
972
973
974 val partition : ('a -> bool) -> 'a t -> 'a t * 'a t
975
976
977 partition p xs returns a pair of the subsequence of the elements of xs
978 that satisfy p and the subsequence of the elements of xs that do not
979 satisfy p .
980
981
982 partition p xs is equivalent to filter p xs, filter (fun x -> not (p
983 x)) xs .
984
985 Consuming both of the sequences returned by partition p xs causes xs to
986 be consumed twice and causes the function f to be applied twice to each
987 element of the list. Therefore, f should be pure and cheap. Further‐
988 more, xs should be persistent and cheap. If that is not the case, use
989 partition p (memoize xs) .
990
991
992 Since 4.14
993
994
995
996
997 Converting between sequences and dispensers
998 A dispenser is a representation of a sequence as a function of type
999 unit -> 'a option . Every time this function is invoked, it returns the
1000 next element of the sequence. When there are no more elements, it re‐
1001 turns None . A dispenser has mutable internal state, therefore is
1002 ephemeral: the sequence that it represents can be consumed at most
1003 once.
1004
1005 val of_dispenser : (unit -> 'a option) -> 'a t
1006
1007
1008 of_dispenser it is the sequence of the elements produced by the dis‐
1009 penser it . It is an ephemeral sequence: it can be consumed at most
1010 once. If a persistent sequence is needed, use memoize (of_dispenser it)
1011 .
1012
1013
1014 Since 4.14
1015
1016
1017
1018 val to_dispenser : 'a t -> unit -> 'a option
1019
1020
1021 to_dispenser xs is a fresh dispenser on the sequence xs .
1022
1023 This dispenser has mutable internal state, which is not protected by a
1024 lock; so, it must not be used by several threads concurrently.
1025
1026
1027 Since 4.14
1028
1029
1030
1031
1032 Sequences of integers
1033 val ints : int -> int t
1034
1035
1036 ints i is the infinite sequence of the integers beginning at i and
1037 counting up.
1038
1039
1040 Since 4.14
1041
1042
1043
1044
1045
1046OCamldoc 2022-07-22 Seq(3)