module Monads:`sig`

..`end`

Monad Transformer Library.
## Abstract

## Table of Contents

## Introduction

### The OCaml representation of the monad signature

## Conventions

A monad is an abstraction that can be used to parametrize code
with the way how computations are sequenced. A monad can also be
seen as design pattern, that sometimes make your code more
readable (and, more often, less readable). A monad transformer of
a monad `M`

is a functor that takes another monad `M'`

and
enriches `M`

with the behavior of `M'`

. In other terms a
transformer is a monad composition operator. This library
provides the monad abstraction and implementations of commonly
known monads. Each implementation provides the transformer as
well.

- Abstract
- Introduction
- Conventions
- Monoid a set with an associative operation
- Monad a basic monad interface
- Monad Interfaces
- Monad.S the unary monad
- Monad.S2 the binary monad
- Monad.Minimal the minimal interface
- Monad.Minimal2 the minimal interface
- Monad.Core the core interface
- Monad.Core2 the core interface
- Monad.Plus a monad over a monoid interface
- Monad.Fail a failure monad interface
- Monad.Choice a choice monad interface
- Monad.Trans a monad transformer interface

- Monad.Collection a container of monads
- Monad.Syntax monad operators
- Monad Constructors
- Monad.Ident the do-nothing monad
- Monad.Option a non-total monad
- Monad.Result a non-total monad
- Monad.Result.Error a non-total monad
- Monad.Result.Exception a non-total monad
- Monad.List a non-deterministic monad
- Monad.Seq a non-deterministic monad
- Monad.Writer a computation with a writable state
- Monad.Reader a computation with a readable state
- Monad.State a computation with a state
- Monad.State.Multi a computation with a non-deterministic state
- Monad.Cont a call/cc monad

- Monad Interfaces

In this section we will provide a small introduction into the Monad Concept. If you feel yourself comfortable with the idea of Monad you may skip to the next section.

Monad by itself is a concept or an abstraction. Abstractions come into play when there is a need to write a generic implementation of some algorithm. There are different mechanisms for parametrization an algorithm, but all of them require defining some kind of abstraction, that are usually denoted in a programming language with a type or a module type. In simple cases, an algorithm is parametrized by scalar, e.g.,

algorithm a b ::= x := f a; y := f b; return (x + y);

In a more general case, we may parametrize an algorithm with transformations, i.e., with functions:

algorithm ((_ + _), (f _)) a b ::= x := f a; y := f b; return (x + y);

However, we have one more generalization opportunity. The
semicolon is a sequencing operator that has semantics that is
usually defined by a programming language, and, typically, in
regular deterministic languages `x := f a; y := f b`

means: first
compute `f a`

and assign the result to `x`

, then compute `f b`

and
assign the result to `y`

. However, what if we would like to
parametrize our algorithm with a behavior of the semicolon
and operators:

algorithm ((return _), (_ := _ ; _)) ((_ + _), (f _)) a b ::= x := f a; y := f b; return (x + y);

A pair of operators `(return _)`

and `(_ := _ ; _)`

form the monad
signature. Since a host language no longer defines semantics of
the assignment and semicolon, the monad actually operates with
computations rather than with values. I.e., it is the monad
implementation that now defines how computations produce values,
the order of evaluation, etc. The `return x`

lifts a value into
the computation, i.e., it constructs a trivial computation from a
constant. The `v := y; z`

operator, also called `bind`

, gives the
general semantics of a program, i.e., how the result of computation
`y`

is propagated to the computation `z`

(if propagated), it also
defines the semantics of the semicolon, i.e., whether `z`

is
performed after `y`

, etc. In general, the semantics may be
arbitrary, but let's show few examples.

1. Partiality: a computation may diverge into a bottom value,
i.e., if `y`

diverges, then `z`

is not called and the bottom
value becomes the result of the whole
computation. Monad.Option and
Monad.Result provide a notion of partial
computation with different representations of the bottom value.

2. Nondeterminism: a computation may produce more than one value,
in that case `v`

will be bound several times, and `z`

will be
called for each possible value of
`v`

. Monad.List and
Monad.Seq provide implementations of the
nondeterministic monad with different representations of a
sequence of values.

3. Side-effects: `x`

may produce an effect that changes the
computation environment. We can subdivide effectful computation
into more precise categories:

- effect only -- computations do depend on the effects produced by other computations, see Monad.Writer;
- coeffect only -- computations can't produce effects, though they depend on the computation environment, see Monad.Reader;
- full effect -- computations may change the environment and
may depend on effects produced by other computations, see
see Monad.State.
The effect itself may also be non-deterministic, e.g.,
`z`

is computed for each possible effect produced by`y`

, see Monad.State.Multi

`x`

defines a continuation of `z`

, i.e., akin to
the effect notion, in which a program state is passed from one
computation to another, the continuation notion reifes the
control flow of a computation and passes it to the consequent
continuation as a state. See Monad.Cont.

The monad signature `(return _), (_ := _ ; _)`

is represented with
the following OCaml signature:

```
module type Monad = sig
type 'a t
val return : 'a -> 'a t
val bind : 'a t -> ('a -> 'b t) -> 'b t
end
```

We also use `>>=`

operator as an alias to the `bind`

function. Thus `v := x; z`

is represented in OCaml as
`x >>= fun v -> z`

. We use functors to parametrize algorithms with
signatures, e.g.,

```
module Algorithm(M : Monad) = struct
open R open M
let run a b =
f a >>= fun x ->
f b >>= fun y ->
return (x + y)
end
```

Basically, whenever you see `c1 >>= fun v -> c2`

you should
understand it as `v := c1; c2`

with a parametrized semicolon, and
when you see `c1 >>= fun () -> c2`

you should understand it as ```
c1;
c2
```

. Once you will develop a habit of using monadic semicolon it
will become much easier to you to understand the monadic
code. Alternatively, you may try one of the syntax preprocessors
that will introduce the so called do-notation, with the actual
semicolon being overloaded.

To use the library add `open Monads.Std`

to your program. It will
bring `Monoid`

and `Monad`

modules to your scope. A conventional
way of writing a computation in a monad `M`

, is to open its syntax
with `open M.Syntax`

.

Given that monad is a concept that goes beyond OCaml language, i.e., it is more a design pattern rather than just a module type signature, we follow few conventions to make it easier to work with different monads.

First of all we have two monad signatures, `S`

and `S2`

. The `S`

signature defines monad interface for an unary type constructor ```
'a
t
```

and `S2`

defines the monad interface for a type parametrized
with two type parameters, i.e., `('a,'b) t`

. Correspondingly,
functors named `Make`

generate modules of type `S`

and modules
named `Make2`

produce modules of type `S2`

.

Every monad `M`

provides two transformers `M.Make`

and `M.Make2`

that transforms `M`

into another monad. The `M`

itself provides an
implementation of `M.S`

or `M.S2`

(depending on a particular kind
of monad).

If a monad type is parametrized by two parameters, then the first parameter holds the type of a value, and the second type holds the type of an extra information (usually the type of the context).

Each monad transformer creates a module that has functions `lift`

and `run`

. The `lift`

function lifts original computation into the
transformed one, and `run`

will run the computation.

module Std:`sig`

..`end`

Monad Transformer Library.