# Category theory/Natural transformation

### From HaskellWiki

EndreyMark (Talk | contribs) m (Better table-of-contents hierarchy) |
EndreyMark (Talk | contribs) (→Natural transformation and functor: Type inference “dissolves” the main point, thus there is no “materialized” manifestation of it in a Haskell program) |
||

Line 181: | Line 181: | ||

</haskell> | </haskell> | ||

:<math>\mathrm{Hom}{(\Lambda\Phi)(X),\;(\Lambda\Psi)(X)}</math> | :<math>\mathrm{Hom}{(\Lambda\Phi)(X),\;(\Lambda\Psi)(X)}</math> | ||

− | In fact, we have a new | + | In fact, we have a new “datatype converter”: converting not Maybe's to lists, but parser on Maybe to Parser on list. Let us notate the corresponding natural transformation with <math>\Lambda\eta</math>: |

:To each <math>X \in \mathbf{Ob}(\mathcal C)</math> we associate <math>(\Lambda\eta)_X \in \mathrm{Hom}_{\mathcal D}(\Lambda\Phi)(X),\;(\Lambda\Psi)(X))</math> | :To each <math>X \in \mathbf{Ob}(\mathcal C)</math> we associate <math>(\Lambda\eta)_X \in \mathrm{Hom}_{\mathcal D}(\Lambda\Phi)(X),\;(\Lambda\Psi)(X))</math> | ||

:<math>\Lambda\eta : \Lambda\Phi \to \Lambda\Psi</math> | :<math>\Lambda\eta : \Lambda\Phi \to \Lambda\Psi</math> | ||

:<math>(\Lambda\eta)_X = \Lambda(\eta_X)</math> | :<math>(\Lambda\eta)_X = \Lambda(\eta_X)</math> | ||

+ | |||

+ | === Natural transformation and functor === | ||

+ | |||

+ | :<math>\eta\Delta : \Phi\Delta \to \Psi\Delta</math> | ||

+ | :<math>(\eta\Delta)_X = \eta_{\Delta(X)}</math> | ||

+ | |||

+ | It can be illustrated by Haskell examples, too. Understanding it is made harder (easier?) by the fact that Haskell's type inference “dissolves” the main point, thus there is no “materialized” manifestation of it. | ||

+ | |||

== External links == | == External links == | ||

* [http://haskell.org/hawiki/CategoryTheory_2fNaturalTransformation?action=highlight&value=natural+transformation The corresponding HaWiki article] is not migrated here yet, so You can see it for more information. | * [http://haskell.org/hawiki/CategoryTheory_2fNaturalTransformation?action=highlight&value=natural+transformation The corresponding HaWiki article] is not migrated here yet, so You can see it for more information. |

## Revision as of 09:29, 4 October 2006

## Contents |

## 1 Example: maybeToList

map even $ maybeToList $ Just 5

yields the same as

maybeToList $ fmap even $ Just 5

yields: both yield

[False]

In the followings, this example will be used to illustrate the notion of natural transformation.

## 2 Definition

- Let , denote categories.
- Let be functors.
- Let . Let .

Let us define the natural transformation. It associates to each object of a morphism of in the following way (usually, not sets are discussed here, but proper classes, so I do not use term “function” for this mapping):

- . We call η
_{A}the component of η at*A*.

Thus, the following diagram commutes (in ):

### 2.1 Vertical arrows: sides of objects

… showing how the natural transformation works.

maybeToList :: Maybe a -> [a]

#### 2.1.1 Left: side of *X* object

maybeToList :: Maybe Int -> [Int] | |

Nothing |
[] |

Just 0 |
[0] |

Just 1 |
[1] |

#### 2.1.2 Right: side of *Y* object

maybeToList :: Maybe Bool -> [Bool] | |

Nothing |
[] |

Just True |
[True] |

Just False |
[False] |

### 2.2 Horizontal arrows: sides of functors

even :: Int -> Bool

#### 2.2.1 Side of Φ functor

fmap even:: Maybe Int -> Maybe Bool | |

Nothing |
Nothing |

Just 0 |
Just True |

Just 1 |
Just False |

#### 2.2.2 Side of Ψ functor

map even:: [Int] -> [Bool] | |

[] |
[] |

[0] |
[True] |

[1] |
[False] |

### 2.3 Commutativity of the diagram

both paths span between

Maybe Int -> [Bool] | ||

map even . maybeToList |
maybeToList . fmap even | |

Nothing |
[] |
[] |

Just 0 |
[True] |
[True] |

Just 1 |
[False] |
[False] |

### 2.4 Remarks

- has a more general type (even) than described hereIntegral a => a -> Bool
- 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`

).

## 3 Operations

### 3.1 Functor and natural transformation

Let us imagine a parser library, which contains functions for parsing a form. There are two kinds of cells:

- containing data which are optional (e.g. name of spouse)
- containing data which consist of an enumaration of items (e.g. names of acquired languages)

spouse :: Parser (Maybe String) languages :: Parser [String]

Let us imagine we have any processing (storing, archiving etc.) function which processes lists (or any other reason which forces us to convert our results tu list fomrat instead of lists). (Maybe all this example is unparactical and exaggerated!)

We can convert*parser*on Maybe's to achieve a

*parser*on list, then

` fmap maybeToList spouse`

Let us see the types: We start with

spouse :: Parser (Maybe String)

- Λ(Φ(
*X*))

or using notion of composing functors

- (ΛΦ)(
*X*)

We want to achieve

fmap maybeToList spouse :: Parser [String]

- Λ(Ψ(
*X*)) - (ΛΨ)(
*X*)

thus we can infer

fmap maybeToList :: Parser (Maybe [String]) -> Parser [String]

In fact, we have a new “datatype converter”: converting not Maybe's to lists, but parser on Maybe to Parser on list. Let us notate the corresponding natural transformation with Λη:

- To each we associate
- (Λη)
_{X}= Λ(η_{X})

### 3.2 Natural transformation and functor

- (ηΔ)
_{X}= η_{Δ(X)}

It can be illustrated by Haskell examples, too. Understanding it is made harder (easier?) by the fact that Haskell's type inference “dissolves” the main point, thus there is no “materialized” manifestation of it.

## 4 External links

- The corresponding HaWiki article is not migrated here yet, so You can see it for more information.
- Wikipedia's Natural transformation article