package seqes

  1. Overview
  2. Docs

Source file sigs2.ml

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
(**************************************************************************)
(*                                                                        *)
(*                                 OCaml                                  *)
(*                                                                        *)
(*                 Simon Cruanes                                          *)
(*                                                                        *)
(*   Copyright 2017 Institut National de Recherche en Informatique et     *)
(*     en Automatique.                                                    *)
(*                                                                        *)
(*                 Raphaël Proust                                         *)
(*                                                                        *)
(*   Copyright 2022 Nomadic Labs                                          *)
(*                                                                        *)
(*   All rights reserved.  This file is distributed under the terms of    *)
(*   the GNU Lesser General Public License version 2.1, with the          *)
(*   special exception on linking described in the file LICENSE.          *)
(*                                                                        *)
(**************************************************************************)

(** {1 Common module signatures}

    This compilation unit gathers module signatures which are used in the rest
    of the library. Essentially, the rest of the library provides functors to
    generate modules with the signatures below.

    The Seqes library provides functors to produce specialised variants of the
    {!Stdlib.Seq} type where the forcing of an element involves a monad. E.g.,
    considering an I/O cooperative scheduling monad à la [Lwt] or [Async], which
    we denote with the type ['a io], you can use Seqes to produce the following
    type

    {[
      type 'a t = unit -> 'a node io
      and 'a node =
        | Nil
        | Cons of 'a * 'a t
    ]}

    In addition to specialised types, the library's functor produce an
    assortment of functions to operate on values of this type. The assortment of
    function is compatible with the {!Stdlib.Seq} (except for the monad part).
    See [examples/seqseq/seqseq.ml] for a demonstration of this compatibility.

    Familiarity with {!Stdlib.Seq} is assumed. *)

(** {1 Two type parameters}

    Some monad have two type parameters. E.g., the result monad is over the type
    [('a, 'e) result].

    The Seqes library offers all the same features over those monads than it
    does over the single-parameter monads. Accordingly, below are variants
    of the module signatures from {!Sigs1}, but for two-parameter monads.

    Note that the specialised type of sequence also carries these two
    parameters:

    {[
      type ('a, 'e) t = unit -> (('a, 'e) node, 'e) io
      and ('a, 'e) node =
        | Nil
        | Cons of 'a * ('a, 'e) t
    ]}

    See [examples/seqres/seqres.ml] for an example of using Seqes for the result
    monad. See [examples/seqlwtres/seqlwtres.ml] for an example of using Seqes
    for the Lwt+result monad.

    {2 Asymmetry}

    Note that the two type parameters of the monad are not treated the same.
    Seqes only requires a bind for the first parameter but not the second.

    {[
      val bind : ('a, 'e) t -> ('a -> ('b, 'e) t) -> ('b, 'e) t
    ]}

*)

(** Equivalent to {!Sigs1.SEQMON1TRAVERSORS} but with two type parameters. *)
module type SEQMON2TRAVERSORS = sig
  type ('a, 'e) callermon
  type ('a, 'e) mon
  type ('a, 'e) t
  val iter : ('a -> (unit, 'e) callermon) -> ('a, 'e) t -> (unit, 'e) mon
  val fold_left : ('a -> 'b -> ('a, 'e) callermon) -> 'a -> ('b, 'e) t -> ('a, 'e) mon
  val iteri : (int -> 'a -> (unit, 'e) callermon) -> ('a, 'e) t -> (unit, 'e) mon
  val fold_lefti : ('b -> int -> 'a -> ('b, 'e) callermon) -> 'b -> ('a, 'e) t -> ('b, 'e) mon
  val for_all : ('a -> (bool, 'e) callermon) -> ('a, 'e) t -> (bool, 'e) mon
  val exists : ('a -> (bool, 'e) callermon) -> ('a, 'e) t -> (bool, 'e) mon
  val find : ('a -> (bool, 'e) callermon) -> ('a, 'e) t -> ('a option, 'e) mon
  val find_map : ('a -> ('b option, 'e) callermon) -> ('a, 'e) t -> ('b option, 'e) mon
  val iter2 : ('a -> 'b -> (unit, 'e) callermon) -> ('a, 'e) t -> ('b, 'e) t -> (unit, 'e) mon
  val fold_left2 : ('a -> 'b -> 'c -> ('a, 'e) callermon) -> 'a -> ('b, 'e) t -> ('c, 'e) t -> ('a, 'e) mon
  val for_all2 : ('a -> 'b -> (bool, 'e) callermon) -> ('a, 'e) t -> ('b, 'e) t -> (bool, 'e) mon
  val exists2 : ('a -> 'b -> (bool, 'e) callermon) -> ('a, 'e) t -> ('b, 'e) t -> (bool, 'e) mon
end

(** Equivalent to {!Sigs1.SEQMON1TRANSFORMERS} but with two type parameters. *)
module type SEQMON2TRANSFORMERS = sig
  type ('a, 'e) callermon
  type ('a, 'e) mon
  type ('a, 'e) t

  include SEQMON2TRAVERSORS
    with type ('a, 'e) callermon := ('a, 'e) callermon
    with type ('a, 'e) mon := ('a, 'e) mon
    with type ('a, 'e) t := ('a, 'e) t

  val init : int -> (int -> ('a, 'e) callermon) -> ('a, 'e) t
  val unfold : ('b -> (('a * 'b) option, 'e) callermon) -> 'b -> ('a, 'e) t
  val forever : (unit -> ('a, 'e) callermon) -> ('a, 'e) t
  val iterate : ('a -> ('a, 'e) callermon) -> 'a -> ('a, 'e) t
  val map : ('a -> ('b, 'e) callermon) -> ('a, 'e) t -> ('b, 'e) t
  val mapi : (int -> 'a -> ('b, 'e) callermon) -> ('a, 'e) t -> ('b, 'e) t
  val filter : ('a -> (bool, 'e) callermon) -> ('a, 'e) t -> ('a, 'e) t
  val filter_map : ('a -> ('b option, 'e) callermon) -> ('a, 'e) t -> ('b, 'e) t
  val scan : ('b -> 'a -> ('b, 'e) callermon) -> 'b -> ('a, 'e) t -> ('b, 'e) t
  val take_while : ('a -> (bool, 'e) callermon) -> ('a, 'e) t -> ('a, 'e) t
  val drop_while : ('a -> (bool, 'e) callermon) -> ('a, 'e) t -> ('a, 'e) t
  val group : ('a -> 'a -> (bool, 'e) callermon) -> ('a, 'e) t -> (('a, 'e) t, 'e) t
  val map2 : ('a -> 'b -> ('c, 'e) callermon) -> ('a, 'e) t -> ('b, 'e) t -> ('c, 'e) t
  val map_product : ('a -> 'b -> ('c, 'e) callermon) -> ('a, 'e) t -> ('b, 'e) t -> ('c, 'e) t
  val partition_map : ('a -> (('b, 'c) Either.t, 'e) callermon) -> ('a, 'e) t -> ('b, 'e) t * ('c, 'e) t
  val partition : ('a -> (bool, 'e) callermon) -> ('a, 'e) t -> ('a, 'e) t * ('a, 'e) t
end

(** Equivalent to {!Sigs1.SEQMON1ALL} but with two type parameters. *)
module type SEQMON2ALL = sig
  type ('a, 'e) mon
  type ('a, 'e) t

  include SEQMON2TRANSFORMERS
    with type ('a, 'e) mon := ('a, 'e) mon
    with type ('a, 'e) callermon := 'a
    with type ('a, 'e) t := ('a, 'e) t

  val is_empty : ('a, 'e) t -> (bool, 'e) mon
  val uncons : ('a, 'e) t -> (('a * ('a, 'e) t) option, 'e) mon
  val length : ('a, 'e) t -> (int, 'e) mon
  val equal : ('a -> 'b -> bool) -> ('a, 'e) t -> ('b, 'e) t -> (bool, 'e) mon
  val compare : ('a -> 'b -> int) -> ('a, 'e) t -> ('b, 'e) t -> (int, 'e) mon
  val empty : ('a, 'e) t
  val return : 'a -> ('a, 'e) t
  val cons : 'a -> ('a, 'e) t -> ('a, 'e) t
  val repeat : 'a -> ('a, 'e) t
  val cycle : ('a, 'e) t -> ('a, 'e) t
  val take : int -> ('a, 'e) t -> ('a, 'e) t
  val drop : int -> ('a, 'e) t -> ('a, 'e) t
  val memoize : ('a, 'e) t -> ('a, 'e) t
  val once : ('a, 'e) t -> ('a, 'e) t
  val transpose : (('a, 'e) t, 'e) t -> (('a, 'e) t, 'e) t
  val append : ('a, 'e) t -> ('a, 'e) t -> ('a, 'e) t
  val concat : (('a, 'e) t, 'e) t -> ('a, 'e) t
  val flat_map : ('a -> ('b, 'e) t) -> ('a, 'e) t -> ('b, 'e) t
  val concat_map : ('a -> ('b, 'e) t) -> ('a, 'e) t -> ('b, 'e) t
  val zip : ('a, 'e) t -> ('b, 'e) t -> (('a * 'b), 'e) t
  val interleave : ('a, 'e) t -> ('a, 'e) t -> ('a, 'e) t
  val sorted_merge : ('a -> 'a -> int) -> ('a, 'e) t -> ('a, 'e) t -> ('a, 'e) t
  val product : ('a, 'e) t -> ('b, 'e) t -> (('a * 'b), 'e) t
  val unzip : (('a * 'b), 'e) t -> ('a, 'e) t * ('b, 'e) t
  val split : (('a * 'b), 'e) t -> ('a, 'e) t * ('b, 'e) t
  val of_dispenser : (unit -> ('a option, 'e) mon) -> ('a, 'e) t
  val to_dispenser : ('a, 'e) t -> (unit -> ('a option, 'e) mon)
  val ints : int -> (int, 'e) t
  val of_seq : 'a Seq.t -> ('a, 'e) t
end

(** Equivalent to {!Sigs1.MONAD} but with two type parameters. *)
module type MONAD2 = sig
  type ('a, 'e) t
  val return : 'a -> ('a, 'e) t
  val bind : ('a, 'e) t -> ('a -> ('b, 'e) t) -> ('b, 'e) t
end

(** Mixed-monad operations *)
module type GLUE2 = sig
  type ('a, 'e) x
  type ('a, 'e) f
  type ('a, 'e) ret
  val bind : ('a, 'e) x -> ('a -> ('b, 'e) f) -> ('b, 'e) ret
end


(**/**)

(* For test purpose we need variants of the monad signatures above where the
   type is injective. This makes the GADTs used to model the seq interface
   valid.

   See https://github.com/ocaml/ocaml/issues/5984 *)

module type INJ_MONAD2 = sig
  type (!'a, 'e) t
  val return : 'a -> ('a, 'e) t
  val bind : ('a, 'e) t -> ('a -> ('b, 'e) t) -> ('b, 'e) t
end