# How do I give a Functor instance to a datatype built for general recursion schemes?

I have a recursive datatype which has a Functor instance:

``````data Expr1 a
= Val1 a
| Add1 (Expr1 a) (Expr1 a)
deriving (Eq, Show, Functor)
``````

Now, I'm interested in modifying this datatype to support general recursion schemes, as they are described in this tutorial and this Hackage package. I managed to get the catamorphism to work:

``````newtype Fix f = Fix {unFix :: f (Fix f)}

data ExprF a r
= Val a
deriving (Eq, Show, Functor)

type Expr2 a = Fix (ExprF a)

cata :: Functor f => (f a -> a) -> Fix f -> a
cata f = f . fmap (cata f) . unFix

eval :: Expr2 Int -> Int
eval = cata \$ \case
Val n -> n
Add x y -> x + y

main :: IO ()
main =
print \$ eval
(Fix (Add (Fix (Val 1)) (Fix (Val 2))))
``````

But now I can't figure out how to give `Expr2` the same functor instance that the original `Expr` had. It seems there is a kind mismatch when trying to define the functor instance:

``````instance Functor (Fix (ExprF a)) where
fmap = undefined
``````
``````Kind mis-match
The first argument of `Functor' should have kind `* -> *',
but `Fix (ExprF a)' has kind `*'
In the instance declaration for `Functor (Fix (ExprF a))'
``````

How do I write a Functor instance for `Expr2`?

I thought about wrapping Expr2 in a newtype with `newtype Expr2 a = Expr2 (Fix (ExprF a))` but then this newtype needs to be unwrapped to be passed to `cata`, which I don't like very much. I also don't know if it would be possible to automatically derive the `Expr2` functor instance like I did with `Expr1`.

Solution

• I wonder if you might be better off using the `Free` type:

``````data Free f a
= Pure a
| Wrap (f (Free f a))
deriving Functor

data ExprF r
deriving Functor
``````

This has the added benefit that there are quite a few libraries that work on free monads already, so maybe they'll save you some work.