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: -