Kevin Meredith
Kevin Meredith

Reputation: 41909

Define Equality Instance for Free Monad

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?

Upvotes: 4

Views: 328

Answers (2)

dfeuer
dfeuer

Reputation: 48581

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.

Upvotes: 2

duplode
duplode

Reputation: 34378

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.

Upvotes: 11

Related Questions