code/monad_library.mdwn

   1 We've written a full-featured [OCaml Monad Library](/code/monads.ml). To use it, download the file and then in your OCaml session or file, write:
   2
   3         # #use "path/to/monads.ml";;
   4
   5 That's not the official, preferred way to load OCaml libraries, but it's quick and easy.
   6
   7 Some comments on the design of this library.
   8
   9 *       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`.
  10
  11 *       It gets tedious to write things like:
  12
  13                 List_monad.bind (List_monad.unit 1) (fun a ->
  14                    List_monad.plus
  15                      (List_monad.unit a)
  16                      (List_monad.unit (succ a)));;
  17
  18         So instead, we recommend the following shortcut:
  19
  20                 List_monad.(bind (unit 1) (fun a -> plus (unit a) (unit (succ a))));;
  21
  22         This is equivalent:
  23
  24                 let open List_monad
  25                 in let f = fun a -> plus (unit a) (unit (succ a))
  26                 in bind (unit 1) f;;
  27
  28         If you know you're only going to be using `bind`s and `unit`s from a single monad, you can also do this:
  29
  30                 open List_monad;; (* now `bind` always refers to List_monad.bind, and so on *)
  31                 bind (unit 1) ...
  32                 (* later you want to use a different monad's operations, so ... *)
  33                 open Maybe_monad;;
  34                 ...
  35
  36         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.
  37
  38 *       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:
  39
  40                 (* we want to implements env as a function from strings to ints *)
  41                 module R = Reader_monad(struct type env = string -> int end);;
  42                 (* now we can use R as a Reader monad module *)
  43                 (R.unit 1, R.unit false, R.unit "string");;
  44
  45         Similarly, to use a State monad, you have to specify the type of the store:
  46
  47                 module S = State_monad(struct type store = int end);;
  48                 S.unit 1;;
  49                 S.get;; (* this monadic value would retrieve the current store *)
  50                 S.put 20;; (* would install 20 as the new store *)
  51                 S.puts succ;; (* would apply succ to the current store, whatever it is *)
  52                 let u = S.(unit 1 >>= fun a ->
  53                     put 20 >>= fun _ ->
  54                     puts succ >>= fun _ ->
  55                     get >>= fun b ->
  56                     unit [a;b]);;
  57
  58         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.
  59
  60         This can be economized somewhat by using the shorthand:
  61
  62                 u >> v
  63
  64         instead of:
  65
  66                 u >>= fun _ -> v.
  67
  68         So we'd have:
  69
  70                 let u = S.(unit 1 >>= fun a ->
  71                     put 20 >>
  72                     puts succ >>
  73                     get >>= fun b ->
  74                     unit [a;b]);;
  75
  76         How can we supply an initial store and get this computation started? You do it like this:
  77
  78                 # let initial_store = 0
  79                 in S.run u initial_store;;
  80                 - : S.store list * S.store = ([1; 21], 21)
  81
  82         Our wrapped value at the end is `[1; 21]`, and the current store is `21`. Compare also:
  83
  84                 # S.(run(let u = puts succ >> get in
  85                         u >>= fun a1 ->
  86                         u >>= fun a2 ->
  87                         u >>= fun a3 ->
  88                         unit [a1;a2;a3])) 0;;
  89                 - : S.store list * S.store = ([1; 2; 3], 3)
  90                 # S.(run(let u = puts succ >> get in sequence [u;u;u])) 0;;
  91                 - : S.store list * S.store = ([1; 2; 3], 3)
  92
  93
  94 *       The monads available are:
  95
  96         *       `Identity_monad`
  97         *       `Maybe_monad`
  98         *       `List_monad`
  99         *       `Reader_monad` (has to be parameterized as above)
 100         *       `State_monad` (has to be parameterized as above)
 101         *       `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)
 102         *       `Writer_monad` (has to be parameterized on the type of the written data; use `Writer1` as a simple predefined case)
 103         *       `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`)
 104         *       `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)
 105         *       `Tree_monad` (leaf-labeled, binary trees)
 106         *       and of course, `Continuation_monad`, with `callcc`, `reset`, `shift` and `abort` operations.
 107
 108 *       All of these monads come with [[monad transformers]] too. To get a State monad wrapped around a Maybe monad, do this:
 109
 110                 module S = State_monad(struct type store = int end);;
 111                 module SM = S.T(Maybe_monad);;
 112
 113         To get a Maybe monad wrapped around a State monad, do this instead:
 114
 115                 module MS = Maybe_monad.T(S);;
 116
 117         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:
 118
 119                 MS.(... >> elevate (S.puts succ) >> ...)
 120
 121         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.
 122
 123 *       If you look at the types of the monadic values:
 124
 125                 # let u = S.(unit 1);;
 126                 val u : ('_a, int) S.m = <abstr>
 127
 128         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)?
 129
 130         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:
 131
 132                 type ('r,'b) m = ('b -> 'r) -> 'r
 133
 134         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`.
 135
 136
 137 *       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:
 138
 139                 # let u = S.(unit 10 >>= fun a -> puts succ >> unit a);;
 140                 # S.run u 0;;
 141                 - : int * S.store = (10, 1)
 142
 143         This will not work:
 144
 145                 # u 0;;
 146                 Error: This expression is not a function; it cannot be applied
 147
 148         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.
 149
 150         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.
 151
 152 *       The same design is used in the `Ref_monad`. Keys into the store are implemented as `int`s, but their type is kept hidden (the computing community says "abstract"), so that the outside world can't do anything with the keys but
 153 compare them for equality and use them for derefs, and so on.
 154
 155
 156 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
 157 [Functional Programming with Overloading and Higher-Order Polymorphism](http://web.cecs.pdx.edu/~mpj/pubs/springschool.html).
 158  I've also been helped in
 159  various ways by posts and direct feedback from Oleg Kiselyov and
 160  Chung-chieh Shan. The following were also useful:
 161
 162  *      <http://pauillac.inria.fr/~xleroy/mpri/progfunc/>
 163  *      Ken Shan "Monads for natural language semantics" <http://arxiv.org/abs/cs/0205026v1>
 164  *      <http://www.grabmueller.de/martin/www/pub/Transformers.pdf>
 165  *      <http://en.wikibooks.org/wiki/Haskell/Monad_transformers>
 166
 167