Comparing lists in Haskell, or more specifically what is lexicographical order?

This evaluates to True as 3 is greater than 2. Having found a result, the comparison stops here. He's demonstrating that 2 and 10 are not compared. The result of the array comparison is true. If the first array started with 2 as well, the comparison would result in false.

A nice example for when lexicographical ordering does not result in what the user would expect is file names in Windows. If you have files named xyz1.txt, xyz2.txt, xyz10.txt and xyz20.txt, the lexicographical order would be: xyz1.txt, xyz10.txt, xyz2.txt, xyz20.txt


"Lexicographic order" means similar to the way words are ordered in a dictionary: if the first element of each list is the same, compare the second elements; if the second elements are the same, compare the thirds; etc. If one list runs out of elements before the other, the shorter list is "less".


Example:

What happens when walking through the following?

[1,2,9,2] > [1,2,10,1] -- False

[ 1, 2, 9, 2]

[ 1, 2,10, 1]

  1. compare 1 > 1, equal? yes, continue to next comparison
  2. compare 2 > 2, equal? yes, continue to next comparison
  3. compare 9 > 10, equal? no, 9 is actually less, stop and return False

Other examples

[1,2,9,2] < [1,2,10,1] -- True

[1,2,3,4] <= [1,2,3,5] -- True

[1,2,3,4] >= [1,2,3,4] -- True

[1,2,3,4] <= [1,2,3,4] -- True


In addition to the other answers: actual definition of instance Ord for lists [in GHC] pretty much says it all:

instance (Ord a) => Ord [a] where
    compare []     []     = EQ
    compare []     (_:_)  = LT
    compare (_:_)  []     = GT
    compare (x:xs) (y:ys) = case compare x y of
                                EQ    -> compare xs ys
                                other -> other

Tags:

List

Haskell