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=0f84bb28e49392cdeb605e6a2e830a9ac3112ea4;hp=49cb8b6941202912b7a5cdfc5a46a2aa4369cee3;hb=8076acb29d9f26cb505398e08d79bf5992584fc7;hpb=b78546f6772fbd3db0a18548ef3dbc8cd3194b6e diff --git a/advanced_topics/monads_in_category_theory.mdwn b/advanced_topics/monads_in_category_theory.mdwn index 49cb8b69..0f84bb28 100644 --- a/advanced_topics/monads_in_category_theory.mdwn +++ b/advanced_topics/monads_in_category_theory.mdwn @@ -21,10 +21,13 @@ Monoids ------- A **monoid** is a structure `(S, *, z)` consisting of an associative binary operation `*` over some set `S`, which is closed under `*`, and which contains an identity element `z` for `*`. That is: - for all s1,s2,s3 in S: + +
```+	for all s1, s2, s3 in S:
(i) s1*s2 etc are also in S
(ii) (s1*s2)*s3 = s1*(s2*s3)
(iii) z*s1 = s1 = s1*z
+```
Some examples of monoids are: @@ -37,15 +40,17 @@ Categories ---------- 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." -When a morphism `f` in category **C** has source `c1` and target `c2`, we'll write `f:c1->c2`. +When a morphism `f` in category C has source `C1` and target `C2`, we'll write `f:C1->C2`. To have a category, the elements and morphisms have to satisfy some constraints: - (i) the class of morphisms has to be closed under composition: where f:c1->c2 and g:c2->c3, g o f is also a morphism of the category, which maps c1->c3. +
```+	(i) the class of morphisms has to be closed under composition: where f:C1->C2 and g:C2->C3, g o f is also a morphism of the category, which maps C1->C3.
(ii) composition of morphisms has to be associative
-	(iii) every element e of the category has to have an identity morphism id[e], which is such that for every morphism f:c1->c2: id[c2] o f = f = f o id[c1]
+	(iii) every element E of the category has to have an identity morphism 1E, which is such that for every morphism f:C1->C2: 1C2 o f = f = f o 1C1
+```
-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. +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. 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. (Every node must have at least one such, which is that node's identity morphism.) @@ -66,16 +71,18 @@ Some examples of categories are: Functors -------- -A **functor** is a "homomorphism", that is, a structure-preserving mapping, between categories. In particular, a functor `F` from category **C** to category **D** must: +A **functor** is a "homomorphism", that is, a structure-preserving mapping, between categories. In particular, a functor `F` from category C to category D must: - (i) associate with every element c1 of **C** an element F(c1) of **D** - (ii) associate with every morphism f:c1->c2 of **C** a morphism F(f):F(c1)->F(c2) of **D** - (iii) "preserve identity", that is, for every element c1 of **C**: F of c1's identity morphism in **C** must be the identity morphism of F(c1) in **D**: F(id[c1]) = id[F(c1)]. - (iv) "distribute over composition", that is for any morphisms f and g in **C**: F(g o f) = F(g) o F(f) +
```+	(i) associate with every element C1 of C an element F(C1) of D
+	(ii) associate with every morphism f:C1->C2 of C a morphism F(f):F(C1)->F(C2) of D
+	(iii) "preserve identity", that is, for every element C1 of C: F of C1's identity morphism in C must be the identity morphism of F(C1) in D: F(1C1) = 1F(C1).
+	(iv) "distribute over composition", that is for any morphisms f and g in C: F(g o f) = F(g) o F(f)
+```