Avoid the tedious implementation of Ord

Question

I have a data type with quite a few constructors, they are all simple enough that Haskell can automatically output an instance of Ord. How in:

data Foo a = A a | B Int deriving (Eq, Ord) 

Now I want to add a third constructor, for example:

 data Foo a = A a | B Int | C a (a -> Bool) 

But now Haskell cannot manually output Eq and Ord to Foo for me. Now it happens that I have some domain-related knowledge about how two values ​​built using C should be ordered:

 instance Eq a => Eq (Foo a) where -- Boilerplate I don't want to write A x == A y = x == y B x == B y = x == y -- This is the case I really care about C xf == C yg = x == y && fx == gy _ == _ = False instance Ord a => Ord (Foo a) where -- Boilerplate I don't want to write A x `compare` A y = x `compare` y A x `compare` _ = LT B x `compare` B y = x `compare` y B x `compare` A _ = GT B _ `compare` _ = LT -- This is the case I really care about C xf `compare` C yg | x == y = fx `compare` gy | otherwise = x `compare` y C{} `compare` _ = GT 

But for this, I also need to manually sort by the values ​​of A and B, which is very tiring (especially for an Ord instance).

Is there any trick that would allow me to implement (==) and compare only with C code, but somehow get the default behavior for other constructors?

Answer 1

Since you know something special about these functions, consider storing information about something special and recounting to function only when necessary. For example, you may know that they partially apply (<) ; then something like this:

 {-# LANGUAGE PatternSynonyms #-} {-# LANGUAGE ViewPatterns #-} data Foo a = A a | B Int | C_ aa deriving (Eq, Ord, Read, Show) pattern C af <- C_ a ((<) -> f) 

Of course, if you have a more complex expression language than just adding, you might want to define a separate type for your AST and a separate function for evaluating AST; but the ACT itself should, in the simplest cases when your proposed comparison rule is correct, be de-equal / ordered.

Answer 2

You can parameterize Foo using special case types, and then apply special instances separately for new types:

 data Foo' ca = A a | B Int | C (ca) deriving (Eq, Ord) data C a = MkC a (a -> Bool) instance Eq a => Eq (C a) where MkC xf == MkC yg = x == y && fx == gy instance Ord a => Ord (C a) where MkC xf `compare` MkC yg | x == y = fx `compare` gy | otherwise = x `compare` y type Foo = Foo' C 

Answer 3

This "package" of the function - its argument (known as Store comonad (.. which does not have an Eq instance)) may be the Eq and Ord instances you are looking

 data Store sa = Store (s -> a) s instance (Eq s, Eq a) => Eq (Store sa) where (==) :: Store sa -> Store sa -> Bool Store fs == Store f' s' = (s == s') && (fs == f' s') instance (Ord s, Ord a) => Ord (Store sa) where compare :: Store sa -> Store sa -> Ordering Store fs `compare` Store f' s' = (compare s s') <> (fs `compare` f' s') 

Now you can get both Eq and Ord

 data Foo a = A a | B Int | C (Store a Bool) deriving (Eq, Ord)