From 89dccec9ab1d2936b2f2ab05ec532c23863d7502 Mon Sep 17 00:00:00 2001
From: Jim Pryor
Date: Sun, 12 Dec 2010 09:33:45 -0500
Subject: [PATCH] point to monad_library
Signed-off-by: Jim Pryor
---
code/monads.ml | 3 +-
index.mdwn | 6 +++
monad_library.mdwn | 142 +++++++++++++++++++++++++++++++++++++++++++++++++++++
3 files changed, 150 insertions(+), 1 deletion(-)
create mode 100644 monad_library.mdwn
diff --git a/code/monads.ml b/code/monads.ml
index e1865a4a..54a32483 100644
--- a/code/monads.ml
+++ b/code/monads.ml
@@ -51,7 +51,8 @@
* - http://www.grabmueller.de/martin/www/pub/Transformers.pdf
* - http://en.wikibooks.org/wiki/Haskell/Monad_transformers
*
- * Licensing: MIT (if that's compatible with the ghc sources).
+ * Licensing: MIT (if that's compatible with the ghc sources this is partly
+ * derived from)
*)
exception Undefined
diff --git a/index.mdwn b/index.mdwn
index 0dd39e9b..1265dbbe 100644
--- a/index.mdwn
+++ b/index.mdwn
@@ -10,13 +10,17 @@ fourth floor at 10 Washington Place.
## Announcements ##
+
* We've added a page on [[Translating between OCaml Scheme and Haskell]]
* We've added some [commentary](/hints/assignment_6_commentary) on some common issues in your solutions to [[Assignment6]].
+* We've added a [[Monad Library]] for OCaml.
+
[[Older Announcements]]
##[[Lambda Evaluator]]##
@@ -27,6 +31,8 @@ the homework questions works correctly.
There is also now a [library](/lambda_library) of lambda-calculus
arithmetical and list operations, some relatively advanced.
+##[[Monad Library]]##
+
## Lecture Notes and Assignments ##
diff --git a/monad_library.mdwn b/monad_library.mdwn
new file mode 100644
index 00000000..398f2e52
--- /dev/null
+++ b/monad_library.mdwn
@@ -0,0 +1,142 @@
+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";;
+
+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 -> List_monad.plus (List_monad.unit a) (List_monad.unit (succ 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 `bind`s and `unit`s 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 ... *)
+ open Maybe_monad;;
+ ...
+
+ 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 *)
+ module R = Reader_monad(struct type env = string -> int end);;
+ (* 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 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]);;
+
+ 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
+
+ instead of:
+
+ 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)
+
+
+* 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.
+
+* All of these monads come with [[monad transformers]] too. To get a State monad wrapped around a Maybe monad, do this:
+
+ module S = State_monad(struct type store = int end);;
+ module SM = S.T(Maybe_monad);;
+
+ To get a Maybe monad wrapped around a State monad, do this instead:
+
+ 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:
+
+ 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 =
+
+ 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 `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.
+
+
--
2.11.0