Overriding (==) in Haskell

Question

I have the following algebraic data types:

data Exp
  = Con Int
  | Var String
  | Op Opkind Exp Exp
  | Input
  deriving (Show,Eq)

data Opkind
  = Plus | Minus | Mult | Div | More | Equal
  deriving (Show,Eq)

That represent expressions in a simple toy language.

However, because I derive Eq, Op Plus (Var "a") (Var "b) is not considered equal to Op Plus (Var "b") (Var "a") even though I would like to treat a+b as an equal expression to b+a.

How do I change (==) for just those instances, without having to specify the behaviour of (==) for all the other instances?

Answer 1

You can achieve this by making Exp an instance of Eq instead of deriving Eq:

instance Eq Exp where
    (Con a) == (Con b) = a == b
    (Var a) == (Var b) = a == b
    (Op Plus a b) == (Op Plus c d) = (a == c && b == d) || (a == d && c == b)
    Input == Input = True
    _ == _ = False

This would compare Op Plus in the way wanted, but is still missing the other cases for Op.

Edit:

The easiest way to implement special cases for (==) on Op without losing the derive on Exp, that comes to my mind would be something like this:

data Exp
  = Con Int
  | Var String
  | EOp Op
  | Input
  deriving (Show, Eq)

data Op = Op Opkind Exp Exp deriving (Show)
instance Eq Op where
    (Op Plus e1 e2) == (Op Plus e3 e4) = (e1 == e3 && e2 == e4) || ( e1 == e4 && e2 == e3)
    (Op kind1 e1 e2) == (Op kind2 e3 e4) = and [kind1 == kind2, e1 == e3, e2 == e4]

Answer 2

If you want custom behavior for Op, but regular behavior for all other variants of your datatype, you'll need to break out Op into its own type.

For example:

data Exp
  = Con Int
  | Var String
  | Input
  | PrimOp Op
  deriving (Show,Eq)

data Op = Op Opkind Exp Exp
  deriving Show

data Opkind
  = Plus | Minus | Mult | Div | More | Equal
  deriving (Show,Eq) 

-- equality on (symbolic) functions, perhaps?
instance Eq Op where
  (Op a _ _) == (Op b _ _) = a == b

Let's you define all expressions structurally equal, except for applications of functions to arguments, which are equal by name only (which may or may not be useful).