Inconsistent instances of Eq and Ord?

Question

I have a great Haskell program that is hard to work with. Profiling and testing have shown that most of the time is spent comparing the equality and ordering of a certain large data type, which is very important. Equality is a useful operation (it is a search in the state space, and a graph search is much preferable to a tree search), but to use Maps I need an Ord instance for this class. So I want to say

instance Eq BigThing where (==) bb' = name b == name b' && firstPart b == firstPart b' && secondPart b == secondPart b' && {- ...and so on... -} instance Ord BigThing where compare bb' = compare (name b) (name b') 

But since the names may not always be different for different objects, this risks the curious case when two BigThings may be unequal in accordance with ==, but when comparing them we get EQ.

Will this cause problems with Haskell libraries? Is there any other way that I could satisfy the requirement of a detailed equality operation, but a cheap order?

Answer 1

Firstly, using Text or ByteString instead of String can help without changing anything.

In general, I would not recommend creating an Eq instance that is not compatible with Ord . Libraries can rightfully rely on this, and you never know what strange problems it can cause. (For example, are you sure Map doesn't use the relationship between Eq and Ord ?)

---

If you don’t need an Eq instance at all, you can simply define

 instance Eq BigThing where x == y = compare xy == EQ 

Then equality will match. There is no requirement that equal values ​​must have all fields equal.

---

If you need an Eq instance that compares all fields, you can stay consistent by wrapping BigThing in newtype , define Eq and Ord above it and use it in your algorithm when you need to sort by name :

 newtype BigThing' abc = BigThing' (BigThing abc) instance Eq BigThing' where x == y = compare xy == EQ instance Ord BigThing' where compare (BigThing b) (BigThing b') = compare (name b) (name b') 

---

Update:. Since you say that any order is acceptable, you can use hashing to your advantage. You can use the hashable package for this . The idea is that you pre-compute the hash values ​​when creating the data and use them when comparing the values. If the two values ​​are different from each other, he is almost sure that their hashes will be different, and you only compare their hashes (two integers), nothing more. It might look like this:

 module BigThing ( BigThing() , bigThing , btHash, btName, btSurname ) where import Data.Hashable data BigThing = BigThing { btHash :: Int, btName :: String, btSurname :: String } -- etc deriving (Eq, Ord) -- Since the derived Eq/Ord instances compare fields lexicographically and -- btHash is the first, they'll compare the hash first and continue with the -- other fields only if the hashes are equal. -- See http://www.haskell.org/onlinereport/derived.html#sect10.1 -- -- Alternativelly, you can create similar Eq/Ord instances yourself, if for any -- reason you don't want the hash to be the first field. -- A smart constructor for creating instances. Your module will not export the -- BigThing constructor, it will export this function instead: bigThing :: String -> String -> BigThing bigThing nm snm = BigThing (hash (nm, snm)) nm snm 

Note that with this solution, the ordering will appear random without a visible relation to the fields.

You can also combine this solution with the previous ones. Or you can create a small module for packaging any type with its pre-computed hash (wrapped values ​​should have Eq instances corresponding to their Hashable instances).

 module HashOrd ( Hashed() , getHashed , hashedHash ) where import Data.Hashable data Hashed a = Hashed { hashedHash :: Int, getHashed :: a } deriving (Ord, Eq, Show, Read, Bounded) hashed :: (Hashable a) => a -> Hashed a hashed x = Hashed (hash x) x instance Hashable a => Hashable (Hashed a) where hashWithSalt salt (Hashed _ x) = hashWithSalt salt x