# Deriving Functor

```Hello,

```
I would like to propose to add a way to automatically derive instances of Functor. From looking at existing code, it seems that almost all Functor instances I see are derivable using the algorithm presented here, resulting in less boilerplate code. This proposal is compatible with Haskell98 (and therefore also with Haskell').
```
Let's start with an example. The following declaration:

> data Tree a = Leaf | Node (Tree a) a (Tree a)
>      deriving Functor

would generate the following Functor instance:

> instance Functor Tree where
>      fmap f (Leaf      ) = Leaf
>      fmap f (Node l a r) = Node (fmap f l) (f a) (fmap f r)

```
To be able to derive Functor in a general way, more classes are needed to support functors over other parameters:
```> class Functor2 f where  fmap2  :: (a -> b) -> f a x   -> f b x
> class Functor3 f where  fmap3  :: (a -> b) -> f a x y -> f b x y
> -- etc.
Provided instances would be:
> instance Functor  ((,) a)  -- currently in Control.Monad.Instances
> instance Functor2  (,)
> instance Functor  ((,,) a b)
> instance Functor2 ((,,) a)
> instance Functor3  (,,)
> instance Functor  ((,,,) a b c)
> instance Functor2 ((,,,) a b)
> instance Functor3 ((,,,) a)
> instance Functor4  (,,,)
> -- etc.

Also, a contravariant functors can come up:
> class CoFunctor  f where  cofmap  :: (a -> b) -> f b   -> f a
> class CoFunctor2 f where  cofmap2 :: (a -> b) -> f b x -> f a x
> -- etc.

Now, to derive functor for a data type
> data D a = C1 u v w | C2 x y z | ...
The instance would be:
> instance Functor D where
>    fmap f d = case d of
>      C1 q r s -> C1 (fmap_<a,u> f q) (fmap_<a,v> f r) (fmap_<a,w> f s)
>      C2 t u v -> C1 (fmap_<a,x> f t) (fmap_<a,y> f u) (fmap_<a,z> f v)
>      ...
```
With the appropriate context. Here fmap_<a,b> is the deriving scheme to derive a functor over type b, parameterized by the type variable a:
```> fmap_<a, a>      f = f
> fmap_<a, b>      f = id -- b does not contain a
> fmap_<a, T x>    f = fmap  (fmap_<a,x> f)
> fmap_<a, T x y>  f = fmap2 (fmap_<a,x> f) . fmap (fmap_<a,y> f)
>   --etc.
> fmap_<a, x -> y> f = \u -> fmap_<a, y> f . u . cofmap_<a, x> f
>
> cofmap_<a, b>      f = id -- b does not contain a
> cofmap_<a, T x>    f = cofmap  (fmap_<a,x> f)
> cofmap_<a, T x y>  f = cofmap2 (fmap_<a,x> f) . cofmap (fmap_<a,y> f)
>   --etc.
> cofmap_<a, x -> y> f = \u -> cofmap_<a, y> f . u . fmap_<a, x> f

```
Before type checking to determine the required instances, the transformations
```   fmapN   id  --> id
cofmapN id  --> id
```
must be applied. Otherwise unnecessary instances will be required, see the State example below.
```

```
Here are some examples of the deriving scheme. The derived instances are exactly as you would expect:
```
> data Tree a = Leaf | Node (Tree a) a (Tree a)

The instance is derived as:
> fmap f d = case d of
>       Leaf       -> Leaf
>       Node a b c -> Node (fmap_<a,Tree a> f   a) (fmap_<a,a> f b)
>                          (fmap_<a,Tree a> f   c)
>                   = Node (fmap (fmap_<a,a> f) a) (f            b)
>                          (fmap (fmap_<a,a> f) c)
>                   = Node (fmap f a) (f b) (fmap f c)

It also works for things like monad transformers:

> newtype StateT s m a = StateT (s -> m (a, s))

> fmap f (StateT a) = StateT b
>  where b = fmap_<a, s -> m (a, s)> f a
>          = fmap_<a, m (a, s)> f . a . cofmap_<a, s> f
>          = fmap_<a, m (a, s)> f . a . id
>          = fmap (fmap_<a, (a, s)> f) . a
>          = fmap (fmap2 (fmap_<a, a> f) . fmap (fmap_<a, s> f)) . a
>          = fmap (fmap2 f . fmap id) . a
>          = fmap (fmap2 f) . a
>          = \s -> fmap (\(a,s) -> (f a, s)) (a s)

Even for Cont:

> newtype Cont r a = ContT ((a -> r) -> r)

> fmap f (ContT a) = ContT b
>  where b = fmap_<a, (a -> r) -> r> f a
>          = fmap_<a, r> f . a . cofmap_<a, a -> r> f
>          = id . a . cofmap_<a, a -> r> f
>          = a . (\u -> cofmap_<a, r> f . u . fmap_<a,a> f)
>          = a . (\u -> id . u . f)
>          = a . (. f)

```
There are some (minor) problems with this approach. First of all the treatment of (->) is rather ad-hoc, consider:
```
> newtype Arrow a b = a -> b    deriving (Functor, CoFunctor2)
> data A a = A (T a -> ())      deriving Functor
> data B a = B (Arrow (T a) ()) deriving Functor

In the first case the derived instance is:
> instance CoFunctor T => Functor A where
>     fmap f (A u) = A (u . cofmap f)
While for the second type the following is derived:
> instance (Functor T, Functor2 Arrow) => Functor B where
>     fmap f (B u) = fmap2 (fmap f)

Consider also:

> newtype Problem a = Problem (T (U a)) deriving Functor

```
Now there are two possible functor instances, depending on the instances for T and U:
```
> instance Functor Problem  where  fmap f = fmap (fmap f)
> instance Functor Problem  where  fmap f = cofmap (cofmap f)

```
Currently the algorithm chooses the former, it will only use CoFunctor if (->) is present, and it tries to get rid of it as soon as possible. This also comes up when trying to derive an instance for this variation of Cont:
```
> data C r a = C ((a -> r, a -> r) -> r) deriving Functor

```
Because it uses a type constructor in a contravariant position. The derivation goes as follows:
```
> fmap f (C a) = C b
>  where b = fmap_<a, (a -> r, a -> r) -> r>
>          = fmap_<a, r> f . a . cofmap_<a, (a -> r, a -> r)> f
>          = id . a . cofmap_<a, (a -> r, a -> r)> f
>          = a . cofmap2 (fmap_<a, a->r> f) . cofmap (fmap_<a, a->r> f)
>          = a . cofmap2 (fmap_<a, a->r> f)
>              . cofmap (\u -> cofmap_<a, a> f . u . fmap_<a,r> f)
>          = error, unable to realize: cofmap_<a,a>

The desired instance would be:
>      ... = a . cofmap_<a, (a -> r, a -> r)> f
>          = a . fmap2 (cofmap_<a, a -> r> f)
>              . fmap (cofmap_<a, a -> r> f)
>          = a . fmap2 (cofmap_<a, a -> r> f)
>              . fmap (\u -> cofmap_<a,r> f . u . fmap_<a, a> f)
>          = a . fmap2 (cofmap_<a, a -> r> f) . fmap (.f)
>          = a . fmap2 (.f) . fmap (.f)
>          = \(x,y) -> a . (x . f, y . f)

```
However, I highly doubt this problem will come up in practice. A 'solution' would be to replace:
```> cofmap_<a, T x y>  f = cofmap2 (fmap_<a,x> f) . cofmap (fmap_<a,y> f)
with
> cofmap_<a, T x y>  f = fmap2 (cofmap_<a,x> f) . fmap (cofmap_<a,y> f)
```
Thereby removing all uses of CoFunctor. Maybe that would be a better definition?
```

```
Finally, if Data.Foldable and Data.Traversable are added to the standard, they could be derived in a similair way.
```

Twan van Laarhoven
_______________________________________________