Module Monads.Std

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

• 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

    • Make
    • Make2
    • Core
    • Core2
    • Minimal
    • Minimal2
  • 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

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)