Haskell: Matching two expressions that are not from class Eq

Question

First of all, I want to clarify that I've tried to find a solution to my problem googling but I didn't succeed.

I need a way to compare two expressions. The problem is that these expressions are not comparable. I'm coming from Erlang, where I can do :

case exp1 of 
     exp2 -> ...

where exp1 and exp2 are bound. But Haskell doesn't allow me to do this. However, in Haskell I could compare using ==. Unfortunately, their type is not member of the class Eq. Of course, both expressions are unknown until runtime, so I can't write a static pattern in the source code.

How could compare this two expressions without having to define my own comparison function? I suppose that pattern matching could be used here in some way (as in Erlang), but I don't know how.

Edit

I think that explaining my goal could help to understand the problem.

I'm modyfing an Abstract Syntax Tree (AST). I am going to apply a set of rules that are going to modify this AST, but I want to store the modifications in a list. The elements of this list should be a tuple with the original piece of the AST and its modification. So the last step is to for each tuple search for a piece of the AST that is exactly the same, and substitute it by the second element of the tuple. So, I will need something like this:

 change (old,new):t piece_of_ast =
     case piece_of_ast of 
          old -> new
          _ -> piece_of_ast

I hope this explanation clarify my problem.

Thanks in advance

Answer 1

It's probably an oversight in the library (but maybe I'm missing a subtle reason why Eq is a bad idea!) and I would contact the maintainer to get the needed Eq instances added in.

But for the record and the meantime, here's what you can do if the type you want to compare for equality doesn't have an instance for Eq, but does have one for Data - as is the case in your question.

The Data.Generics.Twins package offers a generic version of equality, with type

geq :: Data a => a -> a -> Bool

As the documentation states, this is 'Generic equality: an alternative to "deriving Eq" '. It works by comparing the toplevel constructors and if they are the same continues on to the subterms.

Since the Data class inherits from Typeable, you could even write a function like

veryGenericEq :: (Data a, Data b) => a -> b -> Bool
veryGenericEq a b = case (cast a) of
    Nothing -> False
    Maybe a' -> geq a' b

but I'm not sure this is a good idea - it certainly is unhaskelly, smashing all types into one big happy universe :-)

---

If you don't have a Data instance either, but the data type is simple enough that comparing for equality is 100% straightforward then StandaloneDeriving is the way to go, as @ChristianConkle indicates. To do this you need to add a {-# LANGUAGE StandaloneDeriving #-} pragma at the top of your file and add a number of clauses

deriving instance Eq a => Eq (CStatement a)

one for each type CStatement uses that doesn't have an Eq instance, like CAttribute. GHC will complain about each one you need, so you don't have to trawl through the source.

This will create a bunch of so-called 'orphan instances.' Normally, an instance like instance C T where will be defined in either the module that defines C or the module that defines T. Your instances are 'orphans' because they're separated from their 'parents.' Orphan instances can be bad because you might start using a new library which also has those instances defined; which instance should the compiler use? There's a little note on the Haskell wiki about this issue. If you're not publishing a library for others to use, it's fine; it's your problem and you can deal with it. It's also fine for testing; if you can implement Eq, then the library maintainer can probably include deriving Eq in the library itself, solving your problem.

Answer 2

I'm not familiar with Erlang, but Haskell does not assume that all expressions can be compared for equality. Consider, for instance, undefined == undefined or undefined == let x = x in x.

Equality testing with (==) is an operation on values. Values of some types are simply not comparable. Consider, for instance, two values of type IO String: return "s" and getLine. Are they equal? What if you run the program and type "s"?

On the other hand, consider this:

f :: IO Bool
f = do
      x <- return "s" -- note that using return like this is pointless
      y <- getLine
      return (x == y) -- both x and y have type String.

It's not clear what you're looking for. Pattern matching may be the answer, but if you're using a library type that's not an instance of Eq, the likely answer is that comparing two values is actually impossible (or that the library author has for some reason decided to impose that restriction).

What types, specifically, are you trying to compare?

Edit: As a commenter mentioned, you can also compare using Data. I don't know if that is easier for you in this situation, but to me it is unidiomatic; a hack.

You also asked why Haskell can't do "this sort of thing" automatically. There are a few reasons. In part it's historical; in part it's that, with deriving, Eq satisfies most needs.

But there's also an important principle in play: the public interface of a type ideally represents what you can actually do with values of that type. Your specific type is a bad example, because it exposes all its constructors, and it really looks like there should be an Eq instance for it. But there are many other libraries that do not expose the implementation of their types, and instead require you to use provided functions (and class instances). Haskell allows that abstraction; a library author can rely on the fact that a consumer can't muck about with implementation details (at least without using unsafe tools like unsafeCoerce).