Source file sigs1.ml

(**************************************************************************)
(*                                                                        *)
(*                                 OCaml                                  *)
(*                                                                        *)
(*                 Simon Cruanes                                          *)
(*                                                                        *)
(*   Copyright 2017 Institut National de Recherche en Informatique et     *)
(*     en Automatique.                                                    *)
(*                                                                        *)
(*                 Raphaël Proust                                         *)
(*                                                                        *)
(*   Copyright 2022 Nomadic Labs                                          *)
(*   Copyright 2025 Raphaël Proust                                        *)
(*                                                                        *)
(*   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 Traversors}

    A traversor is a function that traverses a sequence, applying a
    caller-provided function on the sequence's elements. E.g., [iter].

    A traversor may traverse only a portion of the sequence. E.g., [for_all].

    The type of traversor mentions two distinct monad types:

    - ['a mon]: the monad that the sequence is specialised to
    - ['a callermon]: the monad that the caller-provided functions use

    These two monad types can be different. The main use for these types being
    distinct is to provide both plain-traversors (e.g., the plain-[iter] has
    type [('a -> unit) -> 'a t -> unit mon]) and [mon]-traversors (e.g., the
    [mon]-[iter] has type [('a -> unit mon) -> 'a t -> unit mon]).
    Plain-traversors are obtained with [type 'a callermon := 'a] whereas
    [mon]-traversors are obtained with [type 'a callermon := 'a mon].

    There are more advanced use for tiers of monads. See
    [examples/seqlist/seqlist.ml] for an advanced example involving [List]
    and [Option].
*)
module type SEQMON1TRAVERSORS = sig

  (** [callermon] is the type constructor for the monad used in caller-provided
      functions.

      The type is meant to be substituted by the functor that produces modules
      following this signature. *)
  type 'a callermon

  (** [mon] is the type constructor for the monad used in the sequence.

   The type is meant to be substituted by the functor that produces modules of
   following this signature. *)
  type 'a mon

  (** [t] is the type constructor for the sequence.

   The type is meant to be substituted by the functor that produces modules of
   following this signature. *)
  type 'a t

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

end

(** {2 Transformers}

    A transformer is a function that traverses a sequence, applying a
    caller-provided function on the sequence's elements, returning a sequence.
    E.g., [map].

    A transformer may traverse only a part of the sequence. E.g., [drop_while].

    Other functions do not necessarily fit the exact description of traversors
    but have similar characteristic in their use of monads. E.g., [init] does
    not consume any sequence.

    The type of a transformer mentions two distinct monad types:

    - ['a mon]: the monad that the sequence is specialised to (sometimes this
      type is mentioned implicitly as a component of the ['a t] type)
    - ['a callermon]: the monad that the caller-provided functions use

    These two monad types can be different. The main use for these types being
    distinct is to provide both plain-traversors (e.g., the plain-[map] has
    type [('a -> 'b) -> 'a t -> 'b t]) and [mon]-traversors (e.g., the
    [mon]-[map] has type [('a -> 'b mon) -> 'a t -> 'b t]).
    Plain-traversors are obtained with [type 'a callermon := 'a] whereas
    [mon]-traversors are obtained with [type 'a callermon := 'a mon].

    There are more advanced use for tiers of monads. See
    [examples/seqlwtres/seqlwtres.ml] for an advanced example involving [Lwt]
    and [result].

    Because a transformer returns a new sequence, and because that sequence
    carries within it the [mon] monad, there are restrictions on what the caller
    monad can be. These restrictions are imposed onto you by the functors that
    produce Transformer modules. Specifically, these functors expect a function
    to lift one monad into the other.

    Because the nature of the transformers impose a restriction on the kind of
    [callermon] that can be used, it is always possible to generate traversors
    for these monads. Consequently, the [SEQMON1TRANSFORMERS] signature includes
    the [SEQMON1TRAVERSORS] signature and the functors that generate transformers
    also generate traversors.
*)
module type SEQMON1TRANSFORMERS = sig

  (** [callermon] is the type constructor for the monad used in caller-provided
      functions.

      The type is meant to be substituted by the functor that produces modules
      following this signature. *)
  type 'a callermon

  (** [mon] is the type constructor for the monad used in the sequence.

   The type is meant to be substituted by the functor that produces modules of
   following this signature. *)
  type 'a mon

  (** [t] is the type constructor for the sequence.

   The type is meant to be substituted by the functor that produces modules of
   following this signature. *)
  type 'a t

  (** Any monad that we can use to produce transformers, we can also use to
      produce traversors. Thus, [SEQMON1TRANSFORMERS] includes [SEQMON1TRAVERSORS]
      and all the functors producing transformer also produce traversors. *)
  include Sigs2.SEQMON2TRANSFORMERS
    with type ('a, 'e) callermon := 'a callermon
    with type ('a, 'e) mon := 'a mon
    with type ('a, 'e) t := 'a t

end

(** {2 Other functions}

    Sequences also have functions that do not take any caller-provided function
    as arguments. For these functions, only the monad that the sequence is
    specialised to matters.

    In addition to all those functions, the [SEQMON1ALL] module signature also
    includes the [SEQMON1TRANSFORMERS] module signature, but specialised with the
    [type 'a callermon := 'a]. All the functors that produce modules with this
    signature also produce all the transformers and traversors that operate with
    no caller monad.
*)
module type SEQMON1ALL = sig

  (** [mon] is the type constructor for the monad used in the sequence.

   The type is meant to be substituted by the functor that produces modules of
   following this signature. *)
  type 'a mon

  (** [t] is the type constructor for the sequence.

   The type is meant to be substituted by the functor that produces modules of
   following this signature. *)
  type 'a t


  include Sigs2.SEQMON2ALL
    with type ('a, 'e) mon := 'a mon
    with type ('a, 'e) t := 'a t

end

(** {2 Monads}

    Different functors require different monads. *)

(** Normal monad *)
module type MONAD1 = sig
  type 'a t
  include Sigs2.MONAD2 with type ('a, 'e) t := 'a t
end

(** Mixed-monad operations *)
module type GLUE1 = sig
  type 'a x
  type 'a f
  type 'a ret
  include Sigs2.GLUE2
    with type ('a, 'e) x := 'a x
    with type ('a, 'e) f := 'a f
    with type ('a, 'e) ret := 'a ret
end