week9 reference tweak
[lambda.git] / monad_library.mdwn
index 398f2e5..1761e61 100644 (file)
@@ -1,6 +1,6 @@
 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:
 
-       #use "path/to/monads.ml";;
+       # #use "path/to/monads.ml";;
 
 That's not the official, preferred way to load OCaml libraries, but it's quick and easy.
 
@@ -10,7 +10,10 @@ Some comments on the design of this library.
 
 *      It gets tedious to write things like:
 
-               List_monad.bind (List_monad.unit 1) (fun a -> List_monad.plus (List_monad.unit a) (List_monad.unit (succ a)));;
+               List_monad.bind (List_monad.unit 1) (fun a ->
+                  List_monad.plus
+                    (List_monad.unit a)
+                    (List_monad.unit (succ a)));;
 
        So instead, we recommend the following shortcut:
 
@@ -43,11 +46,14 @@ Some comments on the design of this library.
 
                module S = State_monad(struct type store = int end);;
                S.unit 1;;
-               S.get;; (* this monadic value retrieves the current store *)
-               S.put 20;; (* installs 20 as the new store *)
-               S.puts succ;; (* applies 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]);;
+               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.
 
@@ -61,8 +67,11 @@ Some comments on the design of this library.
 
        So we'd have:
 
-               let u =
-                       S.(unit 1 >>= fun a -> put 20 >> puts succ >> get >>= fun b -> unit [a;b]);;
+               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:
 
@@ -72,7 +81,11 @@ Some comments on the design of this library.
 
        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.(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)
@@ -80,17 +93,17 @@ Some comments on the design of this library.
 
 *      The monads available are:
 
-       *       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)
-       *       Leaf_monad (leaf-labeled, binary trees)
-       *       and of course, Continuation_monad, with `callcc`, `reset`, `shift` and `abort` operations.
+       *       `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.
 
 *      All of these monads come with [[monad transformers]] too. To get a State monad wrapped around a Maybe monad, do this:
 
@@ -101,7 +114,7 @@ Some comments on the design of this library.
 
                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 "lift" those operations into the MaybeT interface. The way you do that is like this:
+       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) >> ...)
 
@@ -112,7 +125,7 @@ Some comments on the design of this library.
                # 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)?
+       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:
 
@@ -137,6 +150,18 @@ Some comments on the design of this library.
        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 `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
-compare them for equality and use them for derefs/and so on.
+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](http://web.cecs.pdx.edu/~mpj/pubs/springschool.html).
+ 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>