Category theory/Functor

From HaskellWiki

< Category theory(Difference between revisions)

Current revision

1 Definition of a Functor

1 Definition of a Functor

Given that $\mathcal{A}$ and $\mathcal{B}$ are categories, a functor $F:\mathcal{A}\to\mathcal{B}$ is a pair of mappings $(F_{objects}:\mathrm{Ob}(\mathcal{A})\to\mathrm{Ob}(\mathcal{B}), F_{arrows}:\mathrm{Ar}(\mathcal{A})\to\mathrm{Ar}(\mathcal{B}))$ (the subscripts are generally omitted in practice).

1.1 Axioms

If $f:A\to B$ in $\mathcal{A}$ , then $F(f):F(A)\to F(B)$ in $\mathcal{B}$
If $f:B\to C$ in $\mathcal{A}$ and $g:A\to B$ in $\mathcal{A}$ , then $F(f)\circ F(g) = F(f\circ g)$
For all objects $A$ in $\mathcal{A}$ , $i d F (A) = F (i d A)$

1.2 Examples of functors

$\mathrm{Free}:\mathrm{Set}\to\mathrm{Mon}$ , the functor giving the free monoid over a set
$\mathrm{Free}:\mathrm{Set}\to\mathrm{Grp}$ , the functor giving the free group over a set
Every monotone function is a functor, when the underlying partial orders are viewed as categories
Every monoid homomorphism is a functor, when the underlying monoids are viewed as categories

1.3 Functor operations

For all categories $\mathcal{C}$ , there is an identity functor $Id_{\mathcal{C}}$ (again, the subscript is usually ommitted) given by the rule $F (a) = a$ for all objects and arrows $a$ .
If $F:\mathcal{B}\to\mathcal{C}$ and $G:\mathcal{A}\to\mathcal{B}$ , then $F\circ G:\mathcal{A}\to\mathcal{C}$ , with composition defined component-wise.

These operations will be important in the definition of a monad.

1.4 The category Cat

The existence of identity and composition functors implies that, for any well-defined collection of categories $E$ , there exists a category $Cat E$ whose arrows are all functors between categories in $E$ . Since no category can include itself as an object, there can be no category of all categories, but it is common and useful to designate a category small when the collection of objects is a set, and define Cat to be the category whose objects are all small categories and whose arrows are all functors on small categories.

1.5 Functors in Haskell

Properly speaking, a functor in the category Haskell is a pair of a set-theoretic function on Haskell types and a set-theoretic function on Haskell functions satisfying the axioms. However, Haskell being a functional language, Haskellers are only interested in functors where both the object and arrow mappings can be defined and named in Haskell; this effectively restricts them to functors where the object map is a Haskell data constructor and the arrow map is a polymorphic function, the same constraints imposed by the class Functor:

class Functor f where
  fmap :: (a -> b) -> (f a -> f b)

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

@@ Line 25: / Line 25: @@
 === The category Cat ===
-The existence of identity and composition functors implies that, for any well-defined collection of categories <math>E</math>, there exists a category <math>\mathrm{Cat}_E</math> whose arrows are all functors between categories in <math>E</math>.  Since no category can include itself as an object, there can be no category of all categories, but it is command and useful to designate a category '''small''' when the collection of objects is a set, and define Cat to be the category whose objects are all small categories and whose arrows are all functors on small categories.
+The existence of identity and composition functors implies that, for any well-defined collection of categories <math>E</math>, there exists a category <math>\mathrm{Cat}_E</math> whose arrows are all functors between categories in <math>E</math>.  Since no category can include itself as an object, there can be no category of all categories, but it is common and useful to designate a category '''small''' when the collection of objects is a set, and define Cat to be the category whose objects are all small categories and whose arrows are all functors on small categories.
 === Functors in Haskell ===

Personal tools

Views