Personal tools

Category theory/Natural transformation

From HaskellWiki

< Category theory(Difference between revisions)
Jump to: navigation, search
m (Spell-check with ispell)
Current revision (15:30, 5 October 2006) (edit) (undo)
m (→Functor and natural transformation: “zero-or-one-or-many-occurrences” - parser of list of things)
 
(2 intermediate revisions not shown.)
Line 174: Line 174:
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 to list format and exclude any Maybe's). (Perhaps, all this example is impractical and exaggerated, because in real life we should solve the whole thing in other ways.)
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 to list format and exclude any Maybe's). (Perhaps, all this example is impractical and exaggerated, because in real life we should solve the whole thing in other ways.)
-
Thus, we want to build a parser combinator (we could notate it graphically with something like <math>\mathrm?\!\!\to\!\!\mathrm*</math>) which converts a “zero-ore-one-occurrence” like parser to a “zero-or-one-many-occurrences” like parser.
+
Thus, we want to build a parser combinator (we could notate it graphically with something like <math>\mathrm?\!\!\to\!\!\mathrm*</math>) which converts a “zero-ore-one-occurrence” like parser to a “zero-or-one-or-many-occurrences” like parser.
We can convert <hask>Maybe</hask> to list with <hask>maybeToList</hask>
We can convert <hask>Maybe</hask> to list with <hask>maybeToList</hask>
Line 200: Line 200:
fmap maybeToList :: Parser (Maybe [String]) -> Parser [String]
fmap maybeToList :: Parser (Maybe [String]) -> Parser [String]
</haskell>
</haskell>
-
:<math>\mathrm{Hom}{(\Lambda\Phi)(X),\;(\Lambda\Psi)(X)}</math>
+
:<math>(\Lambda\eta)_X \in \mathrm{Hom}_{\mathcal D}((\Lambda\Phi)(X),\;(\Lambda\Psi)(X))</math>
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>:
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>
Line 243: Line 243:
* [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.
* Wikipedia's [http://en.wikipedia.org/wiki/Natural_transformation Natural transformation] article
* Wikipedia's [http://en.wikipedia.org/wiki/Natural_transformation Natural transformation] article
 +
* [http://www.case.edu/artsci/math/wells/pub/ttt.html Toposes, Triples and Theories] written by Michael Barr and Charles Wells.
[[Category:Theoretical foundations]]
[[Category:Theoretical foundations]]

Current revision

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. If the examples are exaggerated and/or the definitions are incomprehensible, try #External links.

Contents

1 Definition

  • 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 (in \mathcal D):

2 Example:
maybeToList

As already mentioned 

map even $ maybeToList $ Just 5

yields the same as 

maybeToList $ fmap even $ Just 5

yields: both yield 

[False]

This example will be shown in the light of the above definition in the followings.

2.1 Vertical arrows: sides of objects

… showing how the natural transformation works.

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

2.1.1 Left: side of X object

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

2.1.2 Right: side of Y object

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

2.2 Horizontal arrows: sides of functors

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

2.2.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

2.2.2 Side of Ψ functor

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

2.3 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]

2.4 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 modify the commutative diagram, see its source code (in LaTeX using amscd).

3 Operations

3.1 Mixed

The “mixed” operations described below will be important also in understanding the definition of “monad” concept in category theory.

3.1.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 enumeration 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 to list format and exclude any Maybe's). (Perhaps, all this example is impractical and exaggerated, because in real life we should solve the whole thing in other ways.)

Thus, we want to build a parser combinator (we could notate it graphically with something like \mathrm?\!\!\to\!\!\mathrm*) which converts a “zero-ore-one-occurrence” like parser to a “zero-or-one-or-many-occurrences” like parser.

We can convert
Maybe
to list with
maybeToList
But if we want to do something similar with a parser on Maybe's to achieve a parser on list, then
maybeToList
is not enough alone, we must
fmap
it. E.g. if we want to convert a parser like
spouse
to be of the same type as
languages
: 
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]
(\Lambda\eta)_X \in \mathrm{Hom}_{\mathcal D}((\Lambda\Phi)(X),\;(\Lambda\Psi)(X))

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 X \in \mathbf{Ob}(\mathcal C) we associate (\Lambda\eta)_X \in \mathrm{Hom}_{\mathcal D}((\Lambda\Phi)(X),\;(\Lambda\Psi)(X))
\Lambda\eta : \Lambda\Phi \to \Lambda\Psi
(Λη)X = Λ(ηX)

Summary:

Let \mathcal C, \mathcal D, \mathcal E be categories
\Phi, \Psi : \mathcal C \to \mathcal D functors
\Lambda : \mathcal D \to \mathcal E functor
\eta : \Phi \to \Psi natural transformation

Then let us define a new natural transformation:

\Lambda\eta : \Lambda\Phi \to \Lambda\Psi
(Λη)X = Λ(ηX)

3.1.2 Natural transformation and functor

Let \mathcal C, \mathcal D, \mathcal E be categories
\Delta : \mathcal C \to \mathcal D functor
\Phi, \Psi : \mathcal D \to \mathcal E functors
\eta : \Phi \to \Psi natural transformation

Then let us define a new natural transformation:

\eta\Delta : \Phi\Delta \to \Psi\Delta
(ηΔ)X = ηΔ(X)

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

convert :: Maybe (Term a) -> [Term a]

Unlike seen at \mathrm?\!\!\to\!\!\mathrm*, the definition of this converter will not show much novelty: 

convert = maybeToList

the most interesting thing is done automatically by type inference.

4 External links

Retrieved from "http://www.haskell.org/haskellwiki/Category_theory/Natural_transformation"

Category: Theoretical foundations