Creating Ord instances with newtype wrapping

Question

Given a datatype such as

data Foo = Bar | Baz | Qux

and I wish to have multiple different orderings for this type, is the following the most common/standard way to achieve this?

newtype FooPriorityA = FooPriorityA { unFooPriorityA :: Foo }

instance Ord FooPriorityA where
    compare (FooPriorityA x) (FooPriorityA y) = f x `compare` f y
        where f :: Foo -> Int
              f Baz = 1
              f Bar = 2
              f Qux = 3

newtype FooPriorityB = FooPriorityB ... and so on

Is delegating to Int's Ord instance like that crazy? It feels safer and a whole lot less work than writing out the n^2 comparisons for compare.

Any obvious flaws I might have overlooked with this "hack"? Is it even a "hack"?

Answer 1

You only need O(n) (2​n - 1, to be precise) definitions to specify a total order, as long as you specify the cases in increasing order of priority:

instance Ord FooPriorityA where
    compare (FooPriorityA x) (FooPriorityA y) | x == y = EQ   -- Use the Eq instance
                                              -- Bar is the smallest
                                              | x == Bar = LT
                                              | y == Bar = GT
                                              -- Baz is the next smallest
                                              | x == Baz = LT
                                              | y == Baz = GT
                                              -- Proceed in the desired order.
                                              -- You don't need to say anything
                                              -- explicit about the largest value

The first case (x == y) covers O(n) possibilities. Each case that follows may look incomplete, but it carries the implied information that each preceding case is false. For example, x == Bar = LT does not mean that every case where x == Bar evaluates to LT; the case where x == Bar && y == Bar is already handled, so the second case is really implicitly x == Bar && y /= Bar.

Likewise, case 4 (x == Baz) carries the assumption that y /= Baz (implied by the failure of case 1 to match) and y /= Bar (implied by the failure of case 3 to match). Therefore, any remaining possible value for y is, in fact, greater than Baz.

The further down the list you go, the fewer unhandled cases remain. By the end, you don't need to say anything explicit about the largest item; all the information about how it compares to the other n - 1 items has already been captured by the preceding cases.

---

Also, keep in mind that your definition of f is one half (fromEnum) of the minimum implementation of an instance of the Enum class, which you could then use to define your Ord instance.

instance Enum FooPriorityA where
     fromEnum Bar = 1
     fromEnum Baz = 2
     fromEnum Qux = 3
     toEnum 1 = Bar
     toEnum 2 = Baz
     toEnum 3 = Qux

instance Ord FooPriorityA where
    compare x y = compare (fromEnum x) (fromEnum y)
    -- compare = compare `on` Data.Function.fromEnum