# Notes (CTFP 07/31): Functors

# 7 Functor

**functor**: A functor is a mapping between categories.

```
f :: a -> b
F f :: F a -> F b
F :: (a -> b) -> (F a -> F b)
```

Compositions of functions in the base category map to the composition of the image of those functions:

```
= g . f
h F h = F g . F f
```

An object’s identity morphisms map to the identity morphisms of its image:

`F (id :: A -> A) = id :: F A -> F A`

**endofunctor**: A functor that maps a category to itself.

## 7.1 Functors in Programming

### 7.1.1 The Maybe Functor

`data Maybe a = Nothing | Just a`

`fmap`

lifts a function onto the functorial target category. For `Maybe`

:

`fmap :: (a -> b) -> (Maybe a -> Maybe b)`

In general:

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

The functor maps both objects and categories, but the objects are types not values, so we need

`F :: * -> *`

which is `Maybe.`

See this Stack Overflow question for more detail.

### 7.1.2 Equational Reasoning

Equational reasoning is possible with pure functions, because the equality is not hiding state mutation. Thus, reasoning about code in functional programming language like Haskell becomes more explicitly mathematical.

### 7.1.3 Optional

Skipping `C++`

content. Perhaps I will come back and do this with `Rust`

### 7.1.4 Typeclasses

Suppose `Maybe`

is a Functor. `Maybe`

is a type constructor. This means `Maybe`

itself is the mapping from objects to objects (`* -> *`

) e.g. `Int -> Maybe Int.`

But to be a functor, `Maybe`

needs a mapping from morphisms to morphisms. This is `fmap`

, which is declared in Haskell in the Functor class:

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

To say that `Maybe`

is an instance of this class, we have to give the implementation of `fmap`

:

```
instance Functor Maybe where
fmap f Nothing = Nothing
fmap f (Just a) = Just (f a)
```

### 7.1.5 Functor in C++

Skipping `C++`

.

### 7.1.6 The List Functor

`data List a = Nil | Cons a (List a)`

An `fmap`

for `List`

has to have the type:

`fmap :: (a -> b) -> (List a -> List b)`

If we have a `List`

of `a`

’s and a function that transforms `a`

’s into `b`

’s, what’s the most natural way to get a `List`

of `b`

’s? To apply the transformation to each `a`

in the list!

```
instance Functor List where
fmap _ Nil = Nil
fmap f (Cons x t) = Cons (f x) (fmap f t)
```

### 7.1.7 The Reader Functor

In Haskell, a function type is constructed using the arrow type constructor:

`->) a b (`

Because `(->)`

is a type constructor that takes two arguments, `(->) a`

is a type constructor, like `List`

or `Maybe`

.

Let’s give wrap type constructor `(->)`

in a newtype called `Reader`

:

```
{-# LANGUAGE InstanceSigs #-}
newtype Reader r a = Reader { run :: r -> a }
instance Functor (Reader r) where
fmap :: (a -> b) -> (Reader r a) -> (Reader r b)
fmap f reader = Reader $ f . (run reader)
```

We could also say:

`fmap f (Reader g) = Reader $ f . g`

## 7.2 Functors as Containers

The idea of a Functor as a container of some value or values is imperfect, since sometimes a Functor will explicitly contain no values, as in the case of the `Const`

functor:

```
{-# LANGUAGE InstanceSigs #-}
data Const c a = Const c
instance Functor (Const c) where
fmap :: (a -> b) -> Const c a -> Const c b
fmap _ (Const v) = (Const v)
```

A `Const c a`

is a box containing a type `c`

and a “phantom” type `a`

. The type `a`

doesn’t exist except in the type signature.

## 7.3 Functor Composition

Lets say we have a list of integers:

```
ints :: [Int]
= [0,1,2,3,4,5,6,7,8,9] ints
```

Now suppose we want to apply the function:

`isPrime :: Int -> Bool`

to this list. The specific implementation of `isPrime`

isn’t important, it just returns `True`

if the `Int`

is prime and `False`

if it is not prime.

But we have a problem here, in that prime numbers are only defined for integers greater than 1. `isPrime 3`

should return `True`

and `isPrime 4`

should return `False`

, but `isPrime 1`

is undefined and should return neither of those things.

Now, you might be saying, why don’t we just return `False`

for any integer where `isPrime`

is undefined? This does seem like the simplest solution from a programming perspective.

However, this solution could actually generate a lot of headache for us later on.

For example, let’s say we wanted to write another function `isComposite`

, that returns `True`

for integers with factors.

Mathematical intuition says that we should be able to do:

```
isComposite :: Int -> Bool
= not . isPrime isComposite
```

But if we defined `isPrime 1`

to be `False`

then `isComposite 1`

would return `True`

, which is wrong, because “composite” numbers are also only defined for numbers greater than 1.

Now, suppose we have some code (maybe from a library) where `isPrime`

and `isComposite`

do follow the rule that each is the logical inverse (the "not) of the other.

But let’s say that for whatever reason, the author decided to make `isPrime`

and `isComposite`

partial functions, meaning that for any integers outside their domain (less than or equal to 1) they return a runtime error.

Runtime errors, are annoying (and dangerous) so, let’s say we want to fix their code.

We could directly modify their code and write two new functions:

```
safeIsPrime :: Int -> Maybe Bool
safeIsComposite :: Int -> Maybe Bool
```

So that `isPrime 1`

return `Nothing`

and `isComposite 4`

returns `Just True`

.

Editing other peoples’ code is a lot of work though, and isn’t always the best solution. Is there a way we can turn make partial functions safe from the “outside”?

There is! We know that

```
safen :: Int -> Maybe Int
safen x| x > 1 = Just x
| otherwise = Nothing
```

safeIsPrime x= safen