# 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].