Personal tools

Category theory/Functor

From HaskellWiki

< Category theory
Revision as of 15:12, 3 July 2007 by Jcast (Talk | contribs)

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search


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 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)