Part 1 - Exploring the Haskell Functor

The is part of a 3 part series of Functors, Applicatives and Monads in Haskell:


So this article is a workthrough of what a Functor is, as I try to develop an intuition for what they are. The Wikipedia definition is a little opaque, unless you have a really good grasp of mathematics, and in particular, Category Theory:

In mathematics, specifically category theory, a functor is a map between categories.

But what does this actually mean?

In order to approach this, we'll explore it from a couple of angles, but the simplest to start with is Haskell.

Haskell Functor

Definition

So in Haskell, a Functor is a type that (minimally) has an fmap instance. To be a proper functor it also needs to obey some laws. And that's basically it. So at it's simplest:

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

Recall that a functor is "a map between categories", and note the fmap type definition above. In words, fmap takes a (function that takes a value of type a and returns a value of type b) and a thing f a, and returns an f b thing. The f is the type that has the functor instance. Before exploring that, let's look at the laws that the Haskell Functor instance should have:

Laws

The laws are really important. They define how fmap functions must behave in order to be composable. And in Haskell, composition is a defining aspect of producing programs.

Functors must preserve identity morphisms

fmap id == id

Or, to put it another way, id is the identity function, and whatever you pass to it, you get back. Thus, the above says that the function fmap id must do the same thing has just applying id.

If it looks a bit odd, remember that in Haskell, all functions take one parameter and return a parameter. The -> is the function, or morphism. Thus, take a look at the type signature of fmap again:

fmap :: (a -> b) -> f a -> f b

It looks like fmap takes two parameters, but the hint is in the -> (morphism) or function sigil. fmap is actually a function that takes a function ((a -> b)) and returns a function that takes an f a and returns an f b (or as a haskell function: f a -> f b). Or to put it another way:

fmap :: (a -> b) -> (f a -> f b)

So the first law really says that fmap id must be identical to id i.e.

fmap id :: f a -> f a   -- but with the proviso that they are the SAME a
                        -- (value)

Functors preserve composition of morphisms

fmap (h . g)  ==  fmap h . fmap g

Normally, this would be written as fmap (f . g) ..., but that would be confusing with the f meaning functor above, so we'll use h instead in this description.

Recall that (.) is the composition function, and h . g reads as h after g or h (g a). i.e. h is applied to the return value of g applied to a.

h . g                -- the composition of h and g which becomes:
(b -> c) . (a -> b)  -- and simplifies to this:
(a -> c)

Or h . g is the function a -> c or what the composed "h after g" function does

i.e. h is the function (b -> c), g is the function (a -> b) and the return value is a function (a -> c). Note that the last function doesn't have braces, which is just a convention. It could be written like:

h . g === (b -> c) -> (a -> b) -> (a -> c)

So we have, in terms of function type declarations, where a, b and c are polymorphic types, g and h are functions of one parameter, and f is a type that is an instance of the type class Functor:

h :: b -> c
g :: a -> b
h . g === (b -> c) . (a -> b) === (a -> c)
h . g :: a -> c
fmap h :: Functor f => f b -> f c
fmap g :: Functor f => f a -> f b

-- and thus, by substition
fmap (h . g) === f a -> f c

-- and with a bit of working:
(fmap h) . (fmap g) === f a -> f c
-- i.e. substituting (fmap h) and (fmap g) we get the identity:
(f b -> f c) . (f a -> f b) === f a -> f c

(Note that the === isn't valid Haskell; it's just me writing that they are the same thing.)

So that's the laws. Still wondering what a functor is?

Developing the intuition

So by now you may be thinking that the fmap function is the functor? Let's see if that fits. A functor is a map between categories, so in theory a functor (i.e. the function) should take a category as a parameter and return a category.

In Haskell, the Functor type class constrains it to be the same category. In this case, category is actually the type that has an instance in the Functor type class. So in fmap:

fmap :: Functor f => (a -> b) -> f a -> f b

And therefore, if you squit hard enough, the category is f. So (for the Haskell implementation) what is the functor? It's fmap fn where fn is that function:

fn :: (a -> b)
-- and
fmap fn :: Functor => f a -> f b

And this fmap fn obeys the laws that we discussed above. So what are fmap and fn? Well, fn is whatever mapping that you want the particular functor to do. It operates on the thing (conceptually) inside the category. i.e. the objects that inhabit the category. Or more concretely, in Haskell, the values inside the type that has a Functor instance. And the fmap is the implementation function that 'knows' how to get at the values inside the type; so fmap is a different, concrete, function for each Functor instance. Which is why we have to define an fmap for each type!

Some examples

These are the really easy, and frequently quoted, examples, but they should serve to embed the concept; the Maybe and [] (list) types. First the Maybe type:

Recall that:

data Maybe a = Just a | Nothing

i.e. the Maybe type is either a Just <something> or a Nothing.

instance Functor Maybe where
    fmap fn (Just x) = Just (fn x)
    fmap _ Nothing = Nothing

Thus, above fn is the mapping function, so basically this is saying fmap applies fn to the x inside the Maybe if it is a Just x, or preserves the Nothing if the Maybe is a Nothing. Let's apply doubling to a Maybe value:

(*2) :: Num a => a -> a
fmap (*2) :: Functor f => f a -> f a

-- therefore
fmap (*2) (Just 1)
=> Just 2

What about lists?

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

Basically, the same pattern exists, the fn function is applied to the things inside the structure. And this is a pattern that repeats, across all the of the types that are instances of the Functor type class. Crucially, an important fact arises:

The structure of the type remains unchanged; the morphisms only occur to the objects inside the structure.

And this is an important aspect of the Functor and fmap the morphism (change) is applied to the 'contents'.

Comments are disabled for this page.