+**Don't try to read this yet!!! Many substantial edits are still in process.
+Will be ready soon.**
+
+**Caveats**: I really don't know much category theory. Just enough to put this
+together. Also, this really is "put together." I haven't yet found an
+authoritative source (that's accessible to a category theory beginner like
+myself) that discusses the correspondence between the category-theoretic and
+functional programming uses of these notions in enough detail to be sure that
+none of the pieces here is misguided. In particular, it wasn't completely
+obvious how to map the polymorphism on the programming theory side into the
+category theory. And I'm bothered by the fact that our `<=<` operation is only
+partly defined on our domain of natural transformations. But these do seem to
+me to be the reasonable way to put the pieces together. We very much welcome
+feedback from anyone who understands these issues better, and will make
+corrections.
+
+
+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:
-
-1. Monoids
-----------
-A <monoid> is a structure 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:
(i) s1*s2 etc are also in S
(ii) (s1*s2)*s3 = s1*(s2*s3)
Some examples of monoids are:
- (a) finite strings of an alphabet A, with * being concatenation and z being the empty string
-
- (b) all functions X->X over a set X, with * being composition and z being the identity function over X
-
- (c) the natural numbers with * 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>.)
-
- (d) the natural numbers with * being multiplication and z being 1 constitute a different monoid over the same set as in (c).
-
-
+* finite strings of an alphabet A, with * being concatenation and z being the empty string
+* all functions X->X over a set X, with * being composition and z being the identity function over X
+* the natural numbers with * 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**.)
+* if we let * be multiplication and z be 1, we get different monoids over the same sets as in the previous item.
-2. 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 given 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."
+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.
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.
(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:a->b:
- id[b] o f = f = f o id[a]
+ (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]
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.)
+
Some examples of categories are:
- (a) any category 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 is the identity function over that set.
+* 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 is the identity function over that set.
+
+* any monoid `(S,*,z)` 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 s3=s1+s2. The identity morphism for the (single) category element x is the monoid's identity z.
- (b) any monoid (S,*,z) 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. The result of composing the morphism consisting of s1 with the morphism s2 is the morphism s3, where s3=s1+s2. The identity morphism on the (single) category element x is the monoid's identity z.
+* a **preorder** is a structure `(S, <=)` consisting of a reflexive, transitive, binary relation on a set S. It need not be connected (that is, there may be members `x`,`y` of `S` such that neither `x<=y` nor `y<=x`). It need not be anti-symmetric (that is, there may be members `s1`,`s2` of `S` such that `s1<=s2` and `s2<=s1` but `s1` and `s2` are not identical).
- (c) a <preorder> <= is a binary relation on a set S which is reflexive and transitive. It need not be connected (that is, there may be members x,y of S such that neither x<=y nor y<=x). It need not be anti-symmetric (that is, there may be members s1,s2 of S such that s1<=s2 and s2<=s1 but s1 and s2 are not identical).
Some examples:
- * sentences ordered by logical implication ("p and p" implies and is implied by "p", but these sentences are not identical).
- * sets ordered by size
- Any pre-order (S,<=) 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 s1<=s2.
+
+ * 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)
+ * sets ordered by size (this illustrates it too)
+
+ Any pre-order `(S,<=)` 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 s1<=s2.
3. 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:
- (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:
+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:
+
+<OL type=i>
+<LI>associate with every element c1 of C an element F(c1) of D
+<LI>associate with every morphism f:c1->c2 of C a morphism F(f):F(c1)->F(c2) of D
+<LI>"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:
+<LI>"distribute over composition", that is for any morphisms f and g in C:
F(g o f) = F(g) o F(f)
+</OL>
-A functor that maps a category to itself is called an <endofunctor>. The (endo)functor that maps every element and morphism of C to itself is denoted 1C.
+A functor that maps a category to itself is called an **endofunctor**. The (endo)functor that maps every element and morphism of `C` to itself is denoted `1C`.
-How functors compose:
-If F is a functor from category C to category D, and H is a functor from category D to category E, then HF is a functor which maps every element c1 of C to element H(F(c1)) of E, and maps every morphism f of C to morphism H(F(f)) of E.
+How functors compose: If `G` is a functor from category `C` to category `D`, and `K` is a functor from category `D` to category `E`, then `KG` is a functor which maps every element `c1` of `C` to element `K(G(c1))` of `E`, and maps every morphism `f` of `C` to morphism `K(G(f))` of `E`.
I'll assert without proving that functor composition is associative.
4. Natural Transformation
-------------------------
-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.
+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.
Where G and H are functors from category C to category D, a natural transformation eta between G and H is a family of morphisms eta[c1]:G(c1)->H(c1) in D for each element c1 of C. That is, eta[c1] has as source c1's image under G in D, and as target c1's image under H in D. The morphisms in this family must also satisfy the constraint:
for every morphism f:c1->c2 in C:
| | J: ------> | |
-----+ +--------+ +------------+ +-------
-(eta F) is a natural transformation from the (composite) functor GF to the composite functor HF, such that where b1 is an element of category B, (eta F)[b1] = eta[F(b1)]---that is, the morphism in D that eta assigns to the element F(b1) of C.
+Then (eta F) is a natural transformation from the (composite) functor GF to the composite functor HF, such that where b1 is an element of category B, (eta F)[b1] = eta[F(b1)]---that is, the morphism in D that eta assigns to the element F(b1) of C.
-(K eta) is a natural transformation from the (composite) functor KG to the (composite) functor KH, such that where c1 is an element of category C, (K eta)[c1] = K(eta[c1])---that is, the morphism in E that K assigns to the morphism eta[c1] of D.
+And (K eta) is a natural transformation from the (composite) functor KG to the (composite) functor KH, such that where c1 is an element of category C, (K eta)[c1] = K(eta[c1])---that is, the morphism in E that K assigns to the morphism eta[c1] of D.
-(phi -v- eta) is a natural transformation from G to J; this is known as a "vertical composition". We will rely later on this:
+(phi -v- eta) is a natural transformation from G to J; this is known as a "vertical composition". We will rely later on this, where f:c1->c2:
phi[c2] o H(f) o eta[c1] = phi[c2] o H(f) o eta[c1]
-------------
by naturalness of phi, is:
---------
In earlier days, these were also called "triples."
-A <monad> is a structure consisting of an (endo)functor M from some category C to itself, along with some natural transformations, which we'll specify in a moment.
+A **monad** is a structure consisting of an (endo)functor M from some category C to itself, along with some natural transformations, which we'll specify in a moment.
Let T be a set of natural transformations p, each being between some (variable) functor P and another functor which is the composite MP' of M and a (variable) functor P'. That is, for each element c1 in C, p assigns c1 a morphism from element P(c1) to element MP'(c1), satisfying the constraints detailed in the previous section. For different members of T, the relevant functors may differ; that is, p is a transformation from functor P to MP', q is a transformation from functor Q to MQ', and none of P,P',Q,Q' need be the same.