title: How do I give a Functor instance to a datatype built for general recursion schemes?
body: <p>I have a recursive datatype which has a Functor instance:</p>
  
  <pre><code>data Expr1 a
    = Val1 a
    | Add1 (Expr1 a) (Expr1 a)
    deriving (Eq, Show, Functor)
  </code></pre>
  
  <p>Now, I'm interested in modifying this datatype to support general recursion schemes, as they are described in <a href="https://www.fpcomplete.com/user/bartosz/understanding-algebras" rel="nofollow noreferrer">this tutorial</a> and <a href="http://hackage.haskell.org/package/data-fix" rel="nofollow noreferrer">this Hackage package</a>. I managed to get the catamorphism to work:</p>
  
  <pre><code>newtype Fix f = Fix {unFix :: f (Fix f)}
  
  data ExprF a r
    = Val a
    | Add r r
    deriving (Eq, Show, Functor)
  
  type Expr2 a = Fix (ExprF a)
  
  cata :: Functor f =&gt; (f a -&gt; a) -&gt; Fix f -&gt; a
  cata f = f . fmap (cata f) . unFix
  
  eval :: Expr2 Int -&gt; Int
  eval = cata $ \case
    Val n -&gt; n
    Add x y -&gt; x + y
  
  main :: IO ()
  main =
    print $ eval
      (Fix (Add (Fix (Val 1)) (Fix (Val 2))))
  </code></pre>
  
  <p>But now I can't figure out how to give <code>Expr2</code> the same functor instance that the original <code>Expr</code> had. It seems there is a kind mismatch when trying to define the functor instance:</p>
  
  <pre><code>instance Functor (Fix (ExprF a)) where
      fmap = undefined
  </code></pre>
  
  <pre class="lang-none prettyprint-override"><code>Kind mis-match
      The first argument of `Functor' should have kind `* -&gt; *',
      but `Fix (ExprF a)' has kind `*'
      In the instance declaration for `Functor (Fix (ExprF a))'
  </code></pre>
  
  <p><strong>How do I write a Functor instance for <code>Expr2</code>?</strong></p>
  
  <p>I thought about wrapping Expr2 in a newtype with <code>newtype Expr2 a = Expr2 (Fix (ExprF a))</code> but then this newtype needs to be unwrapped to be passed to <code>cata</code>, which I don't like very much. I also don't know if it would be possible to automatically derive the <code>Expr2</code> functor instance like I did with <code>Expr1</code>.</p>