CODEWITHSUNDEEP
haskellfunctional-programming
F. Zer
F. Zer

Reputation: 1279

Defining an Ord instance for Maybe datatype

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

Upvotes: 0

Views: 482

Answers (1)

Silvio Mayolo
Silvio Mayolo

Reputation: 70267

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

Upvotes: 5

Related Questions