Personal tools

Category theory/Natural transformation

From HaskellWiki

< Category theory(Difference between revisions)
Jump to: navigation, search
(Fix broken link)
(Commutative diagram: Definition of notion ``natural transformation'')
Line 15: Line 15:
 
=== Commutative diagram ===
 
=== Commutative diagram ===
   
Let <math>\mathcal C</math>, <math>\mathcal D</math> denote categories.
+
* Let <math>\mathcal C</math>, <math>\mathcal D</math> denote categories.
Let <math>\Phi, \Psi : \mathcal C \to \mathcal D</math> be functors.
+
* Let <math>\Phi, \Psi : \mathcal C \to \mathcal D</math> be functors.
Let us define the <math>\eta : \Phi \to \Psi</math> natural transformation.
+
* Let <math>X, Y \in \mathbf{Ob}(\mathcal C)</math>. Let <math>f \in \mathrm{Hom}_{\mathcal C}(X, Y)</math>.
  +
Let us define the <math>\eta : \Phi \to \Psi</math> natural transformation. It associates to each object of <math>\mathcal{C}</math> a morphism of <math>\mathcal{D}</math> in the following way (usually, not sets are discussed here, but proper classes, so I do not use term “function” for this <math>\mathbf{Ob}(\mathcal C) \to \mathbf{Mor}(\mathcal D)</math> mapping):
  +
* <math>\forall A \in \mathbf{Ob}(\mathcal C) \longmapsto \eta_A \in \mathrm{Hom}_{\mathcal D}(\Phi(A), \Psi(A))</math>. We call <math>\eta_A</math> the component of <math>\eta</math> at ''A''.
  +
* <math>\eta_Y \cdot \Phi(f) = \Psi(f) \cdot \eta_X</math>
  +
Thus, the following diagram commutes:
   
............
+
[[Image:natural_transformation.png|center]]
 
[[Image:natural_transformation.png]]
 
   
 
=== Vertical arrows: sides of objects ===
 
=== Vertical arrows: sides of objects ===

Revision as of 14:37, 3 October 2006

Contents

1 Example:
maybeToList

 map even $ maybeToList $ Just 5

yields the same as

 maybeToList $ fmap even $ Just 5

yields: both yield

 [False]

1.1 Commutative diagram

  • Let \mathcal C, \mathcal D denote categories.
  • Let \Phi, \Psi : \mathcal C \to \mathcal D be functors.
  • Let X, Y \in \mathbf{Ob}(\mathcal C). Let f \in \mathrm{Hom}_{\mathcal C}(X, Y).

Let us define the \eta : \Phi \to \Psi natural transformation. It associates to each object of \mathcal{C} a morphism of \mathcal{D} in the following way (usually, not sets are discussed here, but proper classes, so I do not use term “function” for this \mathbf{Ob}(\mathcal C) \to \mathbf{Mor}(\mathcal D) mapping):

  • \forall A \in \mathbf{Ob}(\mathcal C) \longmapsto \eta_A \in \mathrm{Hom}_{\mathcal D}(\Phi(A), \Psi(A)). We call ηA the component of η at A.
  • \eta_Y \cdot \Phi(f) = \Psi(f) \cdot \eta_X

Thus, the following diagram commutes:

Natural transformation.png

1.2 Vertical arrows: sides of objects

… showing how the natural transformation works.

\eta : \Phi \to \Psi
maybeToList :: Maybe a -> [a]

1.2.1 Left: side of X object

\eta_X : \Phi(X) \to \Psi(X)
maybeToList :: Maybe Int -> [Int]
Nothing
[]
Just 0
[0]
Just 1
[1]

1.2.2 Right: side of Y object

\eta_Y : \Phi(Y) \to \Psi(Y)
maybeToList :: Maybe Bool -> [Bool]
Nothing
[]
Just True
[True]
Just False
[False]

1.3 Horizontal arrows: sides of functors

f : X \to Y
 even :: Int -> Bool

1.3.1 Side of Φ functor

\Phi(f) : \Phi(X) \to \Phi(Y)
fmap even:: Maybe Int -> Maybe Bool
Nothing
Nothing
Just 0
Just True
Just 1
Just False

1.3.2 Side of Ψ functor

\Psi(f) : \Psi(X) \to \Psi(Y)
map even:: [Int] -> [Bool]
[]
[]
[0]
[True]
[1]
[False]

1.4 Commutativity of the diagram

\Psi(f) \cdot \eta_X = \eta_Y \cdot \Phi(f)

both paths span between

\Phi(X) \to \Psi(Y)
Maybe Int -> [Bool]
map even . maybeToList
maybeToList . fmap even
Nothing
[]
[]
Just 0
[True]
[True]
Just 1
[False]
[False]

1.5 Remarks

  • even
    has a more general type (
    Integral a => a -> Bool
    ) than described here
  • Words “side”, “horizontal”, “vertical”, “left”, “right” serve here only to point to the discussed parts of a diagram, thus, they are not part of the scientific terminology.
  • If You want to modifiy the #Commutative diagram, see its source code (in LaTeX using amscd).

1.6 External links