Efficient way to write ordering instances?

Question

I'm working on a basic Haskell exercise that is set up as follows: a data definition is made, where Zero is declared to be a NaturalNumber, and a series of numbers (printed out by name, so, for instance, four) up to ten is constructed with this.

I didn't have too much trouble with understanding how the declaration of Eq instances works (apart from not having been given an exact explanation for the syntax), but I'm having trouble with declaring all instances I need for Ord -- I need to be able to construct an ordering over the entire set of numbers, such that I'll get True if I input "ten > nine" or something.

Right now, I have this snippet of code. The first two lines should be correct, as I copied them (as I was supposed to) from the exercise itself.

instance Ord NaturalNumber where
    compare Zero Zero   = EQ
    compare Zero (S Zero)  = LT
    compare (S Zero) Zero  = GT
    compare x    (S x)  = LT

The first four lines work fine, but they can't deal with cases like "compare four five", and anything similar to what I typed in the last doesn't work even if I type in something like compare four four = EQ: I get a "conflicting definitions" error, presumably because the x appears twice. If I write something like compare two one = GT instead, I get a "pattern match(es) are overlapped" warning, but it works. However, I also get the result GT when I input compare one two into the actual Haskell platform, so clearly something isn't working. This happens even if I add compare one two = LT below that line.

So clearly I can't finish off this description of Ord instances by writing every instance I could possibly need, and even if I could, it would be incredibly inefficient to write out all 100 instances by hand.

Might anyone be able to provide me with a hint as to how I can resolve this problem and finish off the construction of an ordering mechanism?

Answer 1

What this task focuses on is finding base cases and recursion rules. The first two lines you were given were

instance Ord NaturalNumber where
    compare Zero Zero   = EQ

This is the first base case, in words:

zero is equal to zero

The other two base cases are:

zero is less than the successor of any NaturalNumber

the successor of any NaturalNumber is greater than zero

Note that your lines three and four only say that 0 < 1 and 1 > 0, but nothing about any other nonzero numbers.

The recursion rule, then, is that it makes no difference if you compare two nonzero numbers, or the numbers they are successors of:

comparing 1 + x and 1 + y is the same as comparing x and y.

Codifying that into Haskell should give you the solution to this exercise.