# PureScript: Deriving Functor

For the 0.10.4 release, I worked on `Functor`

deriving. This allows you to write a data type and derive a `Functor`

instance for it. This obviously doesn’t work for all data types, but also doesn’t necessarily work for all data types that could have a valid `Functor`

instance written for them. In this post I will demonstrate examples of the kinds of structures it works for, and those it doesn’t.

Recall the definition of the `Functor`

type class:

Given a data type `F :: * -> *`

, to derive the `Functor`

instance, we would write a derived instance such as:

If the compiler is able to compute the implementation of `map`

for the particular `F`

data type, then it will do so; otherwise you will get a bad type error. We have a ticket to improve the error message here.

The following is a collection of example data types for which this deriving mechanism should work for. Each with a short comment describing the particular arrangement of types that is being demonstrated.

Note that the last example also requires a `Functor`

instance on the index `f`

. If we omitted this, we would end up with the type error similar to:

```
No type class instance was found for
Data.Functor.Functor f
```

# Algorithm

Implementing the `map`

function is rather straight-forward. For each argument in each constructor:

- if the argument is the type index, then apply the mapping function
- if the argument is a record, then recurse on each field
- if the argument is a type application, recurse on the argument and wrap the function in a call to
`map`

- otherwise, leave the argument alone

Records are somewhat *special* in PureScript, so we decided to add a special case for them.

# Limitations

Given this algorithm, we can see some obvious limitations: we only recurse on the last argument in a type application - so we may miss the uses of the index in other argument positions.

We also only ever assume a `Functor`

instance for a data type with the argument in the last index. If we have some contravariant data type `C :: * -> *`

and a data type `data F x = F (C (C x))`

, with this algorithm we are unable to derive a `Functor F`

instance, even though a valid one exists via `cmap <<< cmap`

.

Each of these limitations could potentially be overcome by a more interesting algorithm with access to more information about the types involved: such as index variance tracking. With variance tracking we could compute which sort of mapping to apply: `map`

, `cmap`

, `bimap`

, `dimap`

, etc.

# Conclusion

Aside from those limitations, with such a simple algorithm we gained a useful and widely applicable code generating tool. As a next step, and following a similar algorithm, we would like to derive `Foldable`

and `Traversable`

(ticket here). Perhaps I will work on those some time soon if someone else doesn’t beat me to it :)