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
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
- otherwise, leave the argument alone
Records are somewhat special in PureScript, so we decided to add a special case for them.
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:
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
Traversable (ticket here). Perhaps I will work on those some time soon if someone else doesn’t beat me to it :)