The monad library.
Introduction
Monads in ocaml, as defined in the batteries library and lwt, are defined narrowly in terms of a type constructor, and two functions, return and bind. This misses the i abstraction, which lies in the ability to write functions that apply generally to i all monads. This library defines modules for such functions.
module type Monoid = sig ... endmodule type BasePlus = sig ... endMonads with additional monoid structure.
module type BaseLazyPlus = sig ... endLazyPlus is another base module useful when the monad is a lazy data structure. We then allow the plus operation to be non-strict in its second argument, which makes it possible to use functions such as Monad.lsum lazily. This is what you want for lazy lists.
module type Monad = sig ... endYour basic library functions for monads.
module type MonadPlus = sig ... endLibrary functions for monads with additional monoid structure.
module MakeLazyPlus (M : BaseLazyPlus) : LazyPlus with type 'a m = 'a M.mThe lazy monad. Automatically wraps calls lazily and forces as needed.
module LazyListM : LazyPlus with type 'a m = 'a LazyList.tmodule Continuation (T : sig ... end) : sig ... endFor the incorruptible programmer:
module type BaseCollectionM = sig ... endMonads for collections. Stream is the current use-case for this, since it is parameterised on a collection monad (like list).
module type Stream = sig ... endStreams supporting fair and unbounded search.
module type StreamC = sig ... endThe union of streams and collections.
module LazyT (M : BatInterfaces.Monad) : sig ... endmodule ListT (M : BatInterfaces.Monad) : sig ... endThe list monad transformer will add non-determinism to computations. I have not provided a transformer for lazy lists, since I'm not yet sure how to implement it. It would probably need a lazy version of map_m, but it's not clear to me how to write this, since whether the computations are strict will determine whether the argument has to be completely forced.
module OptionT (M : BatInterfaces.Monad) : sig ... endmodule StateT (T : sig ... end) (M : BatInterfaces.Monad) : sig ... endmodule WriterT (Mon : Monoid) (M : BatInterfaces.Monad) : sig ... endSometimes, you might want to transform a collection monad, in such a way that functions such as BaseCollectionM.unique behave in a sensible way by regarding None as smaller than any Some. Each transformer provides a function cmp_on with which the collection functions such as BaseCollectionM.difference are implemented. We also provide the list function for transformers.
module CollectionOpt (C : BaseCollectionM) : sig ... endmodule CollectionWriter (Mon : sig ... end) (C : BaseCollectionM) : sig ... endmodule CollectionState (T : sig ... end) (C : BaseCollectionM) : sig ... endmodule MakeStream (M : sig ... end) : sig ... endCreate a stream monad from an arbitrary inner monad, which computes the values discovered in each generation. This is pretty abstract, since we're not requiring that the inner monad is a collection. There is a constraint here, since we're strictly supposed to disallow a monad collection where order of elements matters. I think we can characterise this abstractly by saying that the plus operation on the inner monad must be commutative, but don't take my word for it!
module MakeStreamC (M : sig ... end) : sig ... endHere, we create a stream monad from a definite collection monad Monad.BaseCollectionM. The inner monad will be used to represent the generations in the stream. The order of elements in each generation should not matter, so you might want to use a set or a bag. If you want to live life on the edge, just remember that your code should not depend on the order of elements within generations (you can, of course, depend on the order that generations appear in the stream). You can enforce this constraint by performing, say, a sort on each generation.