Monad Transformer Library.
Abstract
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 makes 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.
Table of Contents
Introduction
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
4. Continuation: 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 OCaml representation of the monad signature
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.
Conventions
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 and/or open M.Let (for the monadic binding operators).
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.
In order to use the monad transformers to build up a monad transformer stack, the inner module needs both the monad types and monad functions, so that it satisfies the Monad.S signature. Therefore, it needs to include both T and Make (or T2 and Make2), in order to use the Make functor of the outer monad. For example, to create a state monad nested inside a writer monad, you can do the following.
module St = struct
module Env = struct
type t = int
end
include Monad.State.T1(Env)(Monad.Ident) (* adds types *)
include Monad.State.Make(Env)(Monad.Ident) (* adds functions and modules *)
end
module W = Monad.Writer.Make(Monoid.String)(St)
module Monad : sig ... end