Deriving functor instance, not on last type argument

Question

Related to this question I asked earlier today.

I have an AST data type with a large number of cases, which is parameterized by an "annotation" type

data Expr ann def var = Plus a Int Int
    | ...
    | Times a Int Int
    deriving (Data, Typeable, Functor)

I've got concrete instances for def and var, say Def and Var.

What I want is to automatically derive fmap which operates as a functor on the first argument. I want to derive a function that looks like this:

fmap :: (a -> b) -> (Expr a Def Var) -> (Expr b Def Var)

When I use normal fmap, I get a compiler message that indicates fmap is trying to apply its function to the last type argument, not the first.

Is there a way I can derive the function as described, without writing a bunch of boilerplate? I tried doing this:

newtype Expr' a = E (Expr a Def Var)
    deriving (Data, Typeable, Functor)

But I get the following error:

  Constructor `E' must use the type variable only as the last argument of a data type

I'm working with someone else's code base, so it would be ideal if I don't have to switch the order of the type arguments everywhere.

Answer 1

The short answer is, this isn't possible, because Functor requires that the changing type variable be in the last position. Only type constructors of kind * -> * can have Functor instances, and your Expr doesn't have that kind.

Do you really need a Functor instance? If you just want to avoid the boilerplate of writing an fmap-like function, something like SYB is a better solution (but really the boilerplate isn't that bad, and you'd only write it once).

If you need Functor for some other reason (perhaps you want to use this data structure in some function with a Functor constraint), you'll have to choose whether you want the instance or the type variables in the current order.

Answer 2

You can exploit a type synonym for minimizing the changes to the original code:

data Expr' def var ann = Plus a Int Int   -- change this to Expr', correct order
    | ...
    | Something (Expr ann def var)        -- leave this as it is, with the original order
    deriving (Data, Typeable, Functor)

type Expr ann def var = Expr' def var ann

The rest of the code can continue using Expr, unchanged. The only exceptions are class instances such as Functor, which as you noticed require a certain order in the parameters. Hopefully Functor is the only such class you need.

The auto-derived fmap function has type

fmap :: (a -> b) -> Expr' def var a -> Expr' def var b

which can be written as

fmap :: (a -> b) -> Expr a def var -> Expr b def var