CODEWITHSUNDEEP
haskell
bwroga
bwroga

Reputation: 5449

How to derive instances in recursion schemes

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)

Upvotes: 6

Views: 558

Answers (2)

Carl
Carl

Reputation: 1019

I'll answer this part of the question:

And why do I need a standalone deriving instance for Term but not Tree?

With attached deriving, GHC attempts to infer the context of the generated instance, i.e. determine what to put before the => in the instance head in a way that makes the generated instance legal. From @phadejs answer it is clear that one such legal context is Eq (f (Term f)) => ... We can see that from the fact that this manually-declared instance type-checks:

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

The error message you get, "No instance for (Eq (f (Term f)))", implies that GHC has not used such a context for the instance it attempted to generate.

On the other hand, for the Eq (Tree a) instance, GHC has obviously managed to infer and use the context Eq a => .., since that instance is properly generated by the attached deriving clause.

GHCs ability to infer contexts is documented in 6.6.2. Inferred context for deriving clauses of the GHC User Guide. One of the paragraphs read (emphasis mine):

GHC takes a conservative position [...]. The rule is this: each constraint in the inferred instance context must consist only of type variables, with no repetitions.

For Tree a, the required context Eq a => .. has the single constraint Eq a. This constraint meets the rule, and hence the context is properly inferred by GHC in this case.

For Term f however, the required context consists of the constraint Eq (f (Term f)). This constraint does not meet the rule since f is repeated, and hence GHC fails to infer the context for this instance.

Upvotes: 1

phadej
phadej

Reputation: 12123

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

Upvotes: 9

Related Questions