What determines data constructor order in Haskell?

Question

When I run this on Haskell:

[2] <= [1,5]

I get False.

However, when I run this:

data T = A | B | C T T deriving (Eq,Ord)
A <= B && B <= C A A

I get True.

Why is this? Shouldn't B <= C A A be false for the same reason [2] < [1,5] is too?

Answer 1

The Haskell report specifies how the automatically derived instances should look like:

10.1 Derived instances of Eq and Ord

The class methods automatically introduced by derived instances of Eq and Ord are (==), (/=), compare, (<), (<=), (>), (>=), max, and min. The latter seven operators are defined so as to compare their arguments lexicographically with respect to the constructor set given, with earlier constructors in the datatype declaration counting as smaller than later ones.

For example, for the Bool datatype, we have that (True > False) == True.

Derived comparisons always traverse constructors from left to right. These examples illustrate this property:

  (1,undefined) == (2,undefined) =>    False
  (undefined,1) == (undefined,2) =>    _|_

All derived operations of class Eq and Ord are strict in both arguments. For example, False <= _|_ is _|_, even though False is the first constructor of the Bool type.

So Haskell will implement an Ord function here where, regardless of the arguments, an object with data constructor A will be less than an object with data constructor B, and an object with data constructor B is less than an object with data constructor C. This is because A has been defined before B has been defined.

Only in case the data constructor is the same, it compares the arguments lexicographically: so first the first arguments of both objects are compares, and if these are not equal, that is the result of the comparison, in case these are, then we compare the second arguments, and so on.

So for your T type, these are implemented as:

instance Ord T where
    (<=) A A = True
    (<=) A B = True
    (<=) A (C _ _) = True
    (<=) B C = True
    (<=) B (C _ _) = True
    (<=) (C xa ya) (C xb yb) = xa <= xb || (xa == xb && ya <= yb)
    (<=) _ _ = False

If a list is defined as:

data [] a = [] | (:) a ([] a)

then the order of a list also follows from that definition, since an empty list is less than a non-empty list, and in case we compare two non-empty lists, we first compare the first elements (first argument of the "cons" data constructor), and then in case of an equal head, we compare the tails (second argument of the "cons" constructor). So an automatic derivation would look like:

import Data.Monoid((<>))

instance Ord ([] a) where
    compare [] [] = EQ
    compare [] (_:_) = LT
    compare (_:_) [] = GT
    compare (ha:ta) (hb:tb) = compare ha hb <> compare ta tb

here the (<>) operator for Orderings takes the left element if it is not equal to EQ and the right element otherwise.