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=3c80bbbcb4b592b5e8c2a936966b0d68278ef565;hp=41b17c5205de8518033ac047d3f2e452a8cc3777;hb=9583e70a7aa87c31b70285030ad3e988d1005ef8;hpb=31786296de9b1c4456c8b85c36c0897eaf02d1c2 diff --git a/advanced_topics/monads_in_category_theory.mdwn b/advanced_topics/monads_in_category_theory.mdwn index 41b17c52..3c80bbbc 100644 --- a/advanced_topics/monads_in_category_theory.mdwn +++ b/advanced_topics/monads_in_category_theory.mdwn @@ -1,7 +1,9 @@ **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 +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 @@ -26,24 +28,25 @@ A **monoid** is a structure `(S, *, z)` consisting of an associative binary oper Some examples of monoids are: -* 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. +* 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. 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. (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 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. +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.) @@ -52,31 +55,28 @@ Some examples of categories are: * 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. +* 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`. -* 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). +* 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). Some examples: * 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. - + 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: +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)]. -
  4. "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(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) 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`. @@ -90,53 +90,54 @@ I'll assert without proving that functor composition is associative. ------------------------- 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: +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: eta[c2] o G(f) = H(f) o eta[c1] -That is, the morphism via G(f) from G(c1) to G(c2), and then via eta[c2] to H(c2), is identical to the morphism from G(c1) via eta[c1] to H(c1), and then via H(f) from H(c1) to H(c2). +That is, the morphism via `G(f)` from `G(c1)` to `G(c2)`, and then via `eta[c2]` to `H(c2)`, is identical to the morphism from `G(c1)` via `eta[c1]` to `H(c1)`, and then via `H(f)` from `H(c1)` to `H(c2)`. How natural transformations compose: -Consider four categories B,C,D, and E. -Let F be a functor from B to C; G,H, and J be functors from C to D; and K and L be functors from D to E. 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: +Consider four categories `B`, `C`, `D`, and `E`. Let `F` be a functor from `B` to `C`; `G`, `H`, and `J` be functors from `C` to `D`; and `K` and `L` be functors from `D` to `E`. 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: + + - B -+ +--- C --+ +---- D -----+ +-- E -- + | | | | | | + F: ------> G: ------> K: ------> + | | | | | eta | | | psi + | | | | v | | v + | | H: ------> L: ------> + | | | | | phi | | + | | | | v | | + | | J: ------> | | + -----+ +--------+ +------------+ +------- -- B -+ +--- C --+ +---- D -----+ +-- E -- - | | | | | | - F: ------> G: ------> K: ------> - | | | | | eta | | | psi - | | | | v | | v - | | H: ------> L: ------> - | | | | | phi | | - | | | | v | | - | | J: ------> | | ------+ +--------+ +------------+ +------- +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`. -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. +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`. -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, where `f:c1->c2`: -(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: - -------------- + +by naturalness of phi, is: + phi[c2] o H(f) o eta[c1] = J(f) o phi[c1] o eta[c1] - -------------- - by naturalness of eta, is: - -------------- + +by naturalness of eta, is: + phi[c2] o eta[c2] o G(f) = J(f) o phi[c1] o eta[c1] - ----------------- ----------------- -Hence, we can define (phi -v- eta)[c1] as: phi[c1] o eta[c1] and rely on it to satisfy the constraints for a natural transformation from G to J: - ----------------- ----------------- + +Hence, we can define `(phi -v- eta)[c1]` as: `phi[c1] o eta[c1]` and rely on it to satisfy the constraints for a natural transformation from `G` to `J`: + (phi -v- eta)[c2] o G(f) = J(f) o (phi -v- eta)[c1] I'll assert without proving that vertical composition is associative and has an identity, which we'll call "the identity transformation." -(psi -h- eta) 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: +`(psi -h- eta)` 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: (phi -h- eta)[c1] = L(eta[c1]) o psi[G(c1)] = psi[H(c1)] o K(eta[c1]) @@ -145,11 +146,11 @@ Horizontal composition is also associative, and has the same identity as vertica -5. Monads ---------- +Monads +------ 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.