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=3e34f85b8e2841bacb7675190bd3e30ed77b425d;hp=8c5f4cd9b256f39c32dccf112098162a5f9fa78e;hb=7026bf51a9211af0586d30d49b61ed187f897a79;hpb=3ca93ad8ccdf0572c3b803b86ea68dd2ad21a5f2 diff --git a/advanced_topics/monads_in_category_theory.mdwn b/advanced_topics/monads_in_category_theory.mdwn index 8c5f4cd9..3e34f85b 100644 --- a/advanced_topics/monads_in_category_theory.mdwn +++ b/advanced_topics/monads_in_category_theory.mdwn @@ -82,12 +82,11 @@ A **functor** is a "homomorphism", that is, a structure-preserving mapping, betw
(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 + (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). + 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 ∘ f) = F(g) ∘ F(f) @@ -105,17 +104,21 @@ 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. -Where `G` and `H` are functors from category C to category D, a natural transformation η between `G` and `H` is a family of morphisms η[C1]:G(C1)→H(C1)` in D for each element `C1` of C. That is, η[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 η between `G` and `H` is a family of morphismsη[C1]:G(C1)→H(C1)
in D for each element `C1` of C. That is,η[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: η[C2] ∘ G(f) = H(f) ∘ η[C1] ++ for every morphism f:C1→C2 in C: + η[C2] ∘ G(f) = H(f) ∘ η[C1] +-That is, the morphism via `G(f)` from `G(C1)` to `G(C2)`, and then via η[C2]` to `H(C2)`, is identical to the morphism from `G(C1)` via η[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η[C2]
to `H(C2)`, is identical to the morphism from `G(C1)` viaη[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 η be a natural transformation from `G` to `H`; φ be a natural transformation from `H` to `J`; and ψ be a natural transformation from `K` to `L`. Pictorally: +- B -+ +--- C --+ +---- D -----+ +-- E -- | | | | | | F: -----→ G: -----→ K: -----→ @@ -126,39 +129,52 @@ Consider four categories B, C, D, and E. Let `F` be | | | | v | | | | J: -----→ | | -----+ +--------+ +------------+ +------- +-Then `(η 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, `(η F)[b1] = η[F(b1)]`---that is, the morphism in D that η assigns to the element `F(b1)` of C. +Then(η 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,(η F)[B1] = η[F(B1)]
---that is, the morphism in D thatη
assigns to the element `F(B1)` of C. -And `(K η)` 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 η)[C1] = K(η[C1])`---that is, the morphism in E that `K` assigns to the morphism η[C1]` of D. +And(K η)
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 η)[C1] = K(η[C1])
---that is, the morphism in E that `K` assigns to the morphismη[C1]
of D. -`(φ -v- η)` 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`: +(φ -v- η)
is a natural transformation from `G` to `J`; this is known as a "vertical composition". We will rely later on this, wheref:C1→C2
: +φ[C2] ∘ H(f) ∘ η[C1] = φ[C2] ∘ H(f) ∘ η[C1] +-by naturalness of φ, is: +by naturalness ofφ
, is: +φ[C2] ∘ H(f) ∘ η[C1] = J(f) ∘ φ[C1] ∘ η[C1] +-by naturalness of η, is: +by naturalness ofη
, is: +φ[C2] ∘ η[C2] ∘ G(f) = J(f) ∘ φ[C1] ∘ η[C1] +-Hence, we can define `(φ -v- η)[x]` as: φ[x] ∘ η[x]` and rely on it to satisfy the constraints for a natural transformation from `G` to `J`: +Hence, we can define(φ -v- η)[x]
as:φ[x] ∘ η[x]
and rely on it to satisfy the constraints for a natural transformation from `G` to `J`: +(φ -v- η)[C2] ∘ G(f) = J(f) ∘ (φ -v- η)[C1] +An observation we'll rely on later: given the definitions of vertical composition and of how natural transformations compose with functors, it follows that: +((φ -v- η) F) = ((φ F) -v- (η F)) +I'll assert without proving that vertical composition is associative and has an identity, which we'll call "the identity transformation." -`(ψ -h- η)` 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: +(ψ -h- η)
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: +(φ -h- η)[C1] = L(η[C1]) ∘ ψ[G(C1)] = ψ[H(C1)] ∘ K(η[C1]) +Horizontal composition is also associative, and has the same identity as vertical composition.