Using different Ordering for Sets

Question

I was reading a Chapter 2 of Purely Functional Data Structures, which talks about unordered sets implemented as binary search trees. The code is written in ML, and ends up showing a signature ORDERED and a functor UnbalancedSet(Element: ORDERED): SET. Coming from more of a C++ background, this makes sense to me; custom comparison function objects form part of the type and can be passed in at construction time, and this seems fairly analogous to the ML functor way of doing things.

When it comes to Haskell, it seems the behavior depends only on the Ord instance, so if I wanted to have a set that had its order reversed, it seems like I'd have to use a newtype instance, e.g.

newtype ReverseInt = ReverseInt Int deriving (Eq, Show)

instance Ord ReverseInt where
    compare (ReverseInt a) (ReverseInt b)  
        | a == b = EQ
        | a < b  = GT
        | a > b  = LT

which I could then use in a set:

let x = Set.fromList $ map ReverseInt [1..5]

Is there any better way of doing this sort of thing that doesn't resort to using newtype to create a different Ord instance?

Answer 1

No, this is really the way to go. Yes, having a newtype is sometimes annoying but you get some big benefits:

• When you see a Set a and you know a, you immediately know what type of comparison it uses (sort of the same way that purity makes code more readable by not making you have to trace execution). You don't have to know where that Set a comes from.
• For many cases, you can coerce your way through multiple newtypes at once. For example, I can turn xs = [1,2,3] :: Int into ys = [ReverseInt 1, ReverseInt 2, ReverseInt 3] :: [ReverseInt] just using ys = coerce xs :: [ReverseInt]. Unfortunately, that isn't the case for Set (and it shouldn't - you'd need the coercion function to be monotonic to not screw up the data structure invariants, and there is not yet a way to express that in the type system).
• newtypes end up being more composable than you expect. For example, the ReverseInt type you made already exists in a form that generalizes to reversing any type with an Ord constraint: it is called Down. To be explicit, you could use Down Int instead of ReversedInt, and you get the instance you wrote out for free!

Of course, if you still feel very strongly about this, nothing is stopping you from writing your version of Set which has to have a field which is the comparison function it uses. Something like

data Set a = Set { comparisionKey :: a -> a -> Ordering
                 , ...
                 }

Then, every time you make a Set, you would have to pass in the comparison key.