How to Inspect Juli8's Monad modules for OCaml?
If you want to see the "signature" of some OCaml library or "module" --- that is, a list of the types it exports, and also of the types of function values (and other values) that it exports, you can do this.
If you're using a version of OCaml >= 4.02 (you can see the version from Sys.ocaml_version
), you can just type #show module_name;;
or #show name_of_module_type;;
. If you're using an older version of OCaml, read on.
If you know the name of the module but not the name of its module type, or if its module type doesn't have a name, then in older versions of OCaml you can do this:
module type SOMETHING = sig include module type of ModuleYouAreInterestedIn end
More commonly, though, you'll know that the module uses a specific named module type. In that case, here is what to do. An example is that modules you create using Monad.Reader(struct type env = ... end)
will all (more-or-less) have the module type named Monad.READER
. We can see an expansion of Monad.READER
by writing:
module type SOMETHING = sig include Monad.READER end
Then OCaml will respond:
module type SOMETHING =
sig
type env
type 'a t
type 'a result = env -> 'a
val run : 'a t -> 'a result
val map : ('a -> 'b) -> 'a t -> 'b t
val mid : 'a -> 'a t
val map2 : ('a -> 'b -> 'c) -> 'a t -> 'b t -> 'c t
val mapply : ('a -> 'b) t -> 'a t -> 'b t
val ( >> ) : 'a t -> 'b t -> 'b t
val ( << ) : 'a t -> 'b t -> 'a t
val ( >>= ) : 'a t -> ('a -> 'b t) -> 'b t
val ( >=> ) : ('a -> 'b t) -> ('b -> 'c t) -> 'a -> 'c t
val ( <=< ) : ('b -> 'c t) -> ('a -> 'b t) -> 'a -> 'c t
val join : 'a t t -> 'a t
val ignore : 'a t -> unit t
val seq : 'a t list -> 'a list t
val seq_ignore : unit t list -> unit t
val do_when : bool -> unit t -> unit t
val do_unless : bool -> unit t -> unit t
val ask : env t
val asks : (env -> 'a) -> 'a t
val shift : (env -> env) -> 'a t -> 'a t
end
Here I've reordered the elements a bit from OCaml's actual presentation to make it easier to explain them. First, there is the type of the env
that you will supply. In this signature it's listed abstractly (no concrete definition of the type is supplied, it's just declared that it exists), but in practice this type will be unified with the envionment type that you supply. Next there is the abstract or opaque type 'a t
. This is the main type of the Reader Monad. Behind the scenes it will be the same as the type 'a result
, that is a function from env
s to 'a
s. But OCaml keeps the type 'a t
opaque, and only exposes the actual implementation of the type when you apply the run
function to 'a t
values. The run
function is for most Monads just implemented as an identity function. Its effect is primarily to shift between the opaque type and the exposed concrete implementation of that type, named 'a result
. Note that even though the 'a t
s and 'a result
s will usually be represented by the same structures in OCaml's memory, our library insists that you only use the opaque 'a t
version for the monadic functions like map
and >>=
and so on. On the other hand, when you want to supply an actual starting env
to your monadic value, you have to use the 'a result
version you got from run
. This will not work:
# let xx = R.(mid 1) in xx env0;;
--
Error: This expression has type int R.t
This is not a function; it cannot be applied.
You need to instead say:
# let xx = R.(mid 1) in R.run xx env0;;
- : int = 1
Also there is no translation function that lets you take an 'a result
that you've built by hand and convert it to an 'a t
. You have to build your 'a t
s using the primitive operations that the Monad library provides for doing so. This is all discussed further elsewhere.
The next block of stuff in the Monad.READER
module type are functions common to all monads. Some monads (such as List and Option) additionally have mzero : 'a t
and some related operations. Finally, at the end are the operations specific to the Reader monad. These have mostly been given the same names as they have in Haskell's monad libraries. Here is a quick explanation:
ask
is a Reader monadic value that, when given anenv
, returns that veryenv
as its payload. So its type is anenv t
. And it is implemented asfun e -> e
.asks
is a variant ofask
. Haskell several times uses the convention that whereblah
is some operation that gives you some raw value,blahs
is a variant that gives you the result of applying some selector function or handler to the raw value. In this case,asks
takes a parameter, which is a function that operates onenv
s and gives some result.asks handler
then constitutes an'a t
, where'a
is the type of the handler's result. For example, if my environments are associations of some sort betweenchar
s andint
s, andlookup 'x'
is a function that takes anenv
as a further argument and returns whatint
that environment associates the char'x'
with, then:let getx = asks (lookup 'x')
will declare an
int t
that, when supplied with an environment, returns theint
that that environment associates thechar
'x'
with.shift
is a function that takes two arguments, an "env
-shifting" function and some Reader monadic value. It returns a new Reader monadic value that, when supplied with anenv
, will process the original monadic value only with theenv
shifted in the specified way. (Haskell calls theshift
operationlocal
, but I thought it would be a bit better to call itshift
--- enough of an improvement to justify changing the name.)For example, if
insert 'x' 1
is a function that operates onenv
s and gives a newenv
which now associates the char'x'
with1
, then:let letx xint body = shift (insert 'x' xint) body
will declare an operation that takes an
int
xint
and a monadic valuebody
, and evaluatesbody
in the contextlet x = xint in ...
. If we wanted instead to have a version which accepted not anint
, but rather anint
Reader, we could write instead:let letx xx body = xx >>= fun xint -> shift (insert 'x' xint) body
Examples of Using Reader
Here are some examples of using the Reader Monad modules to evaluate some simple expressions using bound variables. First, you could look at this Haskell code. It import
s the Control.Monad.Reader
library, which is where Haskell's Reader monad can be found. It declares an Env
type that we'll implement as a simple function from Char
s to Int
s. Then it defines an "empty" environment env0
, and a function insert
for adding new bindings to an env
. Next, we make a general function getint
that can create monadic values like the getx
illustrated above. We show how to use getx
and gety
to write monadic versions of y + x
and 3 + x
. Next, we define a letx
function as illustrated above (the second version, that takes a monadic value xx
as its argument). We show how to use this to write a monadic version of let x = 2 in y + x
. The final line of the file applies runReader
to the monadic value we've built --- this is Haskell's way of doing what we do in OCaml with run
, namely to remove the abstraction curtain and see what concrete type is really constituting our Reader Env a
s --- and we supply it with the empty environment, which will be sufficient since the expression we're interpreting has no free variables. Haskell binds the variable res
to the result. You can run this code inside ghci
by typing :load /path/to/reader1.hs
. (You may also be able to say :add ...
instead of :load ...
.) Then type res
, and Haskell will report back 5
.
This OCaml code does exactly the same thing only using our OCaml monad libraries instead. The biggest difference from the Haskell version is in the first few lines, where we have to generate a Reader monad module parameterized on the env
type that we intend to work with.
Here's a more complicated example. This time we want to be able to bind variables to lambda abstracts as well as to int
s. So our env
type will need to be more complex; it will have to associate char
s with a disjoint sum of int
s and lambda abstracts. Now what will the type of the lambda abstracts be? Let's just restrict our attention to abstracts whose bodies return int
s. But they might get those int
s by performing operations on bound variables, so the body expressions need to be interpreted monadically, as int Reader
s. We'll construe the whole lambda abstract as a function from int Reader
s (that is, the monadic values which are provided as arguments to the lambda abstract) to their results, so the lambda abstract will have the type int Reader -> int Reader
. In OCaml that will be int R.t -> int R.t
, and in Haskell Reader Env Int -> Reader Env Int
. Since variables can be bound to either int
s or to lambda abstracts, we declare our environments like this in OCaml:
type bound = Int of int | Fun of (int R.t -> int R.t)
type env = char -> bound
and like this in Haskell:
data Bound = Int Int | Fun (Reader Env Int -> Reader Env Int)
type Env = Char -> Bound
There is a tricky issue in the OCaml case, though, in that when working with OCaml, we have to generate our R
Reader monad module, parameterized on the type of the env
, but here we see that we need access to the type 'a R.t
from the generated R
module in order to declare the env
. Fortunately, it is possible to do this, by having the module that declares the env
and the module that has our Reader monad in it be mutually recursively defined. The first few lines of this OCaml code do the tricky work.
After that, our Haskell code and OCaml code proceed basically the same, allowing for the difference in syntax and vocabulary between Haskell and OCaml. The getint
function works like before, except now we have to pull the int
out from behind the Int
constructor of our disjoint sum type bound
. We have a parallel getfun
function. Then we interpret the variable x
using the monadic value getint 'x'
, and we interpret the variable f
using the monadic value getfun 'f'
. The letx
operation is similarly adjusted, and we also have a parallel letf
.
The really new thing in this code, compared to the previous example, is our definition of a monadic value to interpret the lambda abstract \y -> y + x
, that f
gets bound to. And also our interpretation of the expression f 3
, which looks up a function that the variable f
is bound to, and then applies it to (a monadically-lifted version of) 3
. (We have the argument be monadically lifted so that we could also say, for example, f y
.) You can examine the code to see how we do these things.
OK, what else is in these Monad modules?
I won't give an exhaustive list here. But here is the output of module type SOMETHING = sig include Monad.BLAH end
for some of the BLAH
s:
module type STATE =
sig
type store
type 'a t
type 'a result = store -> 'a * store
(* plus the other usual monadic stuff, and: *)
val get : store t
val gets : (store -> 'a) -> 'a t
val modify : (store -> store) -> unit t
val put : store -> unit t
end
The store
type has to be provided by you, when you generate the module, similarly to as in the Reader monad. The 'a result
type shows the real definition of an 'a State
type, otherwise kept opaque as 'a t
. Instead of the special operations ask
and so on that the Reader monad has, State has the operations get
, gets
, modify
, and put
. The first two work just like ask
and asks
did for the Reader monad. The third one works similarly to shift
for the Reader monad, with the crucial difference that the rebinding that shift
introduces is in effect only for the body
argument of the shift
operation. Outside of that body
, we revert to the originally supplied env
. But notice that modify
doesn't take any body
argument. modify
introduces changes to the supplied store
that once introduced stay in place, until we manually change them again. Thus with the Reader monad you'd do things like this:
R.(xx >>= fun x -> ... shift (insert ...) body >>= fun y -> (* now we're using the unshifted env *) ...)
With the State monad you'd instead do things like this:
S.(xx >>= fun x -> ... modify (fun old_store -> new_store) >>= fun () -> (* we continue using the modified store, until it's modified once again *) ...)
Since the pattern ... >>= fun () -> ...
or ... >>= fun variable_you_never_use -> ...
occurs often when working with monads, there's a shorthand: you can instead say ... >> ...
, with >>
in place of >>= fun pattern ->
.
Here's another monad module signature:
module type WRITER =
sig
type log
type 'a t
type 'a result = 'a * log
(* plus the other usual monadic stuff, and: *)
val listen : 'a t -> ('a * log) t
val listens : (log -> 'b) -> 'a t -> ('a * 'b) t
val tell : log -> unit t
val censor : (log -> log) -> 'a t -> 'a t
end
Writer is very similar to Reader: first, it is parameterized on something like an env
, here called a log
. (A typical implementation for log
would be the string
type.) Second, the Writer operations listen
, listens
, and censor
parallel the Reader operations ask
, asks
, and shift
. But one difference is that with Writer, you cannot choose what initial env
(log
) to supply. You always begin with the empty
log
(such as ""
for string
s). A second difference is that the types differ. Compare:
module type READER =
sig
...
val ask : env t
val asks : (env -> 'a) -> 'a t
val shift : (env -> env) -> 'a t -> 'a t
end
Whereas Writer's censor
and Reader's shift
have isomorphic types, there is some extra complextity to Writer's listen
and listens
, compared to ask
and asks
. What this extra complexity means is that for Writer
, listening happens only in a local context. You can't listen
to what got written to the log before you installed your listen
ing tap. But you can return payloads that are dependent on what you've heard in the local context.
Unlike Reader, Writer also has a tell
operation, which is akin to the put
operation in the State monad. The difference is that the tell
function takes a log
as argument and appends that to the existing log
. You can't erase or overwrite elements already in the log
; you can only append to it. However, if you like, you can censor
the log generated by any local context. (Inside the local context, the log isn't yet censored; the censoring only affects what's seen downstream as the contributions made by that context to the log.)
Here's a complex example that illustrates this. First we will use the Juli8 helper function String.upper
and a second helper function that we define like this:
let bracket log = "{" ^ log ^ "}"
Next, we construct some monadic values and reveal them at the end using run
:
module W = Monad.Writer(struct
type log = string
let empty = ""
let append s1 s2 = if s1 = "" then s2 else if s2 = "" then s1 else s1 ^ " " ^ s2
end)
W.(let xx = tell "one" >> listens bracket (tell "two" >> mid 10) in
let yy = censor String.upper (tell "zero" >> listens bracket xx) in
let zz = tell "before" >> yy >>= fun y -> tell "after" >> mid y in
run ...);;
The monadic value xx
writes "one"
to the log, then discards the resulting ()
payload (it continues >> ...
rather than >>= fun var -> ...
). Then we have a use of listens
. This will evaluate its body tell "two" >> mid 10
and return as payload a pair of the body's original payload and a bracket
ed copy of the local log. Thus the payload of listens bracket (tell "two" >> mid 10)
will be (10, "{two}")
. Its log will be "two"
. The "one"
that got written to the log earlier isn't accessible to listens
; however it does stay in the overall log, to which the listens ...
construction contributes. Hence the result of run xx
, showing first the payload and then the log, would be:
- : (int * string) W.result = ((10, "{two}"), "one two")
Now yy
uses that xx
monadic value to illustrate the use of censor
. Here we have censor
apply String.upper
to the log generated in the local context it's applied to, hence the result of run yy
would be:
- : ((int * string) * string) W.result = (((10, "{two}"), "{one two}"), "ZERO ONE TWO")
The final value zz
shows what happens to entries written to the log before and after the censor
ing that occurs in yy
, namely nothing. That is, run zz
is:
- : ((int * string) * string) W.result = (((10, "{two}"), "{one two}"), "before ZERO ONE TWO after")
Let's look at some more familiar monad signatures. Here is one:
module type OPTION =
sig
type 'a t
type 'a result = 'a option
(* plus the other usual monadic stuff, and: *)
val mzero : 'a t
val guard : bool -> unit t
val test : ('a option -> bool) -> 'a t -> 'a t
end
That is what's exposed in the Monad.Option
module. In the non-monadic Option
module, there are many more operations. Similarly, List
exposes many more operations than Monad.List
does. The Monad.List
module restricts us to just the monadic interface. Unlike Reader and State and Writer, the Option and List monads don't need to be parameterized on environments or anything else of that sort. The Option monad has three additional monadic operations, analogues of which are also all present in List. First, there is the mzero
monadic value, implemented as None
and satisfying the Monad Laws for mzero
we explained elsewhere. The key one to remember is that mzero
aborts a chain of composed Kleisli functions. That is, mzero >>= anything
is always mzero
. guard
takes a boolean argument and if it is false, gives mzero
. If the argument is true, it just gives the uninteresting mid ()
, hence the typical way to use guard
is as:
module O = Option;;
O.(guard some_bool_expr >> more_monadic_stuff)
If some_bool_expr
is true, then this expression will ignore the ()
payload of guard some_bool_expr
and go on to compute more_monadic_stuff
; if it's false, then the whole chain gets ignored because of the distinctive behavior of mzero
.
The third special operation in the Option monad is test
. This lets you supply a function that takes an ordinary 'a option
type (that is, one where the abstraction curtain imposed by the 'a O.t
type is not in place) and returns a bool
. Then you take an Option monadic value (one where the abstraction curtain is in place). OCaml will temporarily remove the abstraction curtain on the second argument and see how the function you supplied assesses it. If the result is true
, then the result is identical to that Option monadic value, unaltered. If the result is false
, then the result is mzero
. (For those of you who know Frank Veltman's work on dynamic semantics for epistemic modals, this test
(or the version of it for sets of worlds) is a key component.)
Here is the List monadic interface:
module type LIST =
sig
type 'a t
type 'a result = 'a list
(* plus the other usual monadic stuff, and: *)
val mzero : 'a t
val guard : bool -> unit t
val test : ('a list -> bool) -> 'a t -> 'a t
val ( ++ ) : 'a t -> 'a t -> 'a t
val pick : 'a t -> ('a * 'a t) t
end
The mzero
and guard
and test
operations work analogously to the ones in the Option monad. The ++
(infix) operation is like List.append
(OCaml also uses @
for that), with the difference that ++
is defined on the opaque List monadic values of type 'a Monad.List.t
, not the OCaml native lists (which aren't behind an abstraction curtain). In Haskell, ++
works on either native lists or elements of the List monad, because Haskell doesn't distinguish them. Haskell doesn't impose an abstraction curtain in the case of its List and Maybe monads. pick
is an operation that transforms (the opaque version of) [1; 2; 3]
to (the opaque version of) [(1, [2; 3]); (2, [1; 3]); (3, [1; 2])]
.
Here is another monadic interface:
module type TREE =
sig
type 'a tree
type 'a t
type 'a result = 'a tree
(* plus the other usual monadic stuff, and: *)
val ( ++ ) : 'a t -> 'a t -> 'a t
end
This is the signature/module type for the Monad.LTree module. ("LTree" for leaf-labeled trees.)
You can create leaf-only trees using the monadic function mid
. You can join two trees together using the function ++
, paralleling the one in List. Note that in the Tree case, unlike the List case, ++
is not associative: xx ++ (yy ++ zz)
is not the same as (xx + yy) ++ zz
. Nor is there any mzero
for trees as implemented by this module.
Acknowledgements
Our library is largely based on the mtl library distributed with the Haskell Platform. That in turn was inspired by Mark Jones' 1995 paper Functional Programming with Overloading and Higher-Order Polymorphism.
I've also been helped in various ways by posts and direct feedback from Oleg Kiselyov and Chung-chieh Shan. The following were also useful:
- http://pauillac.inria.fr/~xleroy/mpri/progfunc/
- Ken Shan "Monads for natural language semantics" http://arxiv.org/abs/cs/0205026v1
- http://www.grabmueller.de/martin/www/pub/Transformers.pdf
- http://en.wikibooks.org/wiki/Haskell/Monad_transformers
Comparisons with Haskell
Some comparisons with the Haskell monadic libraries, which Juli8 mostly follows.
In Haskell, the 'a Reader.t
monadic type would be defined something like this:
newtype Reader a = Reader { runReader :: env -> a }
(For simplicity, I'm suppressing the fact that Reader
is also parameterized
on what type env
is.) This creates a type wrapper around env -> a
, so that Haskell will
distinguish between values that have been specifically designated as
being of type Reader a
, and common-garden values of type env -> a
.
To lift an aribtrary expression E
of type env -> a
into an Reader a
,
you do this:
Reader { runReader = E }
or use any of the following equivalent shorthands:
Reader (E)
Reader $ E
To drop an expression R
of type Reader a
back into an env -> a
, you do
one of these:
runReader (R)
runReader $ R
The newtype
in the type declaration ensures that Haskell does this all
efficiently: though it regards E
and R
as type-distinct, their underlying
machine implementation is identical and doesn't need to be transformed when
lifting/dropping from one type to the other.
Now, you could also declare monads as record types in OCaml, too, but doing so would introduce an extra level of machine representation, and lifting/dropping from the one type to the other wouldn't be free like it is in Haskell. Also it would be syntactically more complex.
So Juli8 instead encapsulates the monadic values by making their implementation types "private" or abstract or opaque. We get the same result: OCaml won't let you freely interchange 'a Reader.t
s with env -> 'a
s. The Juli8 internals can see that these are equivalent, but refuses to permit code outside of the library to rely on that assumption. Instead, you have to use the run
operation (like Haskell's runReader
) to convert the opaque monadic values to ones whose type is exposed to you.