d5c0941da9a74e539a9e4944ca686ed0473ae91e
[lambda.git] / advanced_topics / monads_in_category_theory.mdwn
1 **Don't try to read this yet!!! Many substantial edits are still in process.
2 Will be ready soon.**
3
4 Caveats
5 -------
6 I really don't know much category theory. Just enough to put this
7 together. Also, this really is "put together." I haven't yet found an
8 authoritative source (that's accessible to a category theory beginner like
9 myself) that discusses the correspondence between the category-theoretic and
10 functional programming uses of these notions in enough detail to be sure that
11 none of the pieces here is misguided. In particular, it wasn't completely
12 obvious how to map the polymorphism on the programming theory side into the
13 category theory. And I'm bothered by the fact that our `<=<` operation is only
14 partly defined on our domain of natural transformations. But this does seem to
15 me to be the reasonable way to put the pieces together. We very much welcome
16 feedback from anyone who understands these issues better, and will make
17 corrections.
18
19
20 Monoids
21 -------
22 A **monoid** is a structure <code>(S,&#8902;,z)</code> consisting of an associative binary operation <code>&#8902;</code> over some set `S`, which is closed under <code>&#8902;</code>, and which contains an identity element `z` for <code>&#8902;</code>. That is:
23
24
25 <pre>
26         for all s1, s2, s3 in S:
27           (i) s1&#8902;s2 etc are also in S
28          (ii) (s1&#8902;s2)&#8902;s3 = s1&#8902;(s2&#8902;s3)
29         (iii) z&#8902;s1 = s1 = s1&#8902;z
30 </pre>
31
32 Some examples of monoids are:
33
34 *       finite strings of an alphabet `A`, with <code>&#8902;</code> being concatenation and `z` being the empty string
35 *       all functions <code>X&rarr;X</code> over a set `X`, with <code>&#8902;</code> being composition and `z` being the identity function over `X`
36 *       the natural numbers with <code>&#8902;</code> being plus and `z` being 0 (in particular, this is a **commutative monoid**). If we use the integers, or the naturals mod n, instead of the naturals, then every element will have an inverse and so we have not merely a monoid but a **group**.
37 *       if we let <code>&#8902;</code> be multiplication and `z` be 1, we get different monoids over the same sets as in the previous item.
38
39 Categories
40 ----------
41 A **category** is a generalization of a monoid. A category consists of a class of **elements**, and a class of **morphisms** between those elements. Morphisms are sometimes also called maps or arrows. They are something like functions (and as we'll see below, given a set of functions they'll determine a category). However, a single morphism only maps between a single source element and a single target element. Also, there can be multiple distinct morphisms between the same source and target, so the identity of a morphism goes beyond its "extension."
42
43 When a morphism `f` in category <b>C</b> has source `C1` and target `C2`, we'll write <code>f:C1&rarr;C2</code>.
44
45 To have a category, the elements and morphisms have to satisfy some constraints:
46
47 <pre>
48           (i) the class of morphisms has to be closed under composition:
49               where f:C1&rarr;C2 and g:C2&rarr;C3, g &#8728; f is also a
50               morphism of the category, which maps C1&rarr;C3.
51
52          (ii) composition of morphisms has to be associative
53
54         (iii) every element E of the category has to have an identity
55               morphism 1<sub>E</sub>, which is such that for every morphism f:C1&rarr;C2:
56               1<sub>C2</sub> &#8728; f = f = f &#8728; 1<sub>C1</sub>
57 </pre>
58
59 These parallel the constraints for monoids. Note that there can be multiple distinct morphisms between an element `E` and itself; they need not all be identity morphisms. Indeed from (iii) it follows that each element can have only a single identity morphism.
60
61 A good intuitive picture of a category is as a generalized directed graph, where the category elements are the graph's nodes, and there can be multiple directed edges between a given pair of nodes, and nodes can also have multiple directed edges to themselves. Morphisms correspond to directed paths of length &ge; 0 in the graph.
62
63
64 Some examples of categories are:
65
66 *       Categories whose elements are sets and whose morphisms are functions between those sets. Here the source and target of a function are its domain and range, so distinct functions sharing a domain and range (e.g., `sin` and `cos`) are distinct morphisms between the same source and target elements. The identity morphism for any element/set is just the identity function for that set.
67
68 *       any monoid <code>(S,&#8902;,z)</code> generates a category with a single element `x`; this `x` need not have any relation to `S`. The members of `S` play the role of *morphisms* of this category, rather than its elements. All of these morphisms are understood to map `x` to itself. The result of composing the morphism consisting of `s1` with the morphism `s2` is the morphism `s3`, where <code>s3=s1&#8902;s2</code>. The identity morphism for the (single) category element `x` is the monoid's identity `z`.
69
70 *       a **preorder** is a structure <code>(S, &le;)</code> consisting of a reflexive, transitive, binary relation on a set `S`. It need not be connected (that is, there may be members `s1`,`s2` of `S` such that neither <code>s1&le;s2</code> nor <code>s2&le;s1</code>). It need not be anti-symmetric (that is, there may be members `s1`,`s2` of `S` such that <code>s1&le;s2</code> and <code>s2&le;s1</code> but `s1` and `s2` are not identical). Some examples:
71
72         *       sentences ordered by logical implication ("p and p" implies and is implied by "p", but these sentences are not identical; so this illustrates a pre-order without anti-symmetry)
73         *       sets ordered by size (this illustrates it too)
74
75         Any pre-order <code>(S,&le;)</code> generates a category whose elements are the members of `S` and which has only a single morphism between any two elements `s1` and `s2`, iff <code>s1&le;s2</code>.
76
77
78 Functors
79 --------
80 A **functor** is a "homomorphism", that is, a structure-preserving mapping, between categories. In particular, a functor `F` from category <b>C</b> to category <b>D</b> must:
81
82 <pre>
83           (i) associate with every element C1 of <b>C</b> an element F(C1) of <b>D</b>
84
85          (ii) associate with every morphism f:C1&rarr;C2 of <b>C</b> a morphism F(f):F(C1)&rarr;F(C2) of <b>D</b>
86
87         (iii) "preserve identity", that is, for every element C1 of <b>C</b>:
88               F of C1's identity morphism in <b>C</b> must be the identity morphism of F(C1) in <b>D</b>:
89               F(1<sub>C1</sub>) = 1<sub>F(C1)</sub>.
90
91          (iv) "distribute over composition", that is for any morphisms f and g in <b>C</b>:
92               F(g &#8728; f) = F(g) &#8728; F(f)
93 </pre>
94
95 A functor that maps a category to itself is called an **endofunctor**. The (endo)functor that maps every element and morphism of <b>C</b> to itself is denoted `1C`.
96
97 How functors compose: If `G` is a functor from category <b>C</b> to category <b>D</b>, and `K` is a functor from category <b>D</b> to category <b>E</b>, then `KG` is a functor which maps every element `C1` of <b>C</b> to element `K(G(C1))` of <b>E</b>, and maps every morphism `f` of <b>C</b> to morphism `K(G(f))` of <b>E</b>.
98
99 I'll assert without proving that functor composition is associative.
100
101
102
103 Natural Transformation
104 ----------------------
105 So categories include elements and morphisms. Functors consist of mappings from the elements and morphisms of one category to those of another (or the same) category. **Natural transformations** are a third level of mappings, from one functor to another.
106
107 Where `G` and `H` are functors from category <b>C</b> to category <b>D</b>, a natural transformation &eta; between `G` and `H` is a family of morphisms <code>&eta;[C1]:G(C1)&rarr;H(C1)</code> in <b>D</b> for each element `C1` of <b>C</b>. That is, <code>&eta;[C1]</code> has as source `C1`'s image under `G` in <b>D</b>, and as target `C1`'s image under `H` in <b>D</b>. The morphisms in this family must also satisfy the constraint:
108
109 <pre>
110         for every morphism f:C1&rarr;C2 in <b>C</b>:
111         &eta;[C2] &#8728; G(f) = H(f) &#8728; &eta;[C1]
112 </pre>
113
114 That is, the morphism via `G(f)` from `G(C1)` to `G(C2)`, and then via <code>&eta;[C2]</code> to `H(C2)`, is identical to the morphism from `G(C1)` via <code>&eta;[C1]</code> to `H(C1)`, and then via `H(f)` from `H(C1)` to `H(C2)`.
115
116
117 How natural transformations compose:
118
119 Consider four categories <b>B</b>, <b>C</b>, <b>D</b>, and <b>E</b>. Let `F` be a functor from <b>B</b> to <b>C</b>; `G`, `H`, and `J` be functors from <b>C</b> to <b>D</b>; and `K` and `L` be functors from <b>D</b> to <b>E</b>. Let &eta; be a natural transformation from `G` to `H`; &phi; be a natural transformation from `H` to `J`; and &psi; be a natural transformation from `K` to `L`. Pictorally:
120
121 <pre>
122         - <b>B</b> -+ +--- <b>C</b> --+ +---- <b>D</b> -----+ +-- <b>E</b> --
123                  | |        | |            | |
124          F: ------> G: ------>     K: ------>
125                  | |        | |  | &eta;       | |  | &psi;
126                  | |        | |  v         | |  v
127                  | |    H: ------>     L: ------>
128                  | |        | |  | &phi;       | |
129                  | |        | |  v         | |
130                  | |    J: ------>         | |
131         -----+ +--------+ +------------+ +-------
132 </pre>
133
134 Then <code>(&eta; F)</code> is a natural transformation from the (composite) functor `GF` to the composite functor `HF`, such that where `B1` is an element of category <b>B</b>, <code>(&eta; F)[B1] = &eta;[F(B1)]</code>---that is, the morphism in <b>D</b> that <code>&eta;</code> assigns to the element `F(B1)` of <b>C</b>.
135
136 And <code>(K &eta;)</code> is a natural transformation from the (composite) functor `KG` to the (composite) functor `KH`, such that where `C1` is an element of category <b>C</b>, <code>(K &eta;)[C1] = K(&eta;[C1])</code>---that is, the morphism in <b>E</b> that `K` assigns to the morphism <code>&eta;[C1]</code> of <b>D</b>.
137
138
139 <code>(&phi; -v- &eta;)</code> is a natural transformation from `G` to `J`; this is known as a "vertical composition". For any morphism <code>f:C1&rarr;C2</code> in <b>C</b>:
140
141 <pre>
142         &phi;[C2] &#8728; H(f) &#8728; &eta;[C1] = &phi;[C2] &#8728; H(f) &#8728; &eta;[C1]
143 </pre>
144
145 by naturalness of <code>&phi;</code>, is:
146
147 <pre>
148         &phi;[C2] &#8728; H(f) &#8728; &eta;[C1] = J(f) &#8728; &phi;[C1] &#8728; &eta;[C1]
149 </pre>
150
151 by naturalness of <code>&eta;</code>, is:
152
153 <pre>
154         &phi;[C2] &#8728; &eta;[C2] &#8728; G(f) = J(f) &#8728; &phi;[C1] &#8728; &eta;[C1]
155 </pre>
156
157 Hence, we can define <code>(&phi; -v- &eta;)[\_]</code> as: <code>&phi;[\_] &#8728; &eta;[\_]</code> and rely on it to satisfy the constraints for a natural transformation from `G` to `J`:
158
159 <pre>
160         (&phi; -v- &eta;)[C2] &#8728; G(f) = J(f) &#8728; (&phi; -v- &eta;)[C1]
161 </pre>
162
163 An observation we'll rely on later: given the definitions of vertical composition and of how natural transformations compose with functors, it follows that:
164
165 <pre>
166         ((&phi; -v- &eta;) F) = ((&phi; F) -v- (&eta; F))
167 </pre>
168
169 I'll assert without proving that vertical composition is associative and has an identity, which we'll call "the identity transformation."
170
171
172 <code>(&psi; -h- &eta;)</code> is natural transformation from the (composite) functor `KG` to the (composite) functor `LH`; this is known as a "horizontal composition." It's trickier to define, but we won't be using it here. For reference:
173
174 <pre>
175         (&phi; -h- &eta;)[C1]  =  L(&eta;[C1]) &#8728; &psi;[G(C1)]
176                                    =  &psi;[H(C1)] &#8728; K(&eta;[C1])
177 </pre>
178
179 Horizontal composition is also associative, and has the same identity as vertical composition.
180
181
182
183 Monads
184 ------
185 In earlier days, these were also called "triples."
186
187 A **monad** is a structure consisting of an (endo)functor `M` from some category <b>C</b> to itself, along with some natural transformations, which we'll specify in a moment.
188
189 Let `T` be a set of natural transformations <code>&phi;</code>, each being between some arbitrary endofunctor `F` on <b>C</b> and another functor which is the composite `MF'` of `M` and another arbitrary endofunctor `F'` on <b>C</b>. That is, for each element `C1` in <b>C</b>, <code>&phi;</code> assigns `C1` a morphism from element `F(C1)` to element `MF'(C1)`, satisfying the constraints detailed in the previous section. For different members of `T`, the relevant functors may differ; that is, <code>&phi;</code> is a transformation from functor `F` to `MF'`, <code>&gamma;</code> is a transformation from functor `G` to `MG'`, and none of `F`, `F'`, `G`, `G'` need be the same.
190
191 One of the members of `T` will be designated the `unit` transformation for `M`, and it will be a transformation from the identity functor `1C` for <b>C</b> to `M(1C)`. So it will assign to `C1` a morphism from `C1` to `M(C1)`.
192
193 We also need to designate for `M` a `join` transformation, which is a natural transformation from the (composite) functor `MM` to `M`.
194
195 These two natural transformations have to satisfy some constraints ("the monad laws") which are most easily stated if we can introduce a defined notion.
196
197 Let <code>&phi;</code> and <code>&gamma;</code> be members of `T`, that is they are natural transformations from `F` to `MF'` and from `G` to `MG'`, respectively. Let them be such that `F' = G`. Now <code>(M &gamma;)</code> will also be a natural transformation, formed by composing the functor `M` with the natural transformation <code>&gamma;</code>. Similarly, `(join G')` will be a natural transformation, formed by composing the natural transformation `join` with the functor `G'`; it will transform the functor `MMG'` to the functor `MG'`. Now take the vertical composition of the three natural transformations `(join G')`, <code>(M &gamma;)</code>, and <code>&phi;</code>, and abbreviate it as follows. Since composition is associative I don't specify the order of composition on the rhs.
198
199 <pre>
200         &gamma; <=< &phi;  =def.  ((join G') -v- (M &gamma;) -v- &phi;)
201 </pre>
202
203 In other words, `<=<` is a binary operator that takes us from two members <code>&phi;</code> and <code>&gamma;</code> of `T` to a composite natural transformation. (In functional programming, at least, this is called the "Kleisli composition operator". Sometimes it's written <code>&phi; >=> &gamma;</code> where that's the same as <code>&gamma; &lt;=&lt; &phi;</code>.)
204
205 <code>&phi;</code> is a transformation from `F` to `MF'`, where the latter = `MG`; <code>(M &gamma;)</code> is a transformation from `MG` to `MMG'`; and `(join G')` is a transformation from `MMG'` to `MG'`. So the composite <code>&gamma; &lt;=&lt; &phi;</code> will be a transformation from `F` to `MG'`, and so also eligible to be a member of `T`.
206
207 Now we can specify the "monad laws" governing a monad as follows:
208
209 <pre>   
210         (T, <=<, unit) constitute a monoid
211 </pre>
212
213 That's it. Well, there may be a wrinkle here. I don't know whether the definition of a monoid requires the operation to be defined for every pair in its set. In the present case, <code>&gamma; &lt;=&lt; &phi;</code> isn't fully defined on `T`, but only when <code>&phi;</code> is a transformation to some `MF'` and <code>&gamma;</code> is a transformation from `F'`. But wherever `<=<` is defined, the monoid laws must hold:
214
215 <pre>
216             (i) &gamma; <=< &phi; is also in T
217
218            (ii) (&rho; <=< &gamma;) <=< &phi;  =  &rho; <=< (&gamma; <=< &phi;)
219
220         (iii.1) unit <=< &phi;  =  &phi;
221                 (here &phi; has to be a natural transformation to M(1C))
222
223         (iii.2)                &rho;  =  &rho; <=< unit
224                 (here &rho; has to be a natural transformation from 1C)
225 </pre>
226
227 If <code>&phi;</code> is a natural transformation from `F` to `M(1C)` and <code>&gamma;</code> is <code>(&phi; G')</code>, that is, a natural transformation from `FG'` to `MG'`, then we can extend (iii.1) as follows:
228
229 <pre>
230         &gamma; = (&phi; G')
231           = ((unit <=< &phi;) G')
232           = (((join 1C) -v- (M unit) -v- &phi;) G')
233           = (((join 1C) G') -v- ((M unit) G') -v- (&phi; G'))
234           = ((join (1C G')) -v- (M (unit G')) -v- &gamma;)
235           = ((join G') -v- (M (unit G')) -v- &gamma;)
236           since (unit G') is a natural transformation to MG',
237           this satisfies the definition for &lt;=&lt;:
238           = (unit G') <=< &gamma;
239 </pre>
240
241 where as we said <code>&gamma;</code> is a natural transformation from some `FG'` to `MG'`.
242
243 Similarly, if <code>&rho;</code> is a natural transformation from `1C` to `MR'`, and <code>&gamma;</code> is <code>(&rho; G)</code>, that is, a natural transformation from `G` to `MR'G`, then we can extend (iii.2) as follows:
244
245 <pre>
246         &gamma; = (&rho; G)
247           = ((&rho; <=< unit) G)
248           = (((join R') -v- (M &rho;) -v- unit) G)
249           = (((join R') G) -v- ((M &rho;) G) -v- (unit G))
250           = ((join (R'G)) -v- (M (&rho; G)) -v- (unit G))
251           since &gamma; = (&rho; G) is a natural transformation to MR'G,
252           this satisfies the definition &lt;=&lt;:
253           = &gamma; <=< (unit G)
254 </pre>
255
256 where as we said <code>&gamma;</code> is a natural transformation from `G` to some `MR'G`.
257
258 Summarizing then, the monad laws can be expressed as:
259
260 <pre>
261         For all &rho;, &gamma;, &phi; in T for which &rho; <=< &gamma; and &gamma; <=< &phi; are defined:
262
263             (i) &gamma; <=< &phi; etc are also in T
264
265            (ii) (&rho; <=< &gamma;) <=< &phi;  =  &rho; <=< (&gamma; <=< &phi;)
266
267         (iii.1) (unit G') <=< &gamma;  =  &gamma;
268                 when &gamma; is a natural transformation from some FG' to MG'
269
270         (iii.2)                     &gamma;  =  &gamma; <=< (unit G)
271                 when &gamma; is a natural transformation from G to some MR'G
272 </pre>
273
274
275
276 Getting to the standard category-theory presentation of the monad laws
277 ----------------------------------------------------------------------
278 In category theory, the monad laws are usually stated in terms of `unit` and `join` instead of `unit` and `<=<`.
279
280 <!--
281         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>.
282         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>.
283 -->
284
285 Let's remind ourselves of some principles:
286
287 *       composition of morphisms, functors, and natural compositions is associative
288
289 *       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>
290
291 *       if <code>&eta;</code> is a natural transformation from `G` to `H`, then for every <code>f:C1&rarr;C2</code> in `G` and `H`'s source category <b>C</b>: <code>&eta;[C2] &#8728; G(f) = H(f) &#8728; &eta;[C1]</code>.
292
293 *       <code>(&eta; F)[E] = &eta;[F(E)]</code> 
294
295 *       <code>(K &eta;)[E} = K(&eta;[E])</code>
296
297 *       <code>((&phi; -v- &eta;) F) = ((&phi; F) -v- (&eta; F))</code>
298
299 Let's use the definitions of naturalness, and of composition of natural transformations, to establish two lemmas.
300
301
302 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>:
303
304 <pre>
305         (1) join[C2] &#8728; MM(f)  =  M(f) &#8728; join[C1]
306 </pre>
307
308 Next, let <code>&gamma;</code> be a transformation from `G` to `MG'`, and
309  consider the composite transformation <code>((join MG') -v- (MM &gamma;))</code>.
310
311 *       <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>.
312
313 *       `(join MG')` is a transformation from `MM(MG')` to `M(MG')` that assigns `C1` the morphism `join[MG'(C1)]`.
314
315 Composing them:
316
317 <pre>
318         (2) ((join MG') -v- (MM &gamma;)) assigns to C1 the morphism join[MG'(C1)] &#8728; MM(&gamma;*).
319 </pre>
320
321 Next, consider the composite transformation <code>((M &gamma;) -v- (join G))</code>:
322
323 <pre>
324         (3) ((M &gamma;) -v- (join G)) assigns to C1 the morphism M(&gamma;*) &#8728; join[G(C1)].
325 </pre>
326
327 So for every element `C1` of <b>C</b>:
328
329 <pre>
330         ((join MG') -v- (MM &gamma;))[C1], by (2) is:
331         join[MG'(C1)] &#8728; MM(&gamma;*), which by (1), with f=&gamma;*:G(C1)&rarr;MG'(C1) is:
332         M(&gamma;*) &#8728; join[G(C1)], which by 3 is:
333         ((M &gamma;) -v- (join G))[C1]
334 </pre>
335
336 So our **(lemma 1)** is:
337
338 <pre>
339         ((join MG') -v- (MM &gamma;))  =  ((M &gamma;) -v- (join G)),
340         where as we said &gamma; is a natural transformation from G to MG'.
341 </pre>
342
343
344 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:C1&rarr;C2</code> in <b>C</b>:
345
346 <pre>
347         (4) unit[C2] &#8728; f = M(f) &#8728; unit[C1]
348 </pre>
349
350 Next, consider the composite transformation <code>((M &gamma;) -v- (unit G))</code>:
351
352 <pre>
353         (5) ((M &gamma;) -v- (unit G)) assigns to C1 the morphism M(&gamma;*) &#8728; unit[G(C1)].
354 </pre>
355
356 Next, consider the composite transformation <code>((unit MG') -v- &gamma;)</code>:
357
358 <pre>
359         (6) ((unit MG') -v- &gamma;) assigns to C1 the morphism unit[MG'(C1)] &#8728; &gamma;*.
360 </pre>
361
362 So for every element C1 of <b>C</b>:
363
364 <pre>
365         ((M &gamma;) -v- (unit G))[C1], by (5) =
366         M(&gamma;*) &#8728; unit[G(C1)], which by (4), with f=&gamma;*:G(C1)&rarr;MG'(C1) is:
367         unit[MG'(C1)] &#8728; &gamma;*, which by (6) =
368         ((unit MG') -v- &gamma;)[C1]
369 </pre>
370
371 So our **(lemma 2)** is:
372
373 <pre>
374         (((M &gamma;) -v- (unit G))  =  ((unit MG') -v- &gamma;)),
375         where as we said &gamma; is a natural transformation from G to MG'.
376 </pre>
377
378
379 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-".
380
381 <pre>
382         For all &rho;, &gamma;, &phi; in T,
383         where &phi; is a transformation from F to MF',
384         &gamma; is a transformation from G to MG',
385         &rho; is a transformation from R to MR',
386         and F'=G and G'=R:
387
388              (i) &gamma; <=< &phi; etc are also in T
389         ==>
390             (i') ((join G') (M &gamma;) &phi;) etc are also in T
391
392
393
394             (ii) (&rho; <=< &gamma;) <=< &phi;  =  &rho; <=< (&gamma; <=< &phi;)
395         ==>
396                      (&rho; <=< &gamma;) is a transformation from G to MR', so
397                          (&rho; <=< &gamma;) <=< &phi; becomes: ((join R') (M (&rho; <=< &gamma;)) &phi;)
398                                                         which is: ((join R') (M ((join R') (M &rho;) &gamma;)) &phi;)
399
400                          similarly, &rho; <=< (&gamma; <=< &phi;) is:
401                                                         ((join R') (M &rho;) ((join G') (M &gamma;) &phi;))
402
403                          substituting these into (ii), and helping ourselves to associativity on the rhs, we get:
404                  ((join R') (M ((join R') (M &rho;) &gamma;)) &phi;) = ((join R') (M &rho;) (join G') (M &gamma;) &phi;)
405     
406                          which by the distributivity of functors over composition, and helping ourselves to associativity on the lhs, yields:
407                  ((join R') (M join R') (MM &rho;) (M &gamma;) &phi;) = ((join R') (M &rho;) (join G') (M &gamma;) &phi;)
408   
409                          which by lemma 1, with &rho; a transformation from G' to MR', yields:
410                  ((join R') (M join R') (MM &rho;) (M &gamma;) &phi;) = ((join R') (join MR') (MM &rho;) (M &gamma;) &phi;)
411
412                          which will be true for all &rho;,&gamma;,&phi; only when:
413                  ((join R') (M join R')) = ((join R') (join MR')), for any R'.
414
415                          which will in turn be true when:
416        (ii') (join (M join)) = (join (join M))
417
418
419
420          (iii.1) (unit G') <=< &gamma;  =  &gamma;
421                  when &gamma; is a natural transformation from some FG' to MG'
422         ==>
423                          (unit G') is a transformation from G' to MG', so:
424                          (unit G') <=< &gamma; becomes: ((join G') (M unit G') &gamma;)
425
426                          substituting in (iii.1), we get:
427                          ((join G') (M unit G') &gamma;) = &gamma;
428
429                          which will be true for all &gamma; just in case:
430                  ((join G') (M unit G')) = the identity transformation, for any G'
431
432                          which will in turn be true just in case:
433         (iii.1') (join (M unit) = the identity transformation
434
435
436
437
438          (iii.2) &gamma;  =  &gamma; <=< (unit G)
439                  when &gamma; is a natural transformation from G to some MR'G
440         ==>
441                          unit <=< &gamma; becomes: ((join R'G) (M &gamma;) unit)
442                         
443                          substituting in (iii.2), we get:
444                          &gamma; = ((join R'G) (M &gamma;) (unit G))
445                 
446                          which by lemma 2, yields:
447                          &gamma; = ((join R'G) ((unit MR'G) &gamma;)
448
449                           which will be true for all &gamma; just in case:
450                  ((join R'G) (unit MR'G)) = the identity transformation, for any R'G
451
452                          which will in turn be true just in case:
453         (iii.2') (join (unit M)) = the identity transformation
454 </pre>
455
456
457 Collecting the results, our monad laws turn out in this format to be:
458
459 <pre>
460         For all &rho;, &gamma;, &phi; in T,
461         where &phi; is a transformation from F to MF',
462         &gamma; is a transformation from G to MG',
463         &rho; is a transformation from R to MR',
464         and F'=G and G'=R:
465
466             (i') ((join G') (M &gamma;) &phi;) etc also in T
467
468            (ii') (join (M join)) = (join (join M))
469
470         (iii.1') (join (M unit)) = the identity transformation
471
472         (iii.2') (join (unit M)) = the identity transformation
473 </pre>
474
475
476
477 Getting to the functional programming presentation of the monad laws
478 --------------------------------------------------------------------
479 In functional programming, `unit` is sometimes called `return` and the monad laws are usually stated in terms of `unit`/`return` and an operation called `bind` which is interdefinable with `<=<` or with `join`.
480
481 The base category <b>C</b> will have types as elements, and monadic functions as its morphisms. The source and target of a morphism will be the types of its argument and its result. (As always, there can be multiple distinct morphisms from the same source to the same target.)
482
483 A monad `M` will consist of a mapping from types `'t` to types `M('t)`, and a mapping from functions <code>f:C1&rarr;C2</code> to functions <code>M(f):M(C1)&rarr;M(C2)</code>. This is also known as <code>lift<sub>M</sub> f</code> for `M`, and is pronounced "function f lifted into the monad M." For example, where `M` is the list monad, `M` maps every type `'t` into the type `'t list`, and maps every function <code>f:x&rarr;y</code> into the function that maps `[x1,x2...]` to `[y1,y2,...]`.
484
485
486 In functional programming, instead of working with natural transformations we work with "monadic values" and polymorphic functions "into the monad" in question.
487
488 A "monadic value" is any member of a type M('t), for any type 't. For example, a list is a monadic value for the list monad. We can think of these monadic values as the result of applying some function <code>(&phi; : F('t) &rarr; M(F'('t)))</code> to an argument `a` of type `F('t)`.
489
490
491 Let `'t` be a type variable, and `F` and `F'` be functors, and let `phi` be a polymorphic function that takes arguments of type `F('t)` and yields results of type `MF'('t)` in the monad `M`. An example with `M` being the list monad:
492
493 <pre>
494         let phi = fun ((_:char, x y) -> [(1,x,y),(2,x,y)]
495 </pre>
496
497 Here phi is defined when `'t = 't1*'t2`, `F('t1*'t2) = char * 't1 * 't2`, and `F'('t1 * 't2) = int * 't1 * 't2`.
498
499
500 Now where `gamma` is another function into monad `M` of type <code>F'('t) &rarr; MG'('t)</code>, we define:
501
502 <pre>
503         gamma =<< phi a  =def. ((join G') -v- (M gamma)) (phi a)
504
505                          = ((join G') -v- (M gamma) -v- phi) a
506                                          = (gamma <=< phi) a
507 </pre>
508
509 Hence:
510
511 <pre>
512         gamma <=< phi = fun a -> (gamma =<< phi a)
513 </pre>
514
515 `gamma =<< phi a` is called the operation of "binding" the function gamma to the monadic value `phi a`, and is usually written as `phi a >>= gamma`.
516
517 With these definitions, our monadic laws become:
518
519
520 <pre>
521         Where phi is a polymorphic function from type F('t) -> M F'('t)
522         and gamma is a polymorphic function from type G('t) -> M G' ('t)
523         and rho is a polymorphic function from type R('t) -> M R' ('t)
524         and F' = G and G' = R, 
525         and a ranges over values of type F('t) for some type 't,
526         and b ranges over values of type G('t):
527
528               (i) &gamma; <=< &phi; is defined,
529                           and is a natural transformation from F to MG'
530         ==>
531                 (i'') fun a -> gamma =<< phi a is defined,
532                           and is a function from type F('t) -> M G' ('t)
533
534
535
536              (ii) (&rho; <=< &gamma;) <=< &phi;  =  &rho; <=< (&gamma; <=< &phi;)
537         ==>
538                           (fun a -> (rho <=< gamma) =<< phi a)  =  (fun a -> rho =<< (gamma <=< phi) a)
539                           (fun a -> (fun b -> rho =<< gamma b) =<< phi a)  =  (fun a -> rho =<< (gamma =<< phi a))
540
541            (ii'') (fun b -> rho =<< gamma b) =<< phi a  =  rho =<< (gamma =<< phi a)
542
543
544
545           (iii.1) (unit G') <=< &gamma;  =  &gamma;
546                   when &gamma; is a natural transformation from some FG' to MG'
547
548                           (unit G') <=< gamma  =  gamma
549                           when gamma is a function of type FQ'('t) -> M G'('t)
550
551                           fun b -> (unit G') =<< gamma b  =  gamma
552
553                           (unit G') =<< gamma b  =  gamma b
554
555                           As below, return will map arguments c of type G'('t)
556                           to the monadic value (unit G') b, of type M G'('t).
557
558         (iii.1'') return =<< gamma b  =  gamma b
559
560
561
562           (iii.2) &gamma;  =  &gamma; <=< (unit G)
563                   when &gamma; is a natural transformation from G to some MR'G
564         ==>
565                           gamma  =  gamma <=< (unit G)
566                           when gamma is a function of type G('t) -> M R' G('t)
567
568                           gamma  =  fun b -> gamma =<< ((unit G) b)
569
570                           Let return be a polymorphic function mapping arguments
571                           of any type 't to M('t). In particular, it maps arguments
572                           b of type G('t) to the monadic value (unit G) b, of
573                           type M G('t).
574
575                           gamma  =  fun b -> gamma =<< return b
576
577         (iii.2'') gamma b  =  gamma =<< return b
578 </pre>
579
580 Summarizing (ii''), (iii.1''), (iii.2''), these are the monadic laws as usually stated in the functional programming literature:
581
582 *       `fun b -> rho =<< gamma b) =<< phi a  =  rho =<< (gamma =<< phi a)`
583
584         Usually written reversed, and with a monadic variable `u` standing in
585         for `phi a`:
586
587         `u >>= (fun b -> gamma b >>= rho)  =  (u >>= gamma) >>= rho`
588
589 *       `return =<< gamma b  =  gamma b`
590
591         Usually written reversed, and with `u` standing in for `phi a`:
592
593         `u >>= return  =  u`
594
595 *       `gamma b  =  gamma =<< return b`
596
597         Usually written reversed:
598
599         `return b >>= gamma  =  gamma b`
600  
601