How to derive instances in recursion schemes

Question

I am testing out some of the ideas in this article.

I want to derive an instance of Eq for the 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 adding a standalone deriving instance:

{-# 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 do I show that f has a kind * -> *? And why do I need a standalone deriving instance for Term but not Tree? Both have type variables that are not necessarily going to be instances of Eq? (a and f)

Possible typo: the definition of Term, does not refer to Tree in any way. — cody
Try writing the instance manually and I think you will understand the problem. — Reid Barton

phadej phadej · Accepted Answer · 2016-08-15T17:16:24

There are two solutions:

Using some GHC extensions StandaloneDeriving, UndecidableInstances and some others you can write:

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

This is what recursion-schemes does at the moment

--

Alternatively, you can use Eq1 from transformers or 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

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

How to derive instances in recursion schemes

1 Answers