Source file sigs2.ml

(**************************************************************************)
(*                                                                        *)
(*                                 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