File: gen_intf.ml

package info (click to toggle)
ocaml-gen 0.5.3-1
  • links: PTS, VCS
  • area: main
  • in suites: bookworm, bullseye, sid
  • size: 296 kB
  • sloc: ml: 2,124; makefile: 35
file content (366 lines) | stat: -rw-r--r-- 13,247 bytes parent folder | download | duplicates (2)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366

(* This file is free software, part of gen. See file "license" for more details. *)

(** {1 Common signature for transient and restartable generators}

    The signature {!S} abstracts on a type ['a t], where the [t] can be
    the type of transient or restartable generators. Some functions specify
    explicitely that they use ['a gen] (transient generators). *)

type 'a gen = unit -> 'a option

module type S = sig
  type 'a t

  val empty : 'a t
  (** Empty generator, with no elements *)

  val singleton : 'a -> 'a t
  (** One-element generator *)

  val return : 'a -> 'a t
  (** Alias to {!singleton}
      @since 0.3 *)

  val repeat : 'a -> 'a t
  (** Repeat same element endlessly *)

  val iterate : 'a -> ('a -> 'a) -> 'a t
  (** [iterate x f] is [[x; f x; f (f x); f (f (f x)); ...]] *)

  val unfold : ('b -> ('a * 'b) option) -> 'b -> 'a t
  (** Dual of {!fold}, with a deconstructing operation. It keeps on
      unfolding the ['b] value into a new ['b], and a ['a] which is yielded,
      until [None] is returned. *)

  val init : ?limit:int -> (int -> 'a) -> 'a t
  (** Calls the function, starting from 0, on increasing indices.
      If [limit] is provided and is a positive int, iteration will
      stop at the limit (excluded).
      For instance [init ~limit:4 id] will yield 0, 1, 2, and 3. *)

  (** {2 Basic combinators}

      {b Note}: those combinators, applied to generators (not restartable
      generators) {i consume} their argument. Sometimes they consume it lazily,
      sometimes eagerly, but in any case once [f gen] has been called (with [f] a
      combinator), [gen] shouldn't be used anymore. *)

  val is_empty : _ t -> bool
  (** Check whether the gen is empty. Pops an element, if any *)

  val fold : ('b -> 'a -> 'b) -> 'b -> 'a t -> 'b
  (** Fold on the generator, tail-recursively. Consumes the generator. *)

  val reduce : ('a -> 'a -> 'a) -> 'a t -> 'a
  (** Fold on non-empty sequences. Consumes the generator.
      @raise Invalid_argument on an empty gen *)

  val scan : ('b -> 'a -> 'b) -> 'b -> 'a t -> 'b t
  (** Like {!fold}, but keeping successive values of the accumulator.
      Consumes the generator. *)

  val unfold_scan : ('b -> 'a -> 'b * 'c) -> 'b -> 'a t -> 'c t
  (** A mix of {!unfold} and {!scan}. The current state is combined with
      the current element to produce a new state, and an output value
      of type 'c.
      @since 0.2.2 *)

  val iter : ('a -> unit) -> 'a t -> unit
  (** Iterate on the gen, consumes it. *)

  val iteri : (int -> 'a -> unit) -> 'a t -> unit
  (** Iterate on elements with their index in the gen, from 0, consuming it. *)

  val length : _ t -> int
  (** Length of an gen (linear time), consuming it *)

  val map : ('a -> 'b) -> 'a t -> 'b t
  (** Lazy map. No iteration is performed now, the function will be called
      when the result is traversed. *)

  val mapi : (int -> 'a -> 'b) -> 'a t -> 'b t
  (** Lazy map with indexing starting from 0. No iteration is performed now,
      the function will be called when the result is traversed.
      @since 0.5 *)

  val fold_map : ('b -> 'a -> 'b) -> 'b -> 'a t -> 'b t
  (** Lazy fold and map. No iteration is performed now, the function will be
      called when the result is traversed. The result is
      an iterator over the successive states of the fold.
      @since 0.2.4 *)

  val append : 'a t -> 'a t -> 'a t
  (** Append the two gens; the result contains the elements of the first,
      then the elements of the second gen. *)

  val flatten : 'a gen t -> 'a t
  (** Flatten the generator of generators *)

  val flat_map : ('a -> 'b gen) -> 'a t -> 'b t
  (** Monadic bind; each element is transformed to a sub-gen
      which is then iterated on, before the next element is processed,
      and so on. *)

  val mem : ?eq:('a -> 'a -> bool) -> 'a -> 'a t -> bool
  (** Is the given element, member of the gen? *)

  val take : int -> 'a t -> 'a t
  (** Take at most n elements *)

  val drop : int -> 'a t -> 'a t
  (** Drop n elements *)

  val nth : int -> 'a t -> 'a
  (** n-th element, or Not_found
      @raise Not_found if the generator contains less than [n] arguments *)

  val take_nth : int -> 'a t -> 'a t
  (** [take_nth n g] returns every element of [g] whose index
      is a multiple of [n]. For instance [take_nth 2 (1--10) |> to_list]
      will return [1;3;5;7;9] *)

  val filter : ('a -> bool) -> 'a t -> 'a t
  (** Filter out elements that do not satisfy the predicate.  *)

  val take_while : ('a -> bool) -> 'a t -> 'a t
  (** Take elements while they satisfy the predicate. The initial generator
      itself is not to be used anymore after this. *)

  val fold_while : ('a -> 'b -> 'a * [`Stop | `Continue]) -> 'a -> 'b t -> 'a
  (** Fold elements until (['a, `Stop]) is indicated by the accumulator.
      @since 0.2.4 *)

  val drop_while : ('a -> bool) -> 'a t -> 'a t
  (** Drop elements while they satisfy the predicate. The initial generator
      itself should not be used anymore, only the result of [drop_while]. *)

  val filter_map : ('a -> 'b option) -> 'a t -> 'b t
  (** Maps some elements to 'b, drop the other ones *)

  val zip_index : 'a t -> (int * 'a) t
  (** Zip elements with their index in the gen *)

  val unzip : ('a * 'b) t -> 'a t * 'b t
  (** Unzip into two sequences, splitting each pair *)

  val partition : ('a -> bool) -> 'a t -> 'a t * 'a t
  (** [partition p l] returns the elements that satisfy [p],
      and the elements that do not satisfy [p] *)

  val for_all : ('a -> bool) -> 'a t -> bool
  (** Is the predicate true for all elements? *)

  val exists : ('a -> bool) -> 'a t -> bool
  (** Is the predicate true for at least one element? *)

  val min : ?lt:('a -> 'a -> bool) -> 'a t -> 'a
  (** Minimum element, according to the given comparison function.
      @raise Invalid_argument if the generator is empty *)

  val max : ?lt:('a -> 'a -> bool) -> 'a t -> 'a
  (** Maximum element, see {!min}
      @raise Invalid_argument if the generator is empty *)

  val eq : ?eq:('a -> 'a -> bool) -> 'a t -> 'a t -> bool
  (** Equality of generators. *)

  val lexico : ?cmp:('a -> 'a -> int) -> 'a t -> 'a t -> int
  (** Lexicographic comparison of generators. If a generator is a prefix
      of the other one, it is considered smaller. *)

  val compare : ?cmp:('a -> 'a -> int) -> 'a t -> 'a t -> int
  (** Synonym for {! lexico} *)

  val find : ('a -> bool) -> 'a t -> 'a option
  (** [find p e] returns the first element of [e] to satisfy [p],
      or None. *)

  val sum : int t -> int
  (** Sum of all elements *)

  (** {2 Multiple iterators} *)

  val map2 : ('a -> 'b -> 'c) -> 'a t -> 'b t -> 'c t
  (** Map on the two sequences. Stops once one of them is exhausted.*)

  val iter2 : ('a -> 'b -> unit) -> 'a t -> 'b t -> unit
  (** Iterate on the two sequences. Stops once one of them is exhausted.*)

  val fold2 : ('acc -> 'a -> 'b -> 'acc) -> 'acc -> 'a t -> 'b t -> 'acc
  (** Fold the common prefix of the two iterators *)

  val for_all2 : ('a -> 'b -> bool) -> 'a t -> 'b t -> bool
  (** Succeeds if all pairs of elements satisfy the predicate.
      Ignores elements of an iterator if the other runs dry. *)

  val exists2 : ('a -> 'b -> bool) -> 'a t -> 'b t -> bool
  (** Succeeds if some pair of elements satisfy the predicate.
      Ignores elements of an iterator if the other runs dry. *)

  val zip_with : ('a -> 'b -> 'c) -> 'a t -> 'b t -> 'c t
  (** Combine common part of the gens (stops when one is exhausted) *)

  val zip : 'a t -> 'b t -> ('a * 'b) t
  (** Zip together the common part of the gens *)

  (** {2 Complex combinators} *)

  val merge : 'a gen t -> 'a t
  (** Pick elements fairly in each sub-generator. The merge of gens
      [e1, e2, ... ] picks elements in [e1], [e2],
      in [e3], [e1], [e2] .... Once a generator is empty, it is skipped;
      when they are all empty, and none remains in the input,
      their merge is also empty.
      For instance, [merge [1;3;5] [2;4;6]] will be, in disorder, [1;2;3;4;5;6]. *)

  val intersection : ?cmp:('a -> 'a -> int) -> 'a t -> 'a t -> 'a t
  (** Intersection of two sorted sequences. Only elements that occur in both
      inputs appear in the output *)

  val sorted_merge : ?cmp:('a -> 'a -> int) -> 'a t -> 'a t -> 'a t
  (** Merge two sorted sequences into a sorted sequence *)

  val sorted_merge_n : ?cmp:('a -> 'a -> int) -> 'a t list -> 'a t
  (** Sorted merge of multiple sorted sequences *)

  val tee : ?n:int -> 'a t -> 'a gen list
  (** Duplicate the gen into [n] generators (default 2). The generators
      share the same underlying instance of the gen, so the optimal case is
      when they are consumed evenly *)

  val round_robin : ?n:int -> 'a t -> 'a gen list
  (** Split the gen into [n] generators in a fair way. Elements with
      [index = k mod n] with go to the k-th gen. [n] default value
      is 2. *)

  val interleave : 'a t -> 'a t -> 'a t
  (** [interleave a b] yields an element of [a], then an element of [b],
      and so on. When a generator is exhausted, this behaves like the
      other generator. *)

  val intersperse : 'a -> 'a t -> 'a t
  (** Put the separator element between all elements of the given gen *)

  val product : 'a t -> 'b t -> ('a * 'b) t
  (** Cartesian product, in no predictable order. Works even if some of the
      arguments are infinite. *)

  val group : ?eq:('a -> 'a -> bool) -> 'a t -> 'a list t
  (** Group equal consecutive elements together. *)

  val uniq : ?eq:('a -> 'a -> bool) -> 'a t -> 'a t
  (** Remove consecutive duplicate elements. Basically this is
      like [fun e -> map List.hd (group e)]. *)

  val sort : ?cmp:('a -> 'a -> int) -> 'a t -> 'a t
  (** Sort according to the given comparison function. The gen must be finite. *)

  val sort_uniq : ?cmp:('a -> 'a -> int) -> 'a t -> 'a t
  (** Sort and remove duplicates. The gen must be finite. *)

  val chunks : int -> 'a t -> 'a array t
  (** [chunks n e] returns a generator of arrays of length [n], composed
      of successive elements of [e]. The last array may be smaller
      than [n] *)

  val permutations : 'a t -> 'a list t
  (** Permutations of the gen.
      @since 0.2.2 *)

  val permutations_heap : 'a t -> 'a array t
  (** Permutations of the gen, using Heap's algorithm.
      @since 0.2.3 *)

  val combinations : int -> 'a t -> 'a list t
  (** Combinations of given length. The ordering of the elements within
      each combination is unspecified.
      Example (ignoring ordering):
        [combinations 2 (1--3) |> to_list = [[1;2]; [1;3]; [2;3]]]
      @since 0.2.2 *)

  val power_set : 'a t -> 'a list t
  (** All subsets of the gen (in no particular order). The ordering of
      the elements within each subset is unspecified.
      @since 0.2.2 *)

  (** {2 Basic conversion functions} *)

  val of_list : 'a list -> 'a t
  (** Enumerate elements of the list *)

  val to_list : 'a t -> 'a list
  (** non tail-call trasnformation to list, in the same order *)

  val to_rev_list : 'a t -> 'a list
  (** Tail call conversion to list, in reverse order (more efficient) *)

  val to_array : 'a t -> 'a array
  (** Convert the gen to an array (not very efficient) *)

  val of_array : ?start:int -> ?len:int -> 'a array -> 'a t
  (** Iterate on (a slice of) the given array *)

  val of_string : ?start:int -> ?len:int -> string -> char t
  (** Iterate on bytes of the string *)

  val to_string : char t -> string
  (** Convert into a string *)

  val to_buffer : Buffer.t -> char t -> unit
  (** Consumes the iterator and writes to the buffer *)

  val rand_int : int -> int t
  (** Random ints in the given range. *)

  val int_range : ?step:int -> int -> int -> int t
  (** [int_range ~step a b] generates integers between [a] and [b], included,
      with steps of length [step] (1 if omitted). [a] is assumed to be smaller
      than [b], otherwise the result will be empty.
      @raise Invalid_argument if [step=0]
      @param step step between two numbers; must not be zero,
        but it can be negative for decreasing ranges (@since 0.5). *)

  val lines : char t -> string t
  (** Group together chars belonging to the same line
      @since 0.3 *)

  val unlines : string t -> char t
  (** Explode lines into their chars, adding a ['\n'] after each one
      @since 0.3 *)

  module Infix : sig
    val (--) : int -> int -> int t
    (** Synonym for {! int_range ~by:1} *)

    val (>>=) : 'a t -> ('a -> 'b gen) -> 'b t
    (** Monadic bind operator *)

    val (>>|) : 'a t -> ('a -> 'b) -> 'b t
    (** Infix map operator
        @since 0.2.3 *)

    val (>|=) : 'a t -> ('a -> 'b) -> 'b t
    (** Infix map operator
        @since 0.2.3 *)
  end

  val (--) : int -> int -> int t
  (** Synonym for {! int_range ~by:1} *)

  val (>>=) : 'a t -> ('a -> 'b gen) -> 'b t
  (** Monadic bind operator *)

  val (>>|) : 'a t -> ('a -> 'b) -> 'b t
  (** Infix map operator
      @since 0.2.3 *)

  val (>|=) : 'a t -> ('a -> 'b) -> 'b t
  (** Infix map operator
      @since 0.2.3 *)

  val pp : ?start:string -> ?stop:string -> ?sep:string -> ?horizontal:bool ->
    (Format.formatter -> 'a -> unit) -> Format.formatter -> 'a t -> unit
  (** Pretty print the content of the generator on a formatter. *)
end