Define Equality Instance for Free Monad

Question

Given the Free Monad:

data Free f a = Var a
               | Node (f (Free f a)) 

I tried to define an Eq instance for it:

instance (Functor f, Eq (f a)) => Eq (Free f a) where
    (==) (Var x) (Var y)       = x == y
    (==) (Node fu1) (Node fu2) = fu1 == fu2
    (==) _ _                   = False

But that fails to compile:

FreeMonad.hs:17:10:
    Non type-variable argument in the constraint: Eq (f a)
    (Use FlexibleContexts to permit this)
    In the context: (Functor f, Eq (f a))
    While checking an instance declaration
    In the instance declaration for ‘Eq (Free f a)’
Failed, modules loaded: none.

Specifying a constraint/pre-condition of (Functor f, Eq (f a)) seems odd to me (at least I don't think that I've seen it as a beginner before).

How can I define an Eq instance for Free f a?

Answer 1

There is nothing wrong with having a constraint like Eq (f a). As the error message says, you will need to enable the (harmless) FlexibleContexts GHC extension to do that, so add...

{-# LANGUAGE FlexibleContexts #-}

... to the top of your source file.

Do note, however, that (Functor f, Eq (f a)) doesn't really reflect what you are doing in your implementation of (==). Firstly, you don't need the supposition that f is a Functor here, so you can safely drop the Functor f constraint. Secondly, the constraints should match what you need to write the different cases. In the first case, you do x == y. x and y are both of type a, and so you need Eq a. For analogous reasons, the second case requires Eq (f (Free f a)) rather than Eq (f a). That means you will end up with...

(Eq (f (Free f a)), Eq a) => Eq (Free f a)

... which matches reference implementations such as the one in Control.Monad.Free.