Сравнение списков в Haskell, а точнее, что такое лексикографический порядок?

Я только начинаю этот классный учебник для начинающих хэшкелл:

на этой странице в списках он объясняет, что списки сравниваются по сравнению с лексикографическим порядком, он приводит этот пример:

ghci> [3,2,1] > [2,10,100]
True

Из какого-то googling мне кажется, что лексикографическое упорядочение означает в алфавитном или последовательном упорядочении чисел (?), но я до сих пор не могу понять, что это оценивает True.

Мне не хватает чего-то очевидного здесь, может ли кто-нибудь помочь?

Ответ 1

Это оценивается как True, так как 3 больше 2. Получив результат, сравнение останавливается здесь. Он демонстрирует, что 2 и 10 не сравниваются. Результатом сравнения массива является True. Если первый массив начался с 2, то сравнение приведет к false.

Хороший пример, когда лексикографическое упорядочение не приводит к тому, что пользователь будет ожидать, это имена файлов в Windows. Если у вас есть файлы с именем xyz1.txt, xyz2.txt, xyz10.txt и xyz20.txt, лексикографический порядок будет выглядеть следующим образом: xyz1.txt, xyz10.txt, xyz2.txt, xyz20.txt

Ответ 2

"Лексикографический порядок" означает аналогично тому, как слова упорядочены в словаре: если первый элемент каждый список один и тот же, сравните второй элемент; если остальные элементы одинаковы, сравните третьи; и т.д. Если в одном списке заканчиваются элементы перед другим, более короткий список "меньше".

Ответ 3

В дополнение к другим ответам: фактическое определение instance Ord для списков [в GHC] в значительной степени говорит обо всем:

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

Ответ 4

Пример:

Что происходит при ходьбе через следующее?

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

[1, 2, 9, 2]

[1, 2, 10, 1]

сравнить 1> 1, равно? да, перейти к следующему сравнению
сравнить 2> 2, равно? да, перейти к следующему сравнению
сравнить 9> 10, равно? нет, 9 на самом деле меньше, остановись и вернись False

Другие примеры

[1,2, 9, 2] <[1,2, 10, 1] - верно

[1,2,3, 4] <= [1,2,3, 5] - Правда

[1,2,3,4]> = [1,2,3,4] - верно

[1,2,3,4] <= [1,2,3,4] - верно

Ответ 5

Просто поймите это: сравнение двух списков не означает сравнение значений всех элементов в каждом списке. Скорее это просто сравнение лексического порядка каждого элемента в списке1 с соответствующим элементом в списке2 и возвращение результата, как только он обнаружил, что два элемента упорядочены по-разному лексически.

Ответ 6

Я думаю, что LearnYouAHaskell выиграет от написания слова Only.

First the heads are compared. *Only* if they are equal then the second elements are compared, etc.

Таким образом, поскольку 3 больше 2, решение принято, и нет необходимости проверять индексы 1 и 2.

[3,2,1] > [2,10,100] == [3] > [2]

Это также может быть немного похоже на сортируемую дату

2019-07-06 > 2011-08-09

Если вы делаете это в своей голове, вы сначала проверяли годы, и вам не нужно проверять месяцы или дни, чтобы узнать, что первая дата больше.