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 constructor
`list`

which appears in type expressions such as`'a list`

; - the function
`return`

; - the function
`bind`

.

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

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.

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:

State monads.

module Error:

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.

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`

.
Use these functors with the base modules to generate the monad library functions.

module Make:

Monad library.

module MakePlus:

MonadPlus library.

module MakeLazyPlus:

LazyPlus library.

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:

The continuation monad.

module MakeReader:

Create a reader from an arbitrary type of environment.

module MakeWriter:

Create a writer from an arbitrary type of written value.

module MakeStream:

Create a stream monad from an arbitrary inner monad, which computes the
values discovered in each generation.

module MakeStreamC:

Here, we create a stream monad from a definite collection monad

`Monad.BaseCollectionM`

.
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:

The lazy monad transformer will wrap computated values in a thunk.

module ListT:

The list monad transformer will add non-determinism to computations.

module OptionT:

The option monad transformer will allow computations to fail.

module StateT:

The state monad transformer will allow computations to read and write to a state.

module WriterT:

The writer monad transformer will allow computations to write values.

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:

Transformer allowing optional values in a collection.

module CollectionWriter:`functor (`

`W`

`:`

`sig`

`include Monad.Writer`

val cmp :`t -> t -> bool`

`end`

`) ->`

Transformer for writing data inside a collection.

module CollectionState:

State inside a collection.