Introduction#

Functor is the class of types f :: * -> * which can be covariantly mapped over. Mapping a function over a data structure applies the function to all the elements of the structure without changing the structure itself.

Remarks#

A Functor can be thought of as a container for some value, or a computation context. Examples are Maybe a or [a]. The Typeclassopedia article has a good write-up of the concepts behind Functors.

To be considered a real Functor, an instance has to respect the 2 following laws:

Identity

fmap id == id

Composition

fmap (f . g) = (fmap f) . (fmap g)

Common instances of Functor

Maybe

Maybe is a Functor containing a possibly-absent value:

instance Functor Maybe where
    fmap f Nothing = Nothing
    fmap f (Just x) = Just (f x)

Maybe’s instance of Functor applies a function to a value wrapped in a Just. If the computation has previously failed (so the Maybe value is a Nothing), then there’s no value to apply the function to, so fmap is a no-op.

> fmap (+ 3) (Just 3)
Just 6
> fmap length (Just "mousetrap")
Just 9
> fmap sqrt Nothing
Nothing

We can check the functor laws for this instance using equational reasoning. For the identity law,

fmap id Nothing
Nothing  -- definition of fmap
id Nothing  -- definition of id

fmap id (Just x)
Just (id x)  -- definition of fmap
Just x  -- definition of id
id (Just x)  -- definition of id

For the composition law,

(fmap f . fmap g) Nothing
fmap f (fmap g Nothing)  -- definition of (.)
fmap f Nothing  -- definition of fmap
Nothing  -- definition of fmap
fmap (f . g) Nothing  -- because Nothing = fmap f Nothing, for all f

(fmap f . fmap g) (Just x)
fmap f (fmap g (Just x))  -- definition of (.)
fmap f (Just (g x))  -- definition of fmap
Just (f (g x))  -- definition of fmap
Just ((f . g) x)  -- definition of (.)
fmap (f . g) (Just x)  -- definition of fmap

Lists

Lists’ instance of Functor applies the function to every value in the list in place.

instance Functor [] where
    fmap f [] = []
    fmap f (x:xs) = f x : fmap f xs

This could alternatively be written as a list comprehension: fmap f xs = [f x | x <- xs].

This example shows that fmap generalises map. map only operates on lists, whereas fmap works on an arbitrary Functor.

The identity law can be shown to hold by induction:

-- base case
fmap id []
[]  -- definition of fmap
id []  -- definition of id

-- inductive step
fmap id (x:xs)
id x : fmap id xs  -- definition of fmap
x : fmap id xs  -- definition of id
x : id xs  -- by the inductive hypothesis
x : xs  -- definition of id
id (x : xs)  -- definition of id

and similarly, the composition law:

-- base case
(fmap f . fmap g) []
fmap f (fmap g [])  -- definition of (.)
fmap f []  -- definition of fmap
[]  -- definition of fmap
fmap (f . g) []  -- because [] = fmap f [], for all f

-- inductive step
(fmap f . fmap g) (x:xs)
fmap f (fmap g (x:xs))  -- definition of (.)
fmap f (g x : fmap g xs)  -- definition of fmap
f (g x) : fmap f (fmap g xs)  -- definition of fmap
(f . g) x : fmap f (fmap g xs)  -- definition of (.)
(f . g) x : fmap (f . g) xs  -- by the inductive hypothesis
fmap (f . g) xs  -- definition of fmap

Functions

Not every Functor looks like a container. Functions’ instance of Functor applies a function to the return value of another function.

instance Functor ((->) r) where
    fmap f g = \x -> f (g x)

Note that this definition is equivalent to fmap = (.). So fmap generalises function composition.

Once more checking the identity law:

fmap id g
\x -> id (g x)  -- definition of fmap
\x -> g x  -- definition of id
g  -- eta-reduction
id g  -- definition of id

and the composition law:

(fmap f . fmap g) h
fmap f (fmap g h)  -- definition of (.)
fmap f (\x -> g (h x))  -- definition of fmap
\y -> f ((\x -> g (h x)) y)  -- definition of fmap
\y -> f (g (h y))  -- beta-reduction
\y -> (f . g) (h y)  -- definition of (.)
fmap (f . g) h  -- definition of fmap

Class Definition of Functor and Laws

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

One way of looking at it is that fmap lifts a function of values into a function of values in a context f.

A correct instance of Functor should satisfy the functor laws, though these are not enforced by the compiler:

fmap id = id                    -- identity
fmap f . fmap g = fmap (f . g)  -- composition

There’s a commonly-used infix alias for fmap called <$>.

infixl 4 <$>
(<$>) :: Functor f => (a -> b) -> f a -> f b
(<$>) = fmap

Replacing all elements of a Functor with a single value

The Data.Functor module contains two combinators, <$ and $>, which ignore all of the values contained in a functor, replacing them all with a single constant value.

infixl 4 <$, $>

<$ :: Functor f => a -> f b -> f a
(<$) = fmap . const

$> :: Functor f => f a -> b -> f b
($>) = flip (<$)

void ignores the return value of a computation.

void :: Functor f => f a -> f ()
void = (() <$)

Polynomial functors

There’s a useful set of type combinators for building big Functors out of smaller ones. These are instructive as example instances of Functor, and they’re also useful as a technique for generic programming, because they can be used to represent a large class of common functors.

The identity functor

The identity functor simply wraps up its argument. It’s a type-level implementation of the I combinator from SKI calculus.

newtype I a = I a

instance Functor I where
    fmap f (I x) = I (f x)

I can be found, under the name of Identity, in the Data.Functor.Identity module.

The constant functor

The constant functor ignores its second argument, containing only a constant value. It’s a type-level analogue of const, the K combinator from SKI calculus.

newtype K c a = K c

Note that K c a doesn’t contain any a-values; K () is isomorphic to Proxy. This means that K’s implementation of fmap doesn’t do any mapping at all!

instance Functor (K c) where
    fmap _ (K c) = K c

K is otherwise known as Const, from Data.Functor.Const.

The remaining functors in this example combine smaller functors into bigger ones.

Functor products

The functor product takes a pair of functors and packs them up. It’s analogous to a tuple, except that while (,) :: * -> * -> * operates on types *, (:*:) :: (* -> *) -> (* -> *) -> (* -> *) operates on functors * -> *.

infixl 7 :*:
data (f :*: g) a = f a :*: g a

instance (Functor f, Functor g) => Functor (f :*: g) where
    fmap f (fx :*: gy) = fmap f fx :*: fmap f gy

This type can be found, under the name Product, in the Data.Functor.Product module.

Functor coproducts

Just like :*: is analogous to (,), :+: is the functor-level analogue of Either.

infixl 6 :+:
data (f :+: g) a = InL (f a) | InR (g a)

instance (Functor f, Functor g) => Functor (f :+: g) where
    fmap f (InL fx) = InL (fmap f fx)
    fmap f (InR gy) = InR (fmap f gy)

:+: can be found under the name Sum, in the Data.Functor.Sum module.

Functor composition

Finally, :.: works like a type-level (.), taking the output of one functor and plumbing it into the input of another.

infixr 9 :.:
newtype (f :.: g) a = Cmp (f (g a))

instance (Functor f, Functor g) => Functor (f :.: g) where
    fmap f (Cmp fgx) = Cmp (fmap (fmap f) fgx)

The Compose type can be found in Data.Functor.Compose

Polynomial functors for generic programming

I, K, :*:, :+: and :.: can be thought of as a kit of building blocks for a certain class of simple datatypes. The kit becomes especially powerful when you combine it with fixed points because datatypes built with these combinators are automatically instances of Functor. You use the kit to build a template type, marking recursive points using I, and then plug it into Fix to get a type that can be used with the standard zoo of recursion schemes.

This “kit” approach to designing datatypes is the idea behind generic programming libraries such as generics-sop. The idea is to write generic operations using a kit like the one presented above, and then use a type class to convert arbitrary datatypes to and from their generic representation:

class Generic a where
    type Rep a  -- a generic representation built using a kit
    to :: a -> Rep a
    from :: Rep a -> a

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

Deriving Functor

The DeriveFunctor language extension allows GHC to generate instances of Functor automatically.

{-# LANGUAGE DeriveFunctor #-}

data List a = Nil | Cons a (List a) deriving Functor

-- instance Functor List where            -- automatically defined
--   fmap f Nil = Nil
--   fmap f (Cons x xs) = Cons (f x) (fmap f xs)

map :: (a -> b) -> List a -> List b
map = fmap