Haskell Language Functors in Category Theory


A Functor is defined in category theory as a structure-preserving map (a 'homomorphism') between categories. Specifically, (all) objects are mapped to objects, and (all) arrows are mapped to arrows, such that the category laws are preserved.

The category in which objects are Haskell types and morphisms are Haskell functions is called Hask. So a functor from Hask to Hask would consist of a mapping of types to types and a mapping from functions to functions.

The relationship that this category theoretic concept bears to the Haskell programming construct Functor is rather direct. The mapping from types to types takes the form of a type f :: * -> *, and the mapping from functions to functions takes the form of a function fmap :: (a -> b) -> (f a -> f b). Putting those together in a class,

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

fmap is an operation that takes a function (a type of morphism), :: a -> b, and maps it to another function, :: f a -> f b. It is assumed (but left to the programmer to ensure) that instances of Functor are indeed mathematical functors, preserving Hask's categorical structure:

fmap (id {- :: a -> a -})  ==  id {- :: f a -> f a -}
fmap (h . g)               ==  fmap h . fmap g

fmap lifts a function :: a -> b into a subcategory of Hask in a way that preserves both the existence of any identity arrows, and the associativity of composition.

The Functor class only encodes endofunctors on Hask. But in mathematics, functors can map between arbitrary categories. A more faithful encoding of this concept would look like this:

class Category c where
    id  :: c i i
    (.) :: c j k -> c i j -> c i k

class (Category c1, Category c2) => CFunctor c1 c2 f where
    cfmap :: c1 a b -> c2 (f a) (f b)

The standard Functor class is a special case of this class in which the source and target categories are both Hask. For example,

instance Category (->) where        -- Hask
    id    = \x -> x
    f . g = \x -> f (g x)

instance CFunctor (->) (->) [] where
    cfmap = fmap