# #use "path/to/monads.ml";;


That's not the official, preferred way to load OCaml libraries, but it's quick and easy.

Some comments on the design of this library.

• First off, the different monads are encapsulated in modules. So you won't say list_bind and so on. Instead, you'll say List_monad.bind.

• It gets tedious to write things like:

List_monad.bind (List_monad.unit 1) (fun a ->


So instead, we recommend the following shortcut:

List_monad.(bind (unit 1) (fun a -> plus (unit a) (unit (succ a))));;


This is equivalent:

let open List_monad
in let f = fun a -> plus (unit a) (unit (succ a))
in bind (unit 1) f;;


If you know you're only going to be using binds and units from a single monad, you can also do this:

open List_monad;; (* now bind always refers to List_monad.bind, and so on *)
bind (unit 1) ...
(* later you want to use a different monad's operations, so ... *)
...


But we recommend using one of the first two forms above, instead. It's easy to lose track of which monad you've loaded at the top level in this way; and if you want to combine operations from different monads in a single expression, you'll have to use the first form, anyway.

• Some of the monads are parameterized. For instance, to use the Reader monad, you have to first specify what is the type of the env you propose to use. You'd do that like this:

(* we want to implements env as a function from strings to ints *)
(* now we can use R as a Reader monad module *)
(R.unit 1, R.unit false, R.unit "string");;


Similarly, to use a State monad, you have to specify the type of the store:

module S = State_monad(struct type store = int end);;
S.unit 1;;
S.get;; (* this monadic value would retrieve the current store *)
S.put 20;; (* would install 20 as the new store *)
S.puts succ;; (* would apply succ to the current store, whatever it is *)
let u = S.(unit 1 >>= fun a ->
put 20 >>= fun _ ->
puts succ >>= fun _ ->
get >>= fun b ->
unit [a;b]);;


The monadic value u we've defined here binds a series of operations to an initial unit 1. The effect of these operations is to save the wrapped 1 in variable a, discard the current store and install 20 in its place, increment the current store, retrieve the current store and make that the wrapped value, and finally deliver a unit [a;b] where b is the current wrapped value and a is the 1 we saved earlier.

This can be economized somewhat by using the shorthand:

u >> v


u >>= fun _ -> v.


So we'd have:

let u = S.(unit 1 >>= fun a ->
put 20 >>
puts succ >>
get >>= fun b ->
unit [a;b]);;


How can we supply an initial store and get this computation started? You do it like this:

# let initial_store = 0
in S.run u initial_store;;
- : S.store list * S.store = ([1; 21], 21)


Our wrapped value at the end is [1; 21], and the current store is 21. Compare also:

# S.(run(let u = puts succ >> get in
u >>= fun a1 ->
u >>= fun a2 ->
u >>= fun a3 ->
unit [a1;a2;a3])) 0;;
- : S.store list * S.store = ([1; 2; 3], 3)
# S.(run(let u = puts succ >> get in sequence [u;u;u])) 0;;
- : S.store list * S.store = ([1; 2; 3], 3)


• Identity_monad
• Maybe_monad
• List_monad
• Reader_monad (has to be parameterized as above)
• State_monad (has to be parameterized as above)
• Ref_monad (a version of State_monad with a structured store, and custom operations for creating new cells in the store, and getting or changing the values of existing cells)
• Writer_monad (has to be parameterized on the type of the written data; use Writer1 as a simple predefined case)
• Error_monad, with throw err and catch u handler_function operations (this has to be parameterized on the type of err; use Failure as a simple predefined case, where type err = string)
• IO_monad (you don't need this in OCaml, but it works analagously to the IO monad in Haskell, so it's handy for working with Haskell-written algorithms in OCaml)
• Tree_monad (leaf-labeled, binary trees)
• and of course, Continuation_monad, with callcc, reset, shift and abort operations.

module S = State_monad(struct type store = int end);;


module MS = Maybe_monad.T(S);;


Note that those two layered monads will have slightly different behavior. See our discussion of monad transformers for details. Also, the outermost monad is the one whose operations are most exposed. If you want to use any of the State-specific operations (like puts succ) in the MS monad, you'll have to "elevate" those operations into the MaybeT interface. The way you do that is like this:

MS.(... >> elevate (S.puts succ) >> ...)


The Haskell libraries use lift instead of elevate. (They use liftM and liftM2 for what we've called lift and lift2. They also call liftM fmap.) This name lift is already over-loaded enough, so we chose to use elevate here. In our usage, lift (and lift2) bring non-monadic operations into a monad; elevate brings monadic operations from a wrapped monad out into the wrapping monad.

• If you look at the types of the monadic values:

# let u = S.(unit 1);;
val u : ('_a, int) S.m = <abstr>


You'll notice that the monadic type S.m is parameterized on two type arguments: one of them, int, is the type of the wrapped value. What is the other one ('_a in the above example)?

The answer is that for most of the monads this second type argument is an idle wheel. The Continuation monad needs both of the type arguments, though, since its monadic type is implemented as:

type ('r,'b) m = ('b -> 'r) -> 'r


and there both 'r and 'b need to be free type variables. Since we want to allow you to layer Continuation monads with the others, it vastly simplified the library to make all of the monadic types take two type parameters, even though the second will only be used by a Continuation monad you may have stacked in the monadic bundle you're using. You can pretty much ignore this; think of the S.(unit 1) as though it just had the type int S.m.

• The implementation of most monadic types is hidden. Above, when we wanted to supply an initial_store to a value u of type ('a,'b) S.m, we did this:

# let u = S.(unit 10 >>= fun a -> puts succ >> unit a);;
# S.run u 0;;
- : int * S.store = (10, 1)


This will not work:

# u 0;;
Error: This expression is not a function; it cannot be applied


Although the library knows that an ('a,'b) S.m type is implemented as store -> ('b * store), it doesn't expose that fact to the outside world. To get at the implementation, you have to use the run operation. That translates the opaque ('a,'b) S.m type into store -> ('b * store) type that you can use as a function.

So the run operation lets you get from the hidden type to its actual implementation. What about the other way around? By design, there is no way to do this. You can't just hand the libary an arbitrary store -> ('b * store) and say it's an ('a,'b) S.m. Instead, you should use the primitive operations in your S module---unit, bind, get, puts and so on---to build up the ('a,'b) S.m you want.

• The same design is used in the Ref_monad. Keys into the store are implemented as ints, but their type is kept hidden (the computing community says "abstract"), so that the outside world can't do anything with the keys but compare them for equality and use them for derefs, and so on.

Acknowledgements: Our library is largely based on the mtl library distributed with the Glasgow Haskell Compiler. 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: