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

  (** See {!Stdlib.Seq.iter} *)
  val iter : ('a -> unit callermon) -> 'a t -> unit mon

  (** See {!Stdlib.Seq.fold_left} *)
  val fold_left : ('a -> 'b -> 'a callermon) -> 'a -> 'b t -> 'a mon

  (** See {!Stdlib.Seq.iteri} *)
  val iteri : (int -> 'a -> unit callermon) -> 'a t -> unit mon

  (** See {!Stdlib.Seq.fold_lefti} *)
  val fold_lefti : ('b -> int -> 'a -> 'b callermon) -> 'b -> 'a t -> 'b mon

  (** See {!Stdlib.Seq.for_all} *)
  val for_all : ('a -> bool callermon) -> 'a t -> bool mon

  (** See {!Stdlib.Seq.exists} *)
  val exists : ('a -> bool callermon) -> 'a t -> bool mon

  (** See {!Stdlib.Seq.find} *)
  val find : ('a -> bool callermon) -> 'a t -> 'a option mon

  (** See {!Stdlib.Seq.find_map} *)
  val find_map : ('a -> 'b option callermon) -> 'a t -> 'b option mon

  (** See {!Stdlib.Seq.iter2} *)
  val iter2 : ('a -> 'b -> unit callermon) -> 'a t -> 'b t -> unit mon

  (** See {!Stdlib.Seq.fold_left2} *)
  val fold_left2 : ('a -> 'b -> 'c -> 'a callermon) -> 'a -> 'b t -> 'c t -> 'a mon

  (** See {!Stdlib.Seq.for_all2} *)
  val for_all2 : ('a -> 'b -> bool callermon) -> 'a t -> 'b t -> bool mon

  (** See {!Stdlib.Seq.exists2} *)
  val exists2 : ('a -> 'b -> bool callermon) -> 'a t -> 'b t -> bool mon
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 SEQMON1TRAVERSORS
    with type 'a callermon := 'a callermon
    with type 'a mon := 'a mon
    with type 'a t := 'a t


  (** See {!Stdlib.Seq.init} *)
  val init : int -> (int -> 'a callermon) -> 'a t

  (** See {!Stdlib.Seq.unfold} *)
  val unfold : ('b -> ('a * 'b) option callermon) -> 'b -> 'a t

  (** See {!Stdlib.Seq.forever} *)
  val forever : (unit -> 'a callermon) -> 'a t

  (** See {!Stdlib.Seq.iterate} *)
  val iterate : ('a -> 'a callermon) -> 'a -> 'a t

  (** See {!Stdlib.Seq.map} *)
  val map : ('a -> 'b callermon) -> 'a t -> 'b t

  (** See {!Stdlib.Seq.mapi} *)
  val mapi : (int -> 'a -> 'b callermon) -> 'a t -> 'b t

  (** See {!Stdlib.Seq.filter} *)
  val filter : ('a -> bool callermon) -> 'a t -> 'a t

  (** See {!Stdlib.Seq.filter_map} *)
  val filter_map : ('a -> 'b option callermon) -> 'a t -> 'b t

  (** See {!Stdlib.Seq.scan} *)
  val scan : ('b -> 'a -> 'b callermon) -> 'b -> 'a t -> 'b t

  (** See {!Stdlib.Seq.take_while} *)
  val take_while : ('a -> bool callermon) -> 'a t -> 'a t

  (** See {!Stdlib.Seq.drop_while} *)
  val drop_while : ('a -> bool callermon) -> 'a t -> 'a t

  (** See {!Stdlib.Seq.group} *)
  val group : ('a -> 'a -> bool callermon) -> 'a t -> 'a t t

  (** See {!Stdlib.Seq.map2} *)
  val map2 : ('a -> 'b -> 'c callermon) -> 'a t -> 'b t -> 'c t

  (** See {!Stdlib.Seq.map_product} *)
  val map_product : ('a -> 'b -> 'c callermon) -> 'a t -> 'b t -> 'c t

  (** See {!Stdlib.Seq.partition_map} *)
  val partition_map : ('a -> ('b, 'c) Either.t callermon) -> 'a t -> 'b t * 'c t

  (** See {!Stdlib.Seq.partition} *)
  val partition : ('a -> bool callermon) -> 'a t -> 'a 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 SEQMON1TRANSFORMERS
    with type 'a mon := 'a mon
    with type 'a callermon := 'a
    with type 'a t := 'a t


  (** See {!Stdlib.Seq.is_empty} *)
  val is_empty : 'a t -> bool mon

  (** See {!Stdlib.Seq.uncons} *)
  val uncons : 'a t -> ('a * 'a t) option mon

  (** See {!Stdlib.Seq.length} *)
  val length : 'a t -> int mon

  (** See {!Stdlib.Seq.equal} *)
  val equal : ('a -> 'b -> bool) -> 'a t -> 'b t -> bool mon

  (** See {!Stdlib.Seq.compare} *)
  val compare : ('a -> 'b -> int) -> 'a t -> 'b t -> int mon

  (** See {!Stdlib.Seq.empty} *)
  val empty : 'a t

  (** See {!Stdlib.Seq.return} *)
  val return : 'a -> 'a t

  (** See {!Stdlib.Seq.cons} *)
  val cons : 'a -> 'a t -> 'a t

  (** See {!Stdlib.Seq.repeat} *)
  val repeat : 'a -> 'a t

  (** See {!Stdlib.Seq.cycle} *)
  val cycle : 'a t -> 'a t

  (** See {!Stdlib.Seq.take} *)
  val take : int -> 'a t -> 'a t

  (** See {!Stdlib.Seq.drop} *)
  val drop : int -> 'a t -> 'a t

  (** See {!Stdlib.Seq.memoize} *)
  val memoize : 'a t -> 'a t

  (** See {!Stdlib.Seq.once} *)
  val once : 'a t -> 'a t

  (** See {!Stdlib.Seq.transpose} *)
  val transpose : 'a t t -> 'a t t

  (** See {!Stdlib.Seq.append} *)
  val append : 'a t -> 'a t -> 'a t

  (** See {!Stdlib.Seq.concat} *)
  val concat : 'a t t -> 'a t

  (** See {!Stdlib.Seq.flat_map} *)
  val flat_map : ('a -> 'b t) -> 'a t -> 'b t

  (** See {!Stdlib.Seq.concat_map} *)
  val concat_map : ('a -> 'b t) -> 'a t -> 'b t

  (** See {!Stdlib.Seq.zip} *)
  val zip : 'a t -> 'b t -> ('a * 'b) t

  (** See {!Stdlib.Seq.interleave} *)
  val interleave : 'a t -> 'a t -> 'a t

  (** See {!Stdlib.Seq.sorted_merge} *)
  val sorted_merge : ('a -> 'a -> int) -> 'a t -> 'a t -> 'a t

  (** See {!Stdlib.Seq.product} *)
  val product : 'a t -> 'b t -> ('a * 'b) t

  (** See {!Stdlib.Seq.unzip} *)
  val unzip : ('a * 'b) t -> 'a t * 'b t

  (** See {!Stdlib.Seq.split} *)
  val split : ('a * 'b) t -> 'a t * 'b t

  (** See {!Stdlib.Seq.of_dispenser} *)
  val of_dispenser : (unit -> 'a option mon) -> 'a t

  (** See {!Stdlib.Seq.to_dispenser} *)
  val to_dispenser : 'a t -> (unit -> 'a option mon)

  (** See {!Stdlib.Seq.ints} *)
  val ints : int -> int t

  (** See {!Stdlib.Seq.of_seq} *)
  val of_seq : 'a Seq.t -> 'a t
end

(** {2 Monads}

    Different functors require different monads. *)

(** Normal monad *)
module type MONAD1 = sig
  type 'a t
  val return : 'a -> 'a t
  val bind : 'a t -> ('a -> 'b t) -> 'b t
end

(** Mixed-monad operations *)
module type GLUE1 = sig
  type 'a x
  type 'a f
  type 'a ret
  val bind : 'a x -> ('a -> 'b f) -> 'b 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_MONAD1 = sig
  type !'a t
  val return : 'a -> 'a t
  val bind : 'a t -> ('a -> 'b t) -> 'b t
end