X-Git-Url: http://lambda.jimpryor.net/git/gitweb.cgi?p=lambda.git;a=blobdiff_plain;f=advanced_topics%2Fmonads_in_category_theory.mdwn;h=24670796b21e1fc3cd230352e0049772bf17a2b3;hp=f05747f675b416fa5d5af01dee2d0f0278258874;hb=ac47fea0dc57a0f496d14dba80383206397a35f9;hpb=704abdbe4afe78e553738662a3cb0bb6944b54ff;ds=sidebyside

diff --git a/advanced_topics/monads_in_category_theory.mdwn b/advanced_topics/monads_in_category_theory.mdwn
index f05747f6..24670796 100644
--- a/advanced_topics/monads_in_category_theory.mdwn
+++ b/advanced_topics/monads_in_category_theory.mdwn
@@ -273,8 +273,8 @@ Summarizing then, the monad laws can be expressed as:
 
 
 
-The standard category-theory presentation of the monad laws
------------------------------------------------------------
+Getting to the standard category-theory presentation of the monad laws
+----------------------------------------------------------------------
 In category theory, the monad laws are usually stated in terms of `unit` and `join` instead of `unit` and `<=<`.
 
 <!--
@@ -308,7 +308,7 @@ Recall that `join` is a natural transformation from the (composite) functor `MM`
 Next, let <code>&gamma;</code> be a transformation from `G` to `MG'`, and
  consider the composite transformation <code>((join MG') -v- (MM &gamma;))</code>.
 
-*	<code>&gamma;</code> assigns elements `C1` in <b>C</b> a morphism <code>&gamma;\*: G(C1) &rarr; MG'(C1)</code>. <code>(MM &gamma;)</code> is a transformation that instead assigns `C1` the morphism <code>MM(&gamma;\*)</code>.
+*	<code>&gamma;</code> assigns elements `C1` in <b>C</b> a morphism <code>&gamma;\*:G(C1) &rarr; MG'(C1)</code>. <code>(MM &gamma;)</code> is a transformation that instead assigns `C1` the morphism <code>MM(&gamma;\*)</code>.
 
 *	`(join MG')` is a transformation from `MM(MG')` to `M(MG')` that assigns `C1` the morphism `join[MG'(C1)]`.
 
@@ -318,10 +318,10 @@ Composing them:
 	(2) ((join MG') -v- (MM &gamma;)) assigns to C1 the morphism join[MG'(C1)] &#8728; MM(&gamma;*).
 </pre>
 
-Next:
+Next, consider the composite transformation <code>((M &gamma;) -v- (join G))</code>:
 
 <pre>
-	(3) Consider the composite transformation <code>((M &gamma;) -v- (join G))</code>. This assigns to C1 the morphism M(&gamma;*) &#8728; join[G(C1)].
+	(3) ((M &gamma;) -v- (join G)) assigns to C1 the morphism M(&gamma;*) &#8728; join[G(C1)].
 </pre>
 
 So for every element `C1` of <b>C</b>:
@@ -347,16 +347,16 @@ Next recall that `unit` is a natural transformation from `1C` to `M`. So for ele
 	(4) unit[C2] &#8728; f = M(f) &#8728; unit[C1]
 </pre>
 
-Next:
+Next, consider the composite transformation <code>((M &gamma;) -v- (unit G))</code>:
 
 <pre>
-	(5) Consider the composite transformation ((M &gamma;) -v- (unit G)). This assigns to C1 the morphism M(&gamma;*) &#8728; unit[G(C1)].
+	(5) ((M &gamma;) -v- (unit G)) assigns to C1 the morphism M(&gamma;*) &#8728; unit[G(C1)].
 </pre>
 
-Next:
+Next, consider the composite transformation <code>((unit MG') -v- &gamma;)</code>:
 
 <pre>
-	(6) Consider the composite transformation ((unit MG') -v- &gamma;). This assigns to C1 the morphism unit[MG'(C1)] &#8728; &gamma;*.
+	(6) ((unit MG') -v- &gamma;) assigns to C1 the morphism unit[MG'(C1)] &#8728; &gamma;*.
 </pre>
 
 So for every element C1 of <b>C</b>:
@@ -379,95 +379,103 @@ So our **(lemma 2)** is:
 Finally, we substitute <code>((join G') -v- (M &gamma;) -v- &phi;)</code> for <code>&gamma; &lt;=&lt; &phi;</code> in the monad laws. For simplicity, I'll omit the "-v-".
 
 <pre>
-	for all &phi;,&gamma;,&rho; in T, where &phi; is a transformation from F to MF', &gamma; is a transformation from G to MG', R is a transformation from R to MR', and F'=G and G'=R:
+	For all &rho;, &gamma;, &phi; in T,
+	where &phi; is a transformation from F to MF',
+	&gamma; is a transformation from G to MG',
+	&rho; is a transformation from R to MR',
+	and F'=G and G'=R:
 
-	(i) &gamma; <=< &phi; etc are also in T
+	     (i) &gamma; <=< &phi; etc are also in T
 	==>
-	(i') ((join G') (M &gamma;) &phi;) etc are also in T
+	    (i') ((join G') (M &gamma;) &phi;) etc are also in T
 
 
-	(ii) (&rho; <=< &gamma;) <=< &phi;  =  &rho; <=< (&gamma; <=< &phi;)
+
+	    (ii) (&rho; <=< &gamma;) <=< &phi;  =  &rho; <=< (&gamma; <=< &phi;)
 	==>
-		 (&rho; <=< &gamma;) is a transformation from G to MR', so:
-			(&rho; <=< &gamma;) <=< &phi; becomes: (join R') (M (&rho; <=< &gamma;)) &phi;
-							which is: (join R') (M ((join R') (M &rho;) &gamma;)) &phi;
-		 	substituting in (ii), and helping ourselves to associativity on the rhs, we get:
+		     (&rho; <=< &gamma;) is a transformation from G to MR', so
+			 (&rho; <=< &gamma;) <=< &phi; becomes: ((join R') (M (&rho; <=< &gamma;)) &phi;)
+							which is: ((join R') (M ((join R') (M &rho;) &gamma;)) &phi;)
 
-	     ((join R') (M ((join R') (M &rho;) &gamma;)) &phi;) = ((join R') (M &rho;) (join G') (M &gamma;) &phi;)
-                     ---------------------
-			which by the distributivity of functors over composition, and helping ourselves to associativity on the lhs, yields:
-                    ------------------------
-	     ((join R') (M join R') (MM &rho;) (M &gamma;) &phi;) = ((join R') (M &rho;) (join G') (M &gamma;) &phi;)
-                                                             ---------------
-			which by lemma 1, with &rho; a transformation from G' to MR', yields:
-                                                             -----------------
-	     ((join R') (M join R') (MM &rho;) (M &gamma;) &phi;) = ((join R') (join MR') (MM &rho;) (M &gamma;) &phi;)
+			 similarly, &rho; <=< (&gamma; <=< &phi;) is:
+							((join R') (M &rho;) ((join G') (M &gamma;) &phi;))
 
-			which will be true for all &rho;,&gamma;,&phi; just in case:
+		 	 substituting these into (ii), and helping ourselves to associativity on the rhs, we get:
+	         ((join R') (M ((join R') (M &rho;) &gamma;)) &phi;) = ((join R') (M &rho;) (join G') (M &gamma;) &phi;)
+    
+			 which by the distributivity of functors over composition, and helping ourselves to associativity on the lhs, yields:
+	         ((join R') (M join R') (MM &rho;) (M &gamma;) &phi;) = ((join R') (M &rho;) (join G') (M &gamma;) &phi;)
+  
+			 which by lemma 1, with &rho; a transformation from G' to MR', yields:
+	         ((join R') (M join R') (MM &rho;) (M &gamma;) &phi;) = ((join R') (join MR') (MM &rho;) (M &gamma;) &phi;)
 
-	      ((join R') (M join R')) = ((join R') (join MR')), for any R'.
+			 which will be true for all &rho;,&gamma;,&phi; only when:
+	         ((join R') (M join R')) = ((join R') (join MR')), for any R'.
 
-			which will in turn be true just in case:
+			 which will in turn be true when:
+       (ii') (join (M join)) = (join (join M))
 
-	(ii') (join (M join)) = (join (join M))
 
 
-	(iii.1) (unit F') <=< &phi;  =  &phi;
+	 (iii.1) (unit G') <=< &gamma;  =  &gamma;
+	         when &gamma; is a natural transformation from some FG' to MG'
 	==>
-			(unit F') is a transformation from F' to MF', so:
-				(unit F') <=< &phi; becomes: (join F') (M unit F') &phi;
-						   which is: (join F') (M unit F') &phi;
-				substituting in (iii.1), we get:
-			((join F') (M unit F') &phi;) = &phi;
-
-			which will be true for all &phi; just in case:
+			 (unit G') is a transformation from G' to MG', so:
+			 (unit G') <=< &gamma; becomes: ((join G') (M unit G') &gamma;)
 
-	         ((join F') (M unit F')) = the identity transformation, for any F'
+			 substituting in (iii.1), we get:
+			 ((join G') (M unit G') &gamma;) = &gamma;
 
-			which will in turn be true just in case:
+			 which will be true for all &gamma; just in case:
+	         ((join G') (M unit G')) = the identity transformation, for any G'
 
+			 which will in turn be true just in case:
 	(iii.1') (join (M unit) = the identity transformation
 
 
-	(iii.2) &phi;  =  &phi; <=< (unit F)
-	==>
-			&phi; is a transformation from F to MF', so:
-				unit <=< &phi; becomes: (join F') (M &phi;) unit
-				substituting in (iii.2), we get:
-			&phi; = ((join F') (M &phi;) (unit F))
-						   --------------
-				which by lemma (2), yields:
-                            ------------
-			&phi; = ((join F') ((unit MF') &phi;)
-
-				which will be true for all &phi; just in case:
-
-	        ((join F') (unit MF')) = the identity transformation, for any F'
 
-				which will in turn be true just in case:
 
+	 (iii.2) &gamma;  =  &gamma; <=< (unit G)
+	         when &gamma; is a natural transformation from G to some MR'G
+	==>
+			 unit <=< &gamma; becomes: ((join R'G) (M &gamma;) unit)
+			
+			 substituting in (iii.2), we get:
+			 &gamma; = ((join R'G) (M &gamma;) (unit G))
+		
+			 which by lemma 2, yields:
+			 &gamma; = ((join R'G) ((unit MR'G) &gamma;)
+
+			  which will be true for all &gamma; just in case:
+	         ((join R'G) (unit MR'G)) = the identity transformation, for any R'G
+
+			 which will in turn be true just in case:
 	(iii.2') (join (unit M)) = the identity transformation
 </pre>
 
 
 Collecting the results, our monad laws turn out in this format to be:
 
-</pre>
-	when &phi; a transformation from F to MF', &gamma; a transformation from F' to MG', &rho; a transformation from G' to MR' all in T:
+<pre>
+	For all &rho;, &gamma;, &phi; in T,
+	where &phi; is a transformation from F to MF',
+	&gamma; is a transformation from G to MG',
+	&rho; is a transformation from R to MR',
+	and F'=G and G'=R:
 
-	(i') ((join G') (M &gamma;) &phi;) etc also in T
+	    (i') ((join G') (M &gamma;) &phi;) etc also in T
 
-	(ii') (join (M join)) = (join (join M))
+	   (ii') (join (M join)) = (join (join M))
 
 	(iii.1') (join (M unit)) = the identity transformation
 
-	(iii.2')(join (unit M)) = the identity transformation
+	(iii.2') (join (unit M)) = the identity transformation
 </pre>
 
 
 
-7. The functional programming presentation of the monad laws
-------------------------------------------------------------
+Getting to the functional programming presentation of the monad laws
+--------------------------------------------------------------------
 In functional programming, unit is usually called "return" and the monad laws are usually stated in terms of return and an operation called "bind" which is interdefinable with <=< or with join.
 
 Additionally, whereas in category-theory one works "monomorphically", in functional programming one usually works with "polymorphic" functions.