I am looking to implement a "general" ordinal type that supports multiple "infinities" (e.g. [1,2,..., W, W+1, W+2, .. , 2 W, .., WW, etc]). I was thinking of implementing as a composite number (e.g. [5:4:2578] < [1:5:4:2578] < [1:5:4:2579] < [1:5:5:2]) with Ints, where comparison starts from the end of the list.
Currently i have implemented it as:
newtype Ordinal = Order [Int]
deriving (Eq)
instance Ord Ordinal where
(<=) x@(Order xl) y@(Order yl)
| null xl && null yl = x == y
| null xl = (Order [0]) <= y
| null yl = x <= (Order [0])
| last xl /= last yl = last xl <= last yl
| otherwise = (init xl) <= (init yl)
I feel like my code is not clean / elegant enough. Is there a standardized library / datatype that already does this? Can i refactor my code more?
Fundamentally, you have a logical error as pointed out by @4castle. In short, you should only be comparing most significant digits if they are of the same significance. For instance, [1,2] is clearly greater than [3] even though the last element of [3] is greater than the last element of [1,2] because the 2 is of greater significance than the 3. You may find that length is useful here.
One elegant strategy is to do a preliminary check for whether one of your Ordinals is clearly bigger than the other (that is, has digits with higher significance, or is "structurally bigger"), and only continue with the recursive underlying numerical check if not. As such, consider defining the recursive part as a helper function; and since it's a helper function anyway, you can call it with the reverse of the ordinal lists, allowing you to do simple pattern matching on the lists, comparing the most significant digit first, without needing "ugly" functions like last and init.