Почему sortBy не принимает (a → a → Bool)?

Функция Haskell sortBy принимает (a → a → Ordering) качестве первого аргумента. Может ли кто-нибудь научить меня тому, что такое рассуждение? Моя история полностью основана на языках, в которых вместо этого используется аналогичная функция take (a → a → Bool), поэтому необходимость написать ту, которая возвращает LT/GT была немного запутанной.

Это стандартный способ сделать это на статически типизированных/чисто функциональных языках? Это свойственно ML-спущенным языкам? Есть ли какое-то фундаментальное преимущество, которого я не вижу, или какой-то скрытый недостаток вместо использования логических значений?

Подводя итог:

Ordering не GT | LT GT | LT, это на самом деле GT | EQ | LT GT | EQ | LT GT | EQ | LT (очевидно, GHC не использует это под капотом для целей сортировки, но все же)
Возвращение трихотомического значения более точно моделирует возможные результаты сравнения двух элементов
В некоторых случаях использование Ordering вместо Bool сохранит сравнение
Использование Ordering упрощает реализацию стабильных сортировок.
Использование Ordering проясняет читателям, что проводится сравнение между двумя элементами (логическое значение по сути не несет этого значения, хотя я чувствую, что многие читатели примут это)

Я предварительно принимаю ответ Карла и публикую вышеизложенное резюме, так как ни один ответ не затронул все пункты на момент этого редактирования.

Ответ 1

Я думаю, что Boolean Blindness является основной причиной. Bool - это тип без семантики домена. Его семантика в случае такой функции, как sortBy, исходит исключительно из соглашения, а не из домена, на котором работает функция.

Это добавляет один уровень косвенности к психическому процессу, связанному с написанием функции сравнения. Вместо того, чтобы просто сказать: "Три значения, которые я могу вернуть, меньше, равно или больше", семантические строительные блоки упорядочения, вы говорите: "Я хочу вернуть меньше, поэтому я должен преобразовать его в логическое". Там есть дополнительный шаг, который всегда присутствует. Даже если вы хорошо разбираетесь в конвенции, это все равно немного замедляет вас. И если вы не разбираетесь в соглашении, вы немного замедляетесь, проверяя, что это такое.

Тот факт, что он 3-значный, а не 2-значный, означает, что вам не нужно быть столь же осторожным в своей реализации, чтобы получить стабильность, - но это небольшая деталь реализации. Это не так важно, как на самом деле ваши значения имеют значения. (Кроме того, Bool не более эффективен, чем Ordering. Это не примитив в Haskell. Они оба являются алгебраическими типами данных, определенными в библиотеках.)

Ответ 2

Когда вы разбираете вещи, вы приводите их в порядок; для определения не существует значения "истины".

В чем смысл "истины"? Что первый аргумент меньше второго? Больше чем? Теперь вы переопределяете "истину", чтобы на самом деле означать "меньше" (или "больше", в зависимости от того, как вы решили реализовать эту функцию). А что, если они равны?

Так почему бы не вырезать среднего человека, так сказать, и вернуть то, что вы на самом деле имеете в виду?

Ответ 3

Нет причин, по которым это не могло быть. Если вы посмотрите на ghc implementation, он проверяет, не является ли результат GT или нет. В версии кода Haskell Report используется insertBy, который также проверяет только на GT или нет. Вы можете написать следующее и использовать его без проблем:

sortByBool :: (a -> a -> Bool) -> [a] -> [a]
sortByBool lte = sortBy (\x y -> if lte x y then LT else GT)

sort' :: Ord a => [a] -> [a]
sort' = sortByBool (<=)

Некоторые виды могут, возможно, выполнять оптимизацию, зная, когда элементы EQ, но используемые в настоящее время реализации не нуждаются в этой информации.

Ответ 4

Для сохранения сравнений требуется трехзначный Ordering в случаях, когда нам нужно различать случай EQ. В дубликатах, сохраняющих sort или merge, мы игнорируем случай EQ, поэтому прецедент с семантикой с меньшим или равным значением является вполне приемлемым. Но не в случае union или nubSort, где мы хотим отличить три результата сравнения.

mergeBy lte (x:xs) (y:ys)
    | lte y x   = y : mergeBy lte (x:xs) ys
    | otherwise = x : mergeBy lte xs (y:ys)

union (x:xs) (y:ys) = case compare x y of 
    LT -> x : union  xs (y:ys) 
    EQ -> x : union  xs    ys 
    GT -> y : union (x:xs) ys

Запись последнего с предикатом lte является неестественной.

Ответ 5

Я думаю, что было два отдельных дизайнерских решения:
1) Создание типа Ordering
2) Выбор для sortBy для возврата значения Ordering

Тип Ordering полезен не только для sortBy - например, compare является "центральным элементом" класса Ord. Его тип :: Ord a => a -> a -> Ordering. Учитывая два значения, вы можете узнать, меньше ли они, больше или равно - с любой другой функцией сравнения ((<), (<=), (>), (>=)), вы можете только исключить одну из этих трех возможностей.

Вот простой пример, где Ordering (по крайней мере, на мой взгляд) делает функцию намерения немного яснее:

f a b = 
  case compare a b of
    GT -> {- something -}
    LT -> {- something -}
    EQ -> {- something -}

Как только вы решили создать тип Ordering, я считаю естественным использовать его в тех местах, где информация, которую вы действительно ищете (например, sortBy), вместо использования Bool as своего рода обходное решение.