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]
- compare 1 > 1, equal? yes, continue to next comparison
- compare 2 > 2, equal? yes, continue to next comparison
- 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