Defining an Ord instance for Maybe datatype

Question

Is this a minimal complete definition of an Ord instance for Maybe datatype ? Is it correct ?

instance Ord (Maybe a) where
  compare (Just x) (Just y) | x < y     = LT
                            | x > y     = GT
                            | otherwise = EQ
  compare _        _                    = LT

instance Ord (Maybe a) where
  (Just x) <= (Just y) = x <= y
  _            _       = False

You could write down those two functions (outside of an instance declaration, and with a different name to avoid some confusing errors) and ask QuickCheck whether they match the default implementations. — Daniel Wagner
Wow, that's very interesting ! Thank you, @Daniel Wagner ! Could you tell me how can I ask QuickCheck what you suggest ? — F. Zer
Aside: when you write x < y or x <= y, how do you know that there are functions (<) and (<=) that you can use on x and y (both of which have type a)? You don't, unless you also know that there is an instance out there of Ord for a. So at a minimum, you need constraints on your instance: instance Ord a => Ord (Maybe a) where ... — liminalisht
@F.Zer Sure, once you named your implementation fZer'sCompare instead of compare, it would be something like quickCheck (\x y -> compare x y == fZer'sCompare x (y :: Maybe Int)). — Daniel Wagner
Thank you, @Daniel Wagner. The compiler says: "fZer'sCompare’ is not a (visible) method of class ‘Ord’". How can I solve this ? — F. Zer

Silvio Mayolo Silvio Mayolo · Accepted Answer · 2021-02-21T03:47:01

Is it complete in the sense that it covers all possible pattern cases? Sure; you have a catch-all at the end of both definitions. However, it's not a very good Ord instance, given that it violates the constraints set forth in the documentation.

Transitivity

if x <= y && y <= z = True, then x <= z = True

Reflexivity

x <= x = True

Antisymmetry

if x <= y && y <= x = True, then x == y = True

In particular, your second proposed relation is not reflexive, since Nothing <= Nothing is false. Your first relation is going to behave even more oddly, since Nothing <= Nothing will return true but Nothing >= Nothing will return false.

The built-in Ord instance for Maybe observes that Maybe a is isomorphic to a, plus an extra value we call Nothing, so it simply defines Nothing to be the minimum value for the ordering. The existing relation is equivalent to the following

instance Ord a => Ord (Maybe a) where
    compare Nothing Nothing = EQ
    compare Nothing (Just _) = LT
    compare (Just _) Nothing = GT
    compare (Just x) (Just y) = compare x y

Or, written in terms of <=,

instance Ord a => Ord (Maybe a) where
    Nothing <= _ = True
    Just _ <= Nothing = False
    Just x <= Just y = x <= y

Defining an Ord instance for Maybe datatype

1 Answers