В Haskell, как я могу использовать встроенную функцию sortBy для сортировки списка пар (кортеж)?

Question

Я новичок в Хаскеле, поэтому, пожалуйста, потерпите меня. (Только вчера начал учиться!) Как я могу отсортировать список кортежей в основном по первым компонентам (от наименьшего к меньшему) и по второму компоненту (от наименьшего к наибольшему)? Пример ввода / вывода будет:

[(1, "b"), (1, "a"), (2, "b"), (2, "a")] (вход)

[(1, "a"), (2, "a"), (1, "b"), (2, "b")] (средний шаг)

[(2, "a"), (2, "b"), (1, "a"), (1, "b")] (выход)

Я пытался использовать следующее, но это дало неправильный вывод:

sortGT a b = GT

sortBy sortGT lst

Я уверен, что смогу сделать это, используя только sortBy, но сам не могу понять это. Любая помощь будет принята с благодарностью!

Answer 1

Вам нужно построить свою функцию sortGT, чтобы она сравнивала пары так, как вы хотите:

sortGT (a1, b1) (a2, b2)
  | a1 < a2 = GT
  | a1 > a2 = LT
  | a1 == a2 = compare b1 b2

Используя это, вы получите следующие результаты (я использовал ghci):

*Main Data.List> sortBy sortGT [(1, "b"), (1, "a"), (2, "b"), (2, "a")]
[(2,"a"),(2,"b"),(1,"a"),(1,"b")]

Answer 2

Могу ли я предложить следующее?

import Data.List (sortBy)
import Data.Monoid (mconcat)

myPredicate (a1, a2) (b1, b2) = mconcat [compare b1 a1, compare a2 b2]

Затем можно отсортировать, написав sortBy myPredicate lst. Функция mconcat просто просматривает список и получает первый не EQ случай (или EQ, если все элементы равны EQ и, следовательно, обе пары считаются равными).

Если подумать, создание списка не обязательно.

import Data.List (sortBy)
import Data.Monoid (mappend)

myPredicate (a1, a2) (b1, b2) = compare b1 a1 `mappend` compare a2 b2

Определение mappend для Ordering по существу:

EQ `mappend` x = x
x  `mappend` _ = x

Что именно нам нужно.

Просто для удовольствия, обобщив ответ gbacon и сделав использование немного более гибким:

import Data.Ord
import Data.List
import Data.Monoid

ascending  = id
descending = flip

sortPairs f x g y = f (comparing x) `mappend` g (comparing y)

mySort = sortBy (sortPairs descending fst ascending snd)

Answer 3

Сначала мы должны сделать функцию упорядочения, которая принимает два касания и возвращает либо EQ, LT, либо GT (т. Е. sortGT :: (a,b) -> (a,b) -> Ordering.). Затем мы можем присвоить эту функцию упорядочения sortBy, и она будет сортируйте входные данные в соответствии с этим порядком.

Так как вы хотите, чтобы первые компоненты имели первый приоритет, мы проверяем это первым и, если они равны, мы проверяем второй аргумент, если первые компоненты не равны, мы присваиваем ему значение, противоположное первоначальному упорядочению, так что упорядочено по убыванию.

Это то, что я считаю наиболее простым для глаз:

sortGT (a1,b1) (a2,b2) = 
  case compare a1 a2 of
    EQ -> compare b1 b2
    LT -> GT
    GT -> LT

Теперь мы используем sortBy, как вы предложили:

*Main> sortBy sortGT [(1, "b"), (1, "a"), (2, "b"), (2, "a")]
[(2,"a"),(2,"b"),(1,"a"),(1,"b")]

Answer 4

Поздравляю с вашими первыми шагами по изучению Haskell. Это отличное путешествие!

Ответ на Ответ FredOverflow :

import Data.Ord
import Data.List
import Data.Monoid

main :: IO ()
main = do
  print $ sortBy cmp [(1, "b"), (1, "a"), (2, "b"), (2, "a")]
  where
    cmp = flip (comparing fst) `mappend` comparing snd

Выход:

[(2,"a"),(2,"b"),(1,"a"),(1,"b")]

Answer 5

Следующее решение лучше всего подходит для меня, новичка на Haskell. Это похоже на 3lectrologos 'ответ: на самом деле я только добавил определение функции и импорт списка, но это может вызвать некоторую путаницу, если ее не учесть.

Создайте функцию «myCompare» и не забудьте импортировать модуль «Список». Он понадобится вам, чтобы заставить sortBy работать. Функция должна выглядеть так:

import Data.List

myCompare :: (Ord a, Ord b) => (a,b) -> (a,b) -> Ordering  
myCompare (a1,b1) (a2,b2)
     | a1 < a2     = GT  
     | a2 == a1    = EQ  
     | otherwise = LT

После загрузки файла Haskell вы можете написать в своем терминале следующее:

*Main> sortBy myCompare [(1, "b"), (1, "a"), (2, "b"), (2, "a")]

Который вернется:

[(2,"a"),(2,"b"),(1,"a"),(1,"b")]

Answer 6

Мне нравится функция сравнения в Data.Ord. Это в основном ответ Грега в еще более компактной форме:

Prelude Data.Ord Data.List Data.Function> (reverse.sortBy (comparing fst)) [(1, "b"), (1, "a"), (2, "b"), (2, "a")]

[(2, "а"), (2, "б"), (1, "а"), (1, "б")]

"сравнение fst" дает порядок, основанный на первом элементе кортежа.

Answer 7

Всегда сложно составлять функции с двумя аргументами. Вот реализация:

invert :: Ordering -> Ordering
invert GT = LT
invert LT = GT
invert EQ = EQ


sosort :: (Ord a, Ord b) => [(a, b)] -> [(a, b)]
sosort = sortBy (\p p' -> invert $ uncurry compare $ double fst p p') . 
         sortBy (\p p' ->          uncurry compare $ double snd p p')
  where double f a a' = (f a, f a')

Поскольку sortBy ожидает функцию с двумя аргументами, состав функции не так хорош.

Я проверил этот код, и он работает на вашем примере.

Как указывает Фред, вы можете написать compare EQ вместо invert. Как указывает Дарио, я мог бы использовать on из Data.Function, но на самом деле on compare == comparing, который я могу использовать вместо этого. Теперь код может читать только мастер Haskell:

sosort :: (Ord a, Ord b) => [(a, b)] -> [(a, b)]
sosort = sortBy (compare EQ `post` comparing fst) . sortBy (comparing snd)
  where post f g x x' = f (g x x')

Я скомпилировал и запустил этот код, и он работает на оригинальном примере.

(У меня нет ни одного голоса за этот ответ, но благодаря хорошим комментариям я наверняка многое узнал о библиотеке Haskell. Кто знает, какой функции post соответствует? 1020 *

Было бы идиоматичнее написать подходящую функцию сравнения для пар , но ваш вопрос задавался для последовательных сортировок.