Source

ocaml-logicm / logicM_stream.mli

(** An attempt to port LogicM (Backtracking, Interleaving,
    and Terminating Monad, see paper http://okmij.org/ftp/papers/LogicT.pdf )
    to OCaml, implementing it using Streams.

    If you have questions about the design or semantics of some function,
    please take a look at this paper first.

    Computations are destructive: once one gets result from computation,
    this operation can't be undone.

    Computations are not ordered, unlike Streams or Lists.

    Although it's possible to get results from computation ([runL], [get])
    and put them back ([from_stream], [return]), it's preferable to use
    combinators that get the computations (values of type ['a m]) and
    return the computations too, to make possible some future optimizations. *)

(** Type of computation returning values of type ['a]. *)
    type 'a m

(** Computation that returns no results. *)
    val mzero : 'a m

(** [return x] is the computation that returns [x] as the only result. *)
    val return : 'a -> 'a m

(** maps values of computation with given function. *)
    val map : ?chunk:int -> ('a -> 'b) -> 'a m -> 'b m

(** Type of mplus-like functions ([interleave], [( <+> )]).
    The optional argument [?chunk] determine the count of values
    to be added to resulting stream before suspending the
    computation. *)
    type 'a mplus_sig = ?chunk:int -> 'a m -> 'a m -> 'a m

(** Interleave two calculations: resulting calculation [interleave m1 m2]
    will return results from [m1] and [m2] both.

    We could have the classic [mplus] too, but since the computations'
    results are not ordered anyway, and [mplus] imposes ordering on
    computation, there are no [mplus] here.  Use [interleave]. *)
    val interleave : 'a mplus_sig

(** Infix operator equal to [interleave]. *)
    val ( <+> ) : 'a mplus_sig

(** Pass value of this type to [join] and [bind] functions to choose
    the algorithm to be used while binding/joining. *)
    type alg =
      [ `Diag
      | `Diagn of int
      | `Wide
      | `Widen of int
      | `Deep
      | `Deepn of int
      ]


(** [join ms] "concatenates" the results of computation [ms],
    which are the computations itself.
    Equivalent to [bind (fun x -> x) ms]. *)
    val join : ?alg:alg -> ('a m) m -> 'a m

(** [bind f m] for computation [m] consisting of results [[a1;a2;..]]
    returns joined results of computations [[f a1;f a2;..]]. *)
    val bind : ?alg:alg -> ('a -> 'b m) -> 'a m -> 'b m

(** [m >>= f] is equivalent to [bind f m]. *)
    val ( >>= ) : 'a m -> ('a -> 'b m) -> 'b m

(** [from_stream s] is the computation that returns all the results
    that return stream [s].

    Use this function (with Stream.of_list) to get results from list. *)
    val from_stream : 'a Stream.t -> 'a m

(** [runL None m] returns list with all results of computation [m].
    [runL (Some n) m] returns list with at most [n] results of
    computation [m]. *)
    val runL : int option -> 'a m -> 'a list

(** [limit n m] returns no more that [n] results from computation [m]. *)
    val limit : int -> 'a m -> 'a m

(** [once m] == [limit 1 m] *)
    val once : 'a m -> 'a m

(** [filter pred m] returns new computation with the results of [m]
    that satisfy the predicate [pred].

    It can be implemented as
    [let filter f m = m >>= (fun x -> if pred x then return x else mzero)] *)
    val filter : ('a -> bool) -> 'a m -> 'a m

(** [ifte ?alg m th el] returns [bind ?alg th m] if [m] returns at least one
    result, and returns [el] otherwise. *)
    val ifte : ?alg:alg -> 'a m -> ('a -> 'b m) -> 'b m -> 'b m

(** [ifteu ?alg m th el] returns [bind ?alg th m] if [m] returns at least one
    result, and returns [el ()] otherwise. *)
    val ifteu : ?alg:alg -> 'a m -> ('a -> 'b m) -> (unit -> 'b m) -> 'b m

(** 
 *)
    val ifm : 'a m -> th:('a m -> 'b) -> el:(unit -> 'b) -> 'b

    val guard : bool -> unit m

(** . *)
    val msplit : 'a m -> ('a * 'a m) option

    val destruct_bind : 'a m -> ('a -> 'a m -> 'b m) -> 'b m -> 'b m
    val destruct_bindu : 'a m -> ('a -> 'a m -> 'b m) -> (unit -> 'b m) -> 'b m

    val iter : ('a -> unit) -> 'a m -> unit

(** {6 Algorithms} *)

(** You can choose the algorithm to be used by [join] and [bind] functions.

    There are three algorithms: wide-first, depth-first and diagonal walking.

    Since Streams can be composed either eagerly or lazy, and lazy
    composition has some overhead, every algorithm has parameter that
    determines how many stream items will be added eagerly before
    suspending the Stream building.

    The [join] function can be trivially expressed using [bind]:
    [let join ma = bind (fun a -> a) ma]
    That's how the [join] is implemented now, and values of type [alg]
    affect the [join]'s behaviour too, the same way.

    Assume we have computation [ma] returning [a1;a2;..].
    Let the "bind function" [f] will be the [f] for [bind f ma]
    and [identity] for [join ma].

    With [`Wide] and [`Widen n], functions will read the whole
    [ma] = [a1;a2;..;ak] into memory, map it with [f], then the
    resulting stream will be composed from [n] results taken
    sequentially from [a1], [a2] and so on, so [n*k] values will be
    added to the result eagerly.

    When you choose wide-first walking, and [ma] is infinite,
    the algorithm will eat up all memory while reading [ma].

    You can choose wide-first walking if [ma] is finite, if you
    want to get all its results (for example, to free some resources
    associated with [ma]), and if the results you need are returned
    at the beginning of [f an] computations.

    With [`Deep] and [`Deepn n], functions will read results of
    [f a1], then results from [f a2] and so on, adding
    approximately [n] values to the result eagerly.

    When you choose depth-first walking, and there exists some [n]
    that computation [f an] is infinite, then [bind] will read results
    from this [f an] infinitely, and [f an+1] will be left untouched.

    You can choose depth-first walking if you want to keep used
    memory low, if you want to have at most one of [f an] computation
    active at time (for example, to avoid concurrent use of resources
    associated with [f an]), or if the results you need are returned
    by processing first [an]'s ([f a1], [f a2]).

    With [`Diag] and [`Diagn n], functions will read values
    diagonally, adding approximately [n^2] values to the result
    eagerly.  In worst case, there will be [s*n] values of type
    ['b m] (computations [f a1; f a2; .. f a_s*n]) present
    in memory, where [s] is the number of step, and if all
    [f ai] are infinite, then used memory will grow linearly.

    (todo: do we need to limit the number of ['b m] values present
    in memory?)

    (todo: do we need to specify the chunk size for reading [ma]
    and for reading [f an] separately?)

    You can choose diagonal walking if you want to get results
    when [ma] and [f an] are possibly infinite computations, or
    when the results you need are distributed uniformly in [f an].

    The default algorithm is diagonal walking.

    The default chunk sizes are: for `Wide -- 10, for `Deep -- 100,
    for `Diag -- 20.
*)

    val impl_name : string