Samuel Evans-Powell

Functor

I've been learning about Haskell and Category Theory lately. In this series of posts I hope to collect my thoughts. Please pop me an email or open a pull request here if you want to make any suggestions/corrections, I'm still learning myself.

A data type that is an instance of Functor allows you to apply some function to values within the context of that Functor (a list of Integers can be thought of as Integer values within the context of a list). You're probably familiar with at least one instance of Functor: the List type in Haskell. The List type allows functions to be applied to values in the list using the map function:

map :: (a -> b) -> [a] -> [b]

In Haskell, for a type to be a Functor instance, it must implement the fmap function:

Note that fmap is just a generalization of the map function, with the list being replaced by the type parameter f.

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

That's it! Just one function.

The fmap function can be thought of as 'mapping' values of the type 'a' in the given functor (the domain) to values of the type 'b' in the same functor (codomain), where the given function (a -> b) performs that 'mapping'.

A simple Functor instance for Lists might look like this:

instance Functor (List) where
  fmap :: (a -> b) -> [a] -> [b]
  fmap _ []     = []
  fmap f (x:xs) = f x : fmap xs

The supplied function is simply applied to each element in the list.

The Haskell Maybe type is also an instance of Functor:

instance Functor (Maybe) where
  fmap :: (a -> b) -> Maybe a -> Maybe b
  fmap _ Nothing  = Nothing
  fmap f (Just a) = Just (f a)

Again, pretty simple: if the given Maybe has the value 'Nothing', return 'Nothing', otherwise apply the function to the value present.

Alright, how about something a bit more challenging:

instance Functor ((->) e) where

The function type constructor can be an instance of Functor too!

Yes, this can be very hard to wrap your head around. If you get lost here, don't worry! Come back to it later.

Kinds

Let's start with an aside on kinds:

Just as types are used to classify values, kinds are used to classify types.

The kind of Bool is '∗':

:k Bool 
Bool :: *

The kind of Integer is '∗':

:k Integer
Integer :: *

:k [Integer]
[Integer] :: *

If something can be used as a value, it's type will have the kind '∗'.

:t True
True :: Bool

:k Bool
Bool :: *

True is a value whose type (Bool) has the kind '∗'.

Type constructors on the other hand have the kind '(∗ -> ∗)':

:k []
[] :: * -> *

:k Maybe
Maybe :: * -> *

They take something of kind '∗' (Such as Integer, [Integer], Bool, Maybe Integer, etc.) and produce something of kind '∗'. That is, it takes a value type and produces a new value type.

The Maybe type takes any type of kind '∗' and produces a value of a type whose kind is '∗':

:k Maybe
Maybe :: * -> *

:k Int
Int :: *

:k Maybe Int
Maybe Int :: *

The function type constructor takes two things of kind '∗' and produces something of kind '∗':

:k (->)
(->) :: * -> * -> *

:k ((->) Integer)
((->) Integer) :: * -> *

:k ((->) Integer Bool)
((->) Integer Bool) :: *

-- Rewritten with (->) infix:
:k (Integer -> Bool)
(Integer -> Bool) :: *

Oh look, functions have the same kind as any other values!

Now, let's look at the kind of Functor.

$ :k Functor
Functor :: (* -> *) -> Constraint

We can see that Functor takes something of kind '(∗ -> ∗)' (i.e. a type constructor) and produces a Constraint. We won't look at constraints now, but the name should give you a sufficient idea of what they do.

It makes sense that we can create a Functor instance of Maybe because the kind of Maybe matches:

:k Maybe
Maybe :: * -> *

instance Functor Maybe where
-- ...

But, notice that the kind of ((->) e) (where e is any type) also matches:

:k ((->) Integer)
((->) Integer) :: * -> *

Therefore, we can make Functor instances of ((->) e), i.e. the function type constructor with one argument applied.

To make such an instance, we need an implementation of the fmap function:

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

Let's substitute f for our function type constructor, ((->) e):

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

And writing (->) infix:

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

Now that we have the type, let's try our hand at writing it (just match the types!):

fmap :: (a -> b) -> (e -> a) -> (e -> b)
fmap f g = f . g

(Convince yourself that this works). Hmm, this is just function composition and so can be re-written pointfree as:

instance Functor ((->) e) where
  fmap :: (a -> b) -> (e -> a) -> (e -> b)
  fmap = (.)

Phew, our Functor instance for the function type constructor. Essentially this allows us to apply a function to the resulting value of another function (function composition).

I hope this also demonstrates the power of 'following the types' of functions (and kinds of types) when trying to understand functional programs. Do this often!

References

B. Yorgey, "Functors", http://www.seas.upenn.edu/~cis194/spring13/lectures/09-functors.html, 2013. [Online]. Available: http://www.seas.upenn.edu/~cis194/spring13/lectures/09-functors.html. [Accessed: 01- Feb- 2018].