author Jim Pryor Tue, 2 Nov 2010 13:27:10 +0000 (09:27 -0400) committer Jim Pryor Tue, 2 Nov 2010 13:27:10 +0000 (09:27 -0400)
Signed-off-by: Jim Pryor <profjim@jimpryor.net>

index b148fe6..fe12655 100644 (file)
@@ -257,60 +257,99 @@ 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 `<=<`.

-(*
+<!--
P2. every element C1 of a category <b>C</b> has an identity morphism 1<sub>C1</sub> such that for every morphism f:C1&rarr;C2 in <b>C</b>: 1<sub>C2</sub> &#8728; f = f = f &#8728; 1<sub>C1</sub>.
P3. functors "preserve identity", that is for every element C1 in F's source category: F(1<sub>C1</sub>) = 1<sub>F(C1)</sub>.
-*)
+-->

Let's remind ourselves of some principles:
-       * composition of morphisms, functors, and natural compositions is associative
-       * functors "distribute over composition", that is for any morphisms f and g in F's source category: F(g &#8728; f) = F(g) &#8728; F(f)
-       * if &eta; is a natural transformation from F to G, then for every f:C1&rarr;C2 in F and G's source category <b>C</b>: &eta;[C2] &#8728; F(f) = G(f) &#8728; &eta;[C1].

+*      composition of morphisms, functors, and natural compositions is associative
+
+*      functors "distribute over composition", that is for any morphisms `f` and `g` in `F`'s source category: <code>F(g &#8728; f) = F(g) &#8728; F(f)</code>
+
+*      if <code>&eta;</code> is a natural transformation from `F` to `G`, then for every <code>f:C1&rarr;C2</code> in `F` and `G`'s source category <b>C</b>: <code>&eta;[C2] &#8728; F(f) = G(f) &#8728; &eta;[C1]</code>.

Let's use the definitions of naturalness, and of composition of natural transformations, to establish two lemmas.

-Recall that join is a natural transformation from the (composite) functor MM to M. So for elements C1 in <b>C</b>, join[C1] will be a morphism from MM(C1) to M(C1). And for any morphism f:a&rarr;b in <b>C</b>:
+Recall that join is a natural transformation from the (composite) functor `MM` to `M`. So for elements `C1` in <b>C</b>, `join[C1]` will be a morphism from `MM(C1)` to `M(C1)`. And for any morphism <code>f:C1&rarr;C2</code> in <b>C</b>:
+
+<pre>
+       (1) join[C2] &#8728; MM(f)  =  M(f) &#8728; join[C1]
+</pre>
+
+Next, consider the composite transformation <code>((join MG') -v- (MM &gamma;))</code>.
+
+*      <code>&gamma;</code> is a transformation from `G` to `MG'`, and 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 `MMMG'` to `MMG'` that assigns `C1` the morphism `join[MG'(C1)]`.

-       (1) join[b] &#8728; MM(f)  =  M(f) &#8728; join[a]
+Composing them:
+
+<pre>
+       (2) <code>((join MG') -v- (MM &gamma;))</code> assigns to `C1` the morphism <code>join[MG'(C1)] &#8728; MM(&gamma;*)</code>.
+</pre>

-Next, consider the composite transformation ((join MG') -v- (MM &gamma;)).
-       &gamma; is a transformation from G to MG', and assigns elements C1 in <b>C</b> a morphism &gamma;*: G(C1) &rarr; MG'(C1). (MM &gamma;) is a transformation that instead assigns C1 the morphism MM(&gamma;*).
-       (join MG') is a transformation from MMMG' to MMG' that assigns C1 the morphism join[MG'(C1)].
-       Composing them:
-       (2) ((join MG') -v- (MM &gamma;)) assigns to C1 the morphism join[MG'(C1)] &#8728; MM(&gamma;*).
+Next, consider the composite transformation <code>((M &gamma;) -v- (join G))</code>.

-Next, consider the composite transformation ((M &gamma;) -v- (join G)).
+<pre>
(3) This assigns to C1 the morphism M(&gamma;*) &#8728; join[G(C1)].
+</pre>

-So for every element C1 of <b>C</b>:
+So for every element `C1` of <b>C</b>:
+
+<pre>
((join MG') -v- (MM &gamma;))[C1], by (2) is:
join[MG'(C1)] &#8728; MM(&gamma;*), which by (1), with f=&gamma;*: G(C1)&rarr;MG'(C1) is:
M(&gamma;*) &#8728; join[G(C1)], which by 3 is:
((M &gamma;) -v- (join G))[C1]
+</pre>
+
+So our **(lemma 1)** is:

-So our (lemma 1) is: ((join MG') -v- (MM &gamma;))  =  ((M &gamma;) -v- (join G)), where &gamma; is a transformation from G to MG'.
+<pre>
+       ((join MG') -v- (MM &gamma;))  =  ((M &gamma;) -v- (join G)), where &gamma; is a transformation from G to MG'.
+</pre>

-Next recall that unit is a natural transformation from 1C to M. So for elements C1 in <b>C</b>, unit[C1] will be a morphism from C1 to M(C1). And for any morphism f:a&rarr;b in <b>C</b>:
+Next recall that unit is a natural transformation from `1C` to `M`. So for elements `C1` in <b>C</b>, `unit[C1]` will be a morphism from `C1` to `M(C1)`. And for any morphism <code>f:a&rarr;b</code> in <b>C</b>:
+
+<pre>
(4) unit[b] &#8728; f = M(f) &#8728; unit[a]
+</pre>
+
+Next consider the composite transformation <code>((M &gamma;) -v- (unit G))</code>:
+
+<pre>
+       (5) This assigns to C1 the morphism M(&gamma;*) &#8728; unit[G(C1)].
+</pre>

-Next consider the composite transformation ((M &gamma;) -v- (unit G)). (5) This assigns to C1 the morphism M(&gamma;*) &#8728; unit[G(C1)].
+Next consider the composite transformation <code>((unit MG') -v- &gamma;)</code>.

-Next consider the composite transformation ((unit MG') -v- &gamma;). (6) This assigns to C1 the morphism unit[MG'(C1)] &#8728; &gamma;*.
+<pre>
+       (6) This assigns to C1 the morphism unit[MG'(C1)] &#8728; &gamma;*.
+</pre>

So for every element C1 of <b>C</b>:
+
+<pre>
((M &gamma;) -v- (unit G))[C1], by (5) =
M(&gamma;*) &#8728; unit[G(C1)], which by (4), with f=&gamma;*: G(C1)&rarr;MG'(C1) is:
unit[MG'(C1)] &#8728; &gamma;*, which by (6) =
((unit MG') -v- &gamma;)[C1]
+</pre>
+
+So our **(lemma 2)** is:

-So our lemma (2) is: (((M &gamma;) -v- (unit G))  =  ((unit MG') -v- &gamma;)), where &gamma; is a transformation from G to MG'.
+<pre>
+       (((M &gamma;) -v- (unit G))  =  ((unit MG') -v- &gamma;)), where &gamma; is a transformation from G to MG'.
+</pre>

-Finally, we substitute ((join G') -v- (M &gamma;) -v- &phi;) for &gamma; <=< &phi; in the monad laws. For simplicity, I'll omit the "-v-".
+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:

(i) &gamma; <=< &phi; etc are also in T
@@ -379,10 +418,12 @@ Finally, we substitute ((join G') -v- (M &gamma;) -v- &phi;) for &gamma; <=< &ph
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:

(i') ((join G') (M &gamma;) &phi;) etc also in T
@@ -392,6 +433,7 @@ Collecting the results, our monad laws turn out in this format to be:
(iii.1') (join (M unit)) = the identity transformation

(iii.2')(join (unit M)) = the identity transformation
+</pre>