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=29b6feb3e250ad195f8884215570afa5fe639ecf;hp=8c5f4cd9b256f39c32dccf112098162a5f9fa78e;hb=c4eb20ae862369e97cadef43183d0663f3eddd11;hpb=3ca93ad8ccdf0572c3b803b86ea68dd2ad21a5f2 diff --git a/advanced_topics/monads_in_category_theory.mdwn b/advanced_topics/monads_in_category_theory.mdwn index 8c5f4cd9..29b6feb3 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,60 +104,77 @@ 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: -----→ - | | | | | η | | | ψ + F: ------> G: ------> K: ------> + | | | | | η | | | ψ | | | | v | | v - | | H: -----→ L: -----→ - | | | | | φ | | + | | H: ------> L: ------> + | | | | | φ | | | | | | v | | - | | J: -----→ | | + | | 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- η)[\_]
as:φ[\_] ∘ η[\_]
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]) + = ψ[H(C1)] ∘ K(η[C1]) +Horizontal composition is also associative, and has the same identity as vertical composition.