Personal tools

Category theory/Functor

From HaskellWiki

< Category theory(Difference between revisions)
Jump to: navigation, search

Revision as of 15:27, 3 July 2007


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

  1. If f:A\to B in \mathcal{A}, then F(f):F(A)\to F(B) in \mathcal{B}
  2. 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)
  3. For all objects A in \mathcal{A}, idF(A) = F(idA)

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

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)