From: Jim Pryor Date: Tue, 2 Nov 2010 00:36:35 +0000 (-0400) Subject: tweak cat theory X-Git-Url: http://lambda.jimpryor.net/git/gitweb.cgi?p=lambda.git;a=commitdiff_plain;h=31786296de9b1c4456c8b85c36c0897eaf02d1c2 tweak cat theory Signed-off-by: Jim Pryor --- diff --git a/advanced_topics/monads_in_category_theory.mdwn b/advanced_topics/monads_in_category_theory.mdwn index 56c897a6..41b17c52 100644 --- a/advanced_topics/monads_in_category_theory.mdwn +++ b/advanced_topics/monads_in_category_theory.mdwn @@ -1,9 +1,24 @@ +**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: -**Don't try to read this yet!!! Many substantial edits are still in process. Will be ready soon.** - -1. Monoids ----------- -A 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) @@ -11,59 +26,61 @@ A is a structure consisting of an associative binary operation * over s 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 ). 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 .) - - (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 is a generalization of a monoid. A category consists of a class of elements, and a class of 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 <= 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 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: + +
    +
  1. associate with every element c1 of C an element F(c1) of D +
  2. associate with every morphism f:c1->c2 of C a morphism F(f):F(c1)->F(c2) of D +
  3. "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: +
  4. "distribute over composition", that is for any morphisms f and g in C: F(g o f) = F(g) o F(f) +
-A functor that maps a category to itself is called an . 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. @@ -71,7 +88,7 @@ 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. 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: @@ -96,12 +113,12 @@ Let F be a functor from B to C; G,H, and J be functors from C to D; and K and L | | 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: @@ -132,7 +149,7 @@ Horizontal composition is also associative, and has the same identity as vertica --------- In earlier days, these were also called "triples." -A 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.