X-Git-Url: http://lambda.jimpryor.net/git/gitweb.cgi?p=lambda.git;a=blobdiff_plain;f=week7.mdwn;h=abb6cfe82690c24556155b8dcf0b730bddcc2535;hp=8daff8a09a02adbc31a74a7a40465597d8b42e7f;hb=c48521340337270a5b9bb439045af44ff0dc2b5a;hpb=0a621c3ef165f707ce3af6ca684fe5f8f8378316

diff --git a/week7.mdwn b/week7.mdwn
index 8daff8a0..abb6cfe8 100644
--- a/week7.mdwn
+++ b/week7.mdwn
@@ -58,12 +58,11 @@ operations.  So we have to jack up the types of the inputs:
 
 <pre>
 let div' (u:int option) (v:int option) =
-  match v with
+  match u with
 	  None -> None
-    | Some 0 -> None
-	| Some y -> (match u with
-					  None -> None
-                    | Some x -> Some (x / y));;
+	| Some x -> (match v with
+				  Some 0 -> None
+				| Some y -> Some (x / y));;
 
 (*
 val div' : int option -> int option -> int option = <fun>
@@ -237,7 +236,7 @@ that provides at least the following three elements:
 	most straightforward way to lift an ordinary value into a monadic value
 	of the monadic type in question.
 
-*	Thirdly, an operation that's often called `bind`. This is another
+*	Thirdly, an operation that's often called `bind`. As we said before, this is another
 	unfortunate name: this operation is only very loosely connected to
 	what linguists usually mean by "binding." In our option/maybe monad, the
 	bind operation is:
@@ -366,8 +365,8 @@ Just like good robots, monads must obey three laws designed to prevent
 them from hurting the people that use them or themselves.
 
 *	**Left identity: unit is a left identity for the bind operation.**
-	That is, for all `f:'a -> 'a m`, where `'a m` is a monadic
-	type, we have `(unit x) * f == f x`.  For instance, `unit` is itself
+	That is, for all `f:'a -> 'b m`, where `'b m` is a monadic
+	type, we have `(unit x) >>= f == f x`.  For instance, `unit` is itself
 	a function of type `'a -> 'a m`, so we can use it for `f`:
 
 		# let unit x = Some x;;
@@ -377,14 +376,17 @@ them from hurting the people that use them or themselves.
 
 	The parentheses is the magic for telling OCaml that the
 	function to be defined (in this case, the name of the function
-	is `*`, pronounced "bind") is an infix operator, so we write
-	`u * f` or `( * ) u f` instead of `* u f`. Now:
+	is `>>=`, pronounced "bind") is an infix operator, so we write
+	`u >>= f` or equivalently `( >>= ) u f` instead of `>>= u
+	f`.
 
 		# unit 2;;
 		- : int option = Some 2
 		# unit 2 >>= unit;;
 		- : int option = Some 2
 
+	Now, for a less trivial instance of a function from `int`s to `int option`s:
+
 		# let divide x y = if 0 = y then None else Some (x/y);;
 		val divide : int -> int -> int option = <fun>
 		# divide 6 2;;
@@ -402,10 +404,12 @@ them from hurting the people that use them or themselves.
 
 		(u >>= f) >>= g == u >>= (fun x -> f x >>= g)
 
-	If you don't understand why the lambda form is necessary (the "fun
-	x" part), you need to look again at the type of `bind`.
+	If you don't understand why the lambda form is necessary (the
+	"fun x -> ..." part), you need to look again at the type of `bind`.
 
-	Some examples of associativity in the option monad:
+	Some examples of associativity in the option monad (bear in
+	mind that in the Ocaml implementation of integer division, 2/3
+	evaluates to zero, throwing away the remainder):
 
 		# Some 3 >>= unit >>= unit;; 
 		- : int option = Some 3
@@ -423,7 +427,7 @@ them from hurting the people that use them or themselves.
 		- : int option = None
 
 Of course, associativity must hold for *arbitrary* functions of
-type `'a -> 'a m`, where `m` is the monad type.  It's easy to
+type `'a -> 'b m`, where `m` is the monad type.  It's easy to
 convince yourself that the `bind` operation for the option monad
 obeys associativity by dividing the inputs into cases: if `u`
 matches `None`, both computations will result in `None`; if
@@ -447,41 +451,38 @@ More details about monads
 If you studied algebra, you'll remember that a *monoid* is an
 associative operation with a left and right identity.  For instance,
 the natural numbers along with multiplication form a monoid with 1
-serving as the left and right identity.  That is, temporarily using
-`*` to mean arithmetic multiplication, `1 * u == u == u * 1` for all
+serving as the left and right identity.  That is, `1 * u == u == u * 1` for all
 `u`, and `(u * v) * w == u * (v * w)` for all `u`, `v`, and `w`.  As
 presented here, a monad is not exactly a monoid, because (unlike the
 arguments of a monoid operation) the two arguments of the bind are of
 different types.  But it's possible to make the connection between
 monads and monoids much closer. This is discussed in [Monads in Category
-Theory](/advanced_notes/monads_in_category_theory).
+Theory](/advanced_topics/monads_in_category_theory).
 See also <http://www.haskell.org/haskellwiki/Monad_Laws>.
 
 Here are some papers that introduced monads into functional programming:
 
-*	[Eugenio Moggi, Notions of Computation and Monads](http://www.disi.unige.it/person/MoggiE/ftp/ic91.pdf): Information and Computation 93 (1) 1991.
+*	[Eugenio Moggi, Notions of Computation and Monads](http://www.disi.unige.it/person/MoggiE/ftp/ic91.pdf): Information and Computation 93 (1) 1991. Would be very difficult reading for members of this seminar. However, the following two papers should be accessible.
+
+*	[Philip Wadler. The essence of functional programming](http://homepages.inf.ed.ac.uk/wadler/papers/essence/essence.ps):
+invited talk, *19'th Symposium on Principles of Programming Languages*, ACM Press, Albuquerque, January 1992.
+<!--	This paper explores the use monads to structure functional programs. No prior knowledge of monads or category theory is required.
+	Monads increase the ease with which programs may be modified. They can mimic the effect of impure features such as exceptions, state, and continuations; and also provide effects not easily achieved with such features. The types of a program reflect which effects occur.
+	The first section is an extended example of the use of monads. A simple interpreter is modified to support various extra features: error messages, state, output, and non-deterministic choice. The second section describes the relation between monads and continuation-passing style. The third section sketches how monads are used in a compiler for Haskell that is written in Haskell.-->
 
 *	[Philip Wadler. Monads for Functional Programming](http://homepages.inf.ed.ac.uk/wadler/papers/marktoberdorf/baastad.pdf):
 in M. Broy, editor, *Marktoberdorf Summer School on Program Design
 Calculi*, Springer Verlag, NATO ASI Series F: Computer and systems
 sciences, Volume 118, August 1992. Also in J. Jeuring and E. Meijer,
 editors, *Advanced Functional Programming*, Springer Verlag, 
-LNCS 925, 1995. Some errata fixed August 2001.  This paper has a great first
-line: **Shall I be pure, or impure?**
+LNCS 925, 1995. Some errata fixed August 2001.
 <!--	The use of monads to structure functional programs is described. Monads provide a convenient framework for simulating effects found in other languages, such as global state, exception handling, output, or non-determinism. Three case studies are looked at in detail: how monads ease the modification of a simple evaluator; how monads act as the basis of a datatype of arrays subject to in-place update; and how monads can be used to build parsers.-->
 
-*	[Philip Wadler. The essence of functional programming](http://homepages.inf.ed.ac.uk/wadler/papers/essence/essence.ps):
-invited talk, *19'th Symposium on Principles of Programming Languages*, ACM Press, Albuquerque, January 1992.
-<!--	This paper explores the use monads to structure functional programs. No prior knowledge of monads or category theory is required.
-	Monads increase the ease with which programs may be modified. They can mimic the effect of impure features such as exceptions, state, and continuations; and also provide effects not easily achieved with such features. The types of a program reflect which effects occur.
-	The first section is an extended example of the use of monads. A simple interpreter is modified to support various extra features: error messages, state, output, and non-deterministic choice. The second section describes the relation between monads and continuation-passing style. The third section sketches how monads are used in a compiler for Haskell that is written in Haskell.-->
-
-*	[Daniel Friedman. A Schemer's View of Monads](/schemersviewofmonads.ps): from <https://www.cs.indiana.edu/cgi-pub/c311/doku.php?id=home> but the link above is to a local copy.
 
-There's a long list of monad tutorials on the [[Offsite Reading]] page. Skimming the titles makes me laugh.
+There's a long list of monad tutorials on the [[Offsite Reading]] page. (Skimming the titles is somewhat amusing.) If you are confused by monads, make use of these resources. Read around until you find a tutorial pitched at a level that's helpful for you.
 
 In the presentation we gave above---which follows the functional programming conventions---we took `unit`/return and `bind` as the primitive operations. From these a number of other general monad operations can be derived. It's also possible to take some of the others as primitive. The [Monads in Category
-Theory](/advanced_notes/monads_in_category_theory) notes do so, for example.
+Theory](/advanced_topics/monads_in_category_theory) notes do so, for example.
 
 Here are some of the other general monad operations. You don't have to master these; they're collected here for your reference.
 
@@ -499,7 +500,7 @@ that is:
 
 You could also do `bind u (fun x -> v)`; we use the `_` for the function argument to be explicit that that argument is never going to be used.
 
-The `lift` operation we asked you to define for last week's homework is a common operation. The second argument to `bind` converts `'a` values into `'b m` values---that is, into instances of the monadic type. What if we instead had a function that merely converts `'a` values into `'b` values, and we want to use it with our monadic type. Then we "lift" that function into an operation on the monad. For example:
+The `lift` operation we asked you to define for last week's homework is a common operation. The second argument to `bind` converts `'a` values into `'b m` values---that is, into instances of the monadic type. What if we instead had a function that merely converts `'a` values into `'b` values, and we want to use it with our monadic type? Then we "lift" that function into an operation on the monad. For example:
 
 	# let even x = (x mod 2 = 0);;
 	val g : int -> bool = <fun>
@@ -574,15 +575,15 @@ Monad outlook
 -------------
 
 We're going to be using monads for a number of different things in the
-weeks to come.  The first main application will be the State monad,
+weeks to come.  One major application will be the State monad,
 which will enable us to model mutation: variables whose values appear
 to change as the computation progresses.  Later, we will study the
 Continuation monad.
 
-In the meantime, we'll look at several linguistic applications for monads, based
-on what's called the *reader monad*.
+But first, we'll look at several linguistic applications for monads, based
+on what's called the *Reader monad*.
 
-##[[Reader monad]]##
+##[[Reader monad for Variable Binding]]##
 
-##[[Intensionality monad]]##
+##[[Reader monad for Intensionality]]##