Сортировка списка пар с использованием сортировки Haskell

Question

У меня есть функция (частота), которая подсчитывает, сколько раз каждое отдельное значение в списке происходит в этом списке. Например,

frequency "ababca" 

должен вернуться:

[(3, 'a'), (2, 'b'), (1, 'c')]. 

Это прекрасно работает, но теперь мне нужно отсортировать список, используя первый элемент в списке в списке, используя эту функцию.

results :: [Party ] -> [(Int, Party)] 
results xs = ??? frequency (sort xs) ??? 

пример желаемых результатов:

[(1, "Green"), (2, "Red"), (3, "Blue")] 

выше не работает, я понятия не имею, что я могу сделать.

с помощью регулярных 'рода'

Спасибо заранее.

Answer 1

import Data.Function (on) 
import Data.List (sortBy) 

results xs = sortBy (compare `on` fst) (frequency xs) 

-- or, if you prefer 
results xs = sort (frequency xs) 

Ссылки на документацию для on, sortBy, compare, fst.

Разница в том, что sort сортирует в порядке возрастания первого элемента каждой пары, разбивая разрывы со вторыми элементами пар, а sortBy (compare `on` fst) явно просматривает только первый элемент каждой пары.

Answer 2

Если вы можете использовать только sort, а не sortBy (по какой-то причине!), То вам нужно убедиться, что элементы имеют тип, который является экземпляром Ord. Как это бывает, все кортежи (до размера 15) имеют Ord экземпляров, при условии, что все позиции в кортеже также имеют Ord экземпляров.

пример вы даете из (1, "Green"), (2, "Red"), (3, "Blue")] должны сортировать в порядке (хотя в обратном порядке), так как Int и String имеют Ord экземпляров.

Однако в фрагменте кода вы также указываете тип Party, фактически не говоря, что это такое. Если это не просто псевдоним для чего-то вроде String, вам может понадобиться определить для него экземпляр Ord, чтобы удовлетворить встроенные экземпляры Ord для кортежей.

Вы можете Haskell создавать экземпляры для вас, используя deriving при объявлении типа

data Party = P1 | P2 | P3 | P4 -- e.g. 
    deriving (Eq,Ord) 

или объявить его самостоятельно:

instance Ord Party where 
    -- you don't care about the ordering of the party values 
    compare a b = EQ 

Но, как говорит dave4420, это гораздо лучше просто используйте sortBy, поэтому я бы сделал это, если у вас нет конкретной причины (например, это назначение класса с ограничениями).