Deconstructing a Monad Tutorial

OCaml programmers are bimodal, some of them have learned from tutorials and have gone on to write significant programs that would have been awkward in their previous languages. Other users will have learned modern academic type theory and brought from that patterns that are amplified but not explained in the OCaml literature.

I aim at a tutorial for those who want to see a particular monad before we generalize.

This page meets us partway. It fails for me because it assumes knowledge of OCaml that is not, I think, in what I take to be the official OCaml Reference. Perhaps I am wrong. I will try to resolve this question. I have information from sources outside the document which may guide me to figure this out. I probably learned any such information from Pierce’s wonderful book. That book, by its nature however, deals in general notions and syntaxes whereas we need precise rules for OCaml which I have not seen in print.

Consider the text of their brief “module type” example:

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

After many experiments I propose some additional information about OCaml that should go somewhere in the official manual. In the case at hand the first “t” in the code snippet is the defining occurrence and the type parameters with apostrophes each have a scope of one line of text.

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

module OptionMonad = struct
    type 'a t = 'a option

    let bind opt f =
        match opt with
            | Some(x) -> f x
            | None -> None

    let return x = Some x
end;;

module Aa = (OptionMonad : MonadRequirements);;
module Aa : MonadRequirements

We have another documentation problem. There is a global name space in which the type constructor option lives. It is not in the list of keywords, nor mentioned among the pervasives. The type constructor ‘option’ is introduced in the section on built-in types.

‘type constructor’s at Inria

Google Search incantation:
site:caml.inria.fr/pub/docs/manual-ocaml "type constructor"
as a Name. Significantly there is no category for types in this list of sorts of names.

This section describes a syntax that provides a defining occurrence of a ‘type constructor’ but where the scope is an expression. In that expression the identifier is taken as an ‘abstract type’.

a ‘constructed type’ among Type Expressions

Here we see the text “Type definitions bind type constructors to data types” which confounds me. I thought that “list” within the type “int list” was a type constructor; that is I thought that the type “int list” was constructed by “list” by taking the type “int” as a type argument.

Also the text “A simple definition consists in a lowercase identifier, possibly preceded by one or several type parameters, … ” which refers to the “type-parms” as type parameters. Parameters are a familiar notion syntactically and this sounds like a defining occurrence of such a parameter, but we shall see.

Caml Light

Involved with type expressions

“constr-name ” at Inria

constr-decl??

as exception

Note the text here: “The constructor declaration constr-name of typexpr declares the name constr-name as a non-constant constructor, whose argument has type typexpr. ”

There seems to be an OCaml ‘constructor’ notion that I am missing. See “Variants” here for a clear description of constructors which I take to be limited to value constructors.