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

Ответ 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")]

Ответ 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)

Ответ 3

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

Riffing on Ответ 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")]

Ответ 4

Сначала мы должны сделать функцию упорядочения, которая берет два кортежа и возвращает либо 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")]

Ответ 5

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

Создайте функцию 'myCompare' и не забудьте импортировать модуль List. Вам понадобится, чтобы сделать 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")]

Ответ 6

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

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 эквивалентна? Не Hoogle...)

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

Ответ 7

Мне нравится функция сравнения в 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" дает упорядочение на основе первого элемента кортежа.