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?

score 11 · Accepted Answer · answered Sep 20 '15 at 03:34

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.

Now I'm seeing: `Variable ‘f’ occurs more often than in the instance head in the constraint: Eq (f (Free f a)). (Use UndecidableInstances to permit this)`. OK to add that too? — Kevin Meredith, Sep 21 '15 at 02:43
@KevinMeredith It is OK too. The worst thing that might happen with UndecidableInstances is compilation failing if you e.g. lead the type checker to an infinite loop, but that won't happen here. The main nasty extensions that you generally should not turn on even when GHC suggests them are [OverlappingInstances](http://stackoverflow.com/q/1064232) and [IncoherentInstances](http://stackoverflow.com/q/16050566) -- those two open the doors to nonsense. You did the right thing by asking, BTW: most extensions are harmless, but you should know what they do and whether you need them before enabling. — duplode, Sep 21 '15 at 03:16

dfeuer · Answer 2 · 2015-09-20T16:01:16.550

2

duplode shows how to do it with flexible contexts. If you want Haskell 2010, the usual approach is to use the Eq1 class from Prelude.Extras or similar.

class Eq1 f where
  (==#) :: Eq a => f a -> f a -> Bool

Then you'd use

instance (Eq1 f, Eq a) => Eq (Free f a) where ...
instance Eq1 f => Eq1 (Free f) -- default instance is fine.

I'm not at my computer right now, so I can't test this until later.

edited Sep 20 '15 at 16:01

answered Sep 20 '15 at 14:29

dfeuer

48,079
5
63
167

Define Equality Instance for Free Monad

2 Answers2