How to get instances in recursion schemes

Question

I am testing some ideas in this article .

I want to get an Eq instance for type Term:

{-# LANGUAGE DeriveFunctor #-}
data Tree a = Branch Int [a] | Leaf Int deriving (Eq, Functor, Show)
data Term f = Term (f (Term f)) deriving (Eq)

But get this error:

No instance for (Eq (f (Term f)))
      arising from the first field of ‘Term’ (type ‘f (Term f)’)
    Possible fix:
      use a standalone 'deriving instance' declaration,
        so you can specify the instance context yourself
    When deriving the instance for (Eq (Term f))

I tried to add a separate output:

{-# LANGUAGE DeriveFunctor #-}
{-# LANGUAGE StandaloneDeriving #-}
data Tree a = Branch Int [a] | Leaf Int deriving (Eq, Functor, Show)
data Term f = Term (f (Term f))
deriving instance (Eq f) => Eq (Term f)

But get this error:

The first argument of ‘Term’ should have kind ‘* -> *’,
  but ‘f’ has kind ‘*’
In the stand-alone deriving instance for ‘(Eq f) => Eq (Term f)’

Now i'm stuck. How to show that f has the form * -> *? And why do I need a separate conclusion for Term, but not Tree? Do both have type variables that will not necessarily be instances of Eq? ( aand f)

Answer 1

There are two solutions:

Using some GHC extensions StandaloneDeriving, UndecidableInstancesand some others you can write:

deriving instance (Eq (f (Term f))) => Eq (Term f)

This is what it is recursion-schemesdoing at the moment.

-

Eq1 transformers base-4.9.0.0

class Eq1 f where
    liftEq :: (a -> b -> Bool) -> f a -> f b -> Bool

eq1 :: (Eq1 f, Eq a) -> f a -> f a -> Bool
eq1 = liftEq (==)

instance Eq1 f => Eq (Term f) where
    Term a == Term b = eq1 a b

: https://github.com/ekmett/recursion-schemes/blob/ffada24f92efd5bcfe71f7f0af3b4af057f50bd0/Data/Functor/Foldable.hs#L392