Equal class misunderstanding

Question

• I have my own data type to represent nodes and edges of a graph as follows:

  data Node a = Node a deriving (Show, Eq)
  
  data Label a = Label a deriving (Show)
  
  data Cost = CostI Int | CostF Float deriving (Show)
  
  data Edge label node = Edge (Label label, (Node node,Node node), Cost) deriving (Show)
  

• Now, I create a function to check whether an edge contains 2 nodes or not as follows:

  isEdge:: (Eq n) => (Edge l n) -> (Node n, Node n) -> Bool
  isEdge (Edge (_, (n1,n2), _)) (n3, n4) = result
       where result = (n1 == n3) && (n2 == n4)
  

• The function works well, the problem here is if I remove (Eq n) from the function, it fails. So, why is that, even though in the declaration above I declared Node as deriving from Eq class?

  data Node a = Node a deriving (Show, Eq)
  

Answer 1

The Eq instance GHC derives for Node a is something like this:

instance Eq a => Eq (Node a) where
    (Node x) == (Node y) = x == y
    (Node x) /= (Node y) = x /= y

You can view the generated code by compiling with -ddump-deriv. The Eq a constraint is needed for obvious reasons. So, GHC couldn't infer an instance of Eq for, say, Node (a -> b) since functions can't be compared.

However, the fact that GHC can't infer an instance of Eq for Node a for some a doesn't mean it will stop you from constructing a values of type Node a where a isn't an equality type.

---

If you wanted to stop people from constructing non-comparable Nodes, you could try putting a constraint like this:

data Eq a => Node a = Node a deriving (Eq, Show)

But now GHC tells us we need a compiler pragma:

Illegal datatype context (use -XDatatypeContexts): Eq a =>

OK, let's add it to the top of our file:

{-# LANGUAGE DatatypeContexts #-}

Now compile:

/tmp/foo.hs:1:41: Warning: -XDatatypeContexts is deprecated: It was widely
considered a misfeature, and has been removed from the Haskell language.

The problem is that now every function using Nodes will need an Eq class constraint, which is annoying (your functions still need the constraint!). (Also, if your user wants to create Nodes using a non-equality type but never tests them for equality, what's the problem?)

---

There's actually a way to get GHC to do what you want, however: Generalized Algebraic Data Types (GADTs):

{-# LANGUAGE GADTs, StandaloneDeriving #-}

data Node a where
  Node :: Eq a => a -> Node a

This looks just like your original definition, except that it emphasizes the Node value constructor (the one formerly on the right hand side of the data declaration) is just a function, which you can add constraints to. Now GHC knows that only equality types can be put into Nodes, and unlike our earlier attempted solution, we can make new functions that don't need a constraint:

fromNode :: Node a -> a
fromNode (Node x) = x

We can still derive Eq and Show instances, but with a slightly different syntax:

deriving instance Eq   (Node a)
deriving instance Show (Node a)

(Hence the StandaloneDeriving pragma above.)

For this to work, GHC also requires us to add a Show constraint to our GADT (if you look at the generated code again, you'll see the constraints are now gone):

data Node a where
  Node :: (Eq a, Show a) => a -> Node a

And now we can take the Eq constraint off isEdge, since GHC can infer it!

(This is definitely overkill for such a simple situation -- again, if people want to construct nodes with functions inside them, why shouldn't they? However, GADTs are extremely useful in pretty similar situations when you want to enforce certain properties of your data types. See a cool example).

---

EDIT (from the future): you can also write

data Node a = (Eq a, Show a) => Node a

but you still need to enable GADT extensions and derive instances separately. See this thread.

Answer 2

When you add a deriving clause to a data declaration, the derived clause will include any necessary constraints for the type variable in scope at the declaration. In this case, deriving Eq will create essentially the following instance:

instance Eq a => Eq (Node a) where
    (Node a) == (Node b) = a == b
    (Node a) /= (Node b) = a /= b

Any derived Eq instance will depend upon the Eq instance of types that appear to the right of the data constructor.

This is because there's really no other way to derive an Eq instance automatically. Two values are equal if they have the same type and all their components are equal. So you need to be able to test the components for equality. In order to generically test a polymorphic component for equality, you need an Eq instance.

This is true not just for Eq, but for all the derived classes. For example this code

toStr :: Edge l n -> String
toStr = show

won't work without adding the constraint (Show l, Show n). Without that constraint, the function to show an Edge doesn't know what to call to show its internal Labels and Nodes.