Module Monad

module Monad: sig .. end
The monad library.

Introduction

Monads are a popular concept in Haskell and controversial just about everywhere else on the planet! They have been thought of by some in the Ocaml community as a "design pattern" (see the documentation for BatMonad), and a nice way to abstract over resource manipulation. My favourite example in Ocaml is the lwt library.

But I find that, in Ocaml, "monads" are typically seen rather narrowly in terms of a bind and return function. Personally, I think monads are bigger than that. They are an abstraction, and the meaning of that abstraction is to be found in libraries which give you general functions that apply to all monads. To make the point concretely, if we aren't automatically deriving a Monad.Monad.join function for all of our monads, then we've missed something important.

In other words, I want to say that monads as an abstraction are defined by an abstract monad library. Such a library is the purpose of this module.

I recommend checking out the the types in this module. I find they say a lot about the meaning of the various functions.

A rambling note on terminology

There's some confusing terminology when it comes to monads, which I'll try to clarify for the purposes of the documentation.

Now I'm no category theorist, but if I were to try to get technical, I'd say that a monad is a three-tuple: a type-constructor, and two functions. So, for instance, the list monad can be defined by three things:

The fact that we have a type-constructor here explains why a monad cannot be represented nicely by a simple tuple. We need to package them into a module instead.

Terminology now gets a bit hairy, because as pointed out by Mark Dominus, we need to talk about many different things in the context of monads, which leads to overloading and an (overused) use of the adjective "monadic."

We have our three tuple above, we have the type-constructor list, we have types such as int list, and we have values such as [1;2;3] : int list. In general, I shall reserve "monad" for the type-constructor list, and I'll read values such as [1;2;3] as "the computation in the list monad which returns 1, 2 or 3." I will also read values of type m () as "the computation in the m monad which returns nothing."

I'm not convinced that "computation" is the best analogy for what monads are about, and I worry that if this metaphor gets taken too seriously, we might miss some interesting monads. For now, I'm just treating it as a useful metaphor for writing this documentation.
Author(s): Phil Scott



Base Modules

module type Monoid = sig .. end
This is your usual monoid.
module type BasePlus = sig .. end
Monads with additional monoid structure.
module type BaseLazyPlus = sig .. end
LazyPlus is another base module useful when the monad is a lazy data structure.

Some general monads.

module type Reader = sig .. end
Readers are monads which allow computations to depend on a fixed environment.
module type Writer = sig .. end
A writer allows an additional output value to be written during computations and accumulated into a final result.
module State: 
functor (T : sig
type s 
end) -> sig .. end
State monads.
module Error: 
functor (E : sig
type e 
val defaultError : e
end) -> sig .. end
Error monads.
module type BaseCollectionM = sig .. end
Monads for collections.
module type Stream = sig .. end
Streams supporting fair and unbounded search.
module type StreamC = sig .. end
The union of streams and collections.

Library Types

module type Monad = sig .. end
Your basic library functions for monads.
module type MonadPlus = sig .. end
Library functions for monads with additional monoid structure.
module type LazyPlus = sig .. end
This is the counterpart for the lazy version of Monad.BasePlus.

Library Creation


Use these functors with the base modules to generate the monad library functions.
module Make: 
functor (M : BatInterfaces.Monad) -> Monad with type 'a m = 'a M.m
Monad library.
module MakePlus: 
functor (M : BasePlus) -> MonadPlus with type 'a m = 'a M.m
MonadPlus library.
module MakeLazyPlus: 
functor (M : BaseLazyPlus) -> LazyPlus with type 'a m = 'a M.m
LazyPlus library.

Specific monads

module LazyM: BatInterfaces.Monad  with type 'a m = 'a Lazy.t
The lazy monad.
module List: BasePlus  with type 'a m = 'a list
The venerable list monad.
module LazyListM: BaseLazyPlus  with type 'a m = 'a LazyList.t
The lazy list monad.
module Option: BasePlus  with type 'a m = 'a option
Options can be understood as computations which might optionally fail.
module Continuation: 
functor (T : sig
type r 
end) -> sig .. end
The continuation monad.
module MakeReader: 
functor (T : sig
type t 
end) -> sig .. end
Create a reader from an arbitrary type of environment.
module MakeWriter: 
functor (M : Monoid) -> sig .. end
Create a writer from an arbitrary type of written value.
module MakeStream: 
functor (M : sig
include Monad.BaseLazyPlus
include Applicative.Base
end) -> sig .. end
Create a stream monad from an arbitrary inner monad, which computes the values discovered in each generation.
module MakeStreamC: 
functor (M : sig
include Monad.BaseCollectionM
include Applicative.Base
end) -> sig .. end
Here, we create a stream monad from a definite collection monad Monad.BaseCollectionM.

Transformers


Monads support a certain amount of composition, allowing one create a single monad which combines the properties of other monads. For instance, we might want a monad which reads from an environment and writes to a log. We can do this by transforming the reader monad with the writer transformer, or vice versa.
module LazyT: 
functor (M : BatInterfaces.Monad) -> sig .. end
The lazy monad transformer will wrap computated values in a thunk.
module ListT: 
functor (M : BatInterfaces.Monad) -> sig .. end
The list monad transformer will add non-determinism to computations.
module OptionT: 
functor (M : BatInterfaces.Monad) -> sig .. end
The option monad transformer will allow computations to fail.
module StateT: 
functor (T : sig
type s 
end) ->
functor (M : BatInterfaces.Monad) -> sig .. end
The state monad transformer will allow computations to read and write to a state.
module WriterT: 
functor (W : Writer) ->
functor (M : BatInterfaces.Monad) -> sig .. end
The writer monad transformer will allow computations to write values.

Transformers on Collections


Sometimes, you might want to transform a collection monad, in such a way that functions such as Monad.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: 
functor (C : BaseCollectionM) -> sig .. end
Transformer allowing optional values in a collection.
module CollectionWriter: 
functor (W : sig
include Monad.Writer
val cmp : t -> t -> bool
end) ->
functor (C : BaseCollectionM) -> sig .. end
Transformer for writing data inside a collection.
module CollectionState: 
functor (T : sig
type s 
val cmp : s -> s -> bool
end) ->
functor (C : BaseCollectionM) -> sig .. end
State inside a collection.