# ocaml-logicm / logicM_stream.mli

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