A personal blog about computer science topics.

A Homomorphism of Categories
Posted on Aug 30 2023 ~ 4 min read
#category theory  #haskell 

Functor  Functor Applicative Applicative Functor->Applicative Traversable Traversable Functor->Traversable Applicative->Traversable Alternative Alternative Applicative->Alternative Monad Monad Applicative->Monad Apply Apply Apply->Applicative Semigroup Semigroup Semigroup->Apply Monoid Monoid Semigroup->Monoid MonadPlus MonadPlus Monad->MonadPlus MonadFix MonadFix Monad->MonadFix ArrowApply ArrowApply Monad->ArrowApply Monoid->Applicative Monoid->Alternative Monoid->Monad Monoid->MonadPlus Category Category Monoid->Category ArrowPlus ArrowPlus Monoid->ArrowPlus Foldable Foldable Monoid->Foldable Arrow Arrow Category->Arrow Foldable->Traversable Arrow->ArrowApply ArrowChoice ArrowChoice Arrow->ArrowChoice ArrowZero ArrowZero Arrow->ArrowZero ArrowZero->ArrowPlus

A functor, in category theory, is a structural-preserving mapping between categories. Given two categories, C \mathcal{C} and D \mathcal{D} , a functor F : C D F: \mathcal{C} \rightarrow \mathcal{D} associates each object in C \mathcal{C} with an object in D \mathcal{D} and each morphism f : A B f : A \rightarrow B in C \mathcal{C} with a morphism F ( f ) : F ( A ) F ( B ) F(f) : F(A) \rightarrow F(B) in D \mathcal{D} , such that:

  • F ( i d A ) = i d F ( A ) F(id_{A}) = id_{F(A)} for every object A A in C \mathcal{C} ,

  • F ( g f ) = F ( g ) F ( f ) F(g \circ f) = F(g) \circ F(f) for all morphisms f : A B f : A \rightarrow B and g : B C g : B \rightarrow C in C \mathcal{C}

That is, functors must preserve identity morphisms and composition of morphisms. We can rephrase these conditions using the subsequent commutative diagram:

\begin{xy} \xymatrix{ F(A) \ar[r]_{F(f)} \ar@/^1.5pc/[rr]^{F(g\ \circ f)} & F(B) \ar[r]_{F(g)} & F(C) \\ A \ar[r]^{f} \ar@/_1.5pc/[rr]_{g\ \circ\ f} \ar[u]_{F} & B \ar[r]^{g} \ar[u]_{F} & C \ar[u]_{F} } \end{xy}


A Functor in Haskell is a typeclass that represents a type that can be mapped over, meaning that you can apply a function to every element of the type without changing its structure.

Haskell Definition of Functor (Interface)

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

The following condition must always hold:

fmap id == id                   -- Identity
fmap (. g) == fmap f . fmap g -- Composition

An Instance of Functor, the List Functor

instance Functor [] where
    fmap = map

Another Instance, the Maybe Functor

instance  Functor Maybe  where
    fmap _ Nothing       = Nothing
    fmap f (Just a)      = Just (f a)

All of the above is already implemented in the standard Haskell library, so you can simply open an interactive Haskell interpreter (ghci) and test the following examples.

ghci> fmap (*2) [1,2,3]

ghci> fmap id [1,2,3]

ghci> fmap (++ "B") (Just "A")
Just "AB"

ghci> fmap (++ "B") Nothing

Some more examples contains basically everything that can be mapped over:

  • Either Functor: If the Either contains a right value, it applies the function to the value, else it leaves the left value untouched.
  • IO Functor: Used to construct computations which perform I/O and computes a result.
  • Future Functor: Applies a function to a value in a future (a sort of placeholder object for a value that is initially unknown).
  • Const Functor: Ignores its function argument and always yields the same value.
  • Identity Functor: Simply applies the given function to its argument without any additional behavior.
  • Function Functor (in the sense of (a -> b) -> (c -> d)): Applies a function to the return type of another function.
  • Tree Functor: Applies a function to every node in a tree.
  • Pair Functor: Applies the function to the second element of a pair.
  • Reader Functor: Applies a function to the result of another function (a “reader” of some shared environment)
  • State Functor: Applies a function to the result of a stateful computation.
  • Writer Functor: Applies a function to the result while preserving some additional logging or output.


  1. 0.The diagram displayed at the top of this post is a modified version of Brent Yorgey's Typeclassopedia diagram
  2. 1.Functor in ncatlab