Подсчет уникальных элементов в списке

Question

Существует ли прямая комбинация стандартных функций высшего порядка для подсчета уникальных элементов в списке?

Например, результат для

[1, 1, 4, 0, 4, 4]

будет выглядеть примерно так:

[(1,2), (4,3), (0,1)]

Answer 1

Использование разделов Data.Map и кортежа:

 count = Map.fromListWith (+) . map (, 1)

(Добавьте Map.toList, если вам нужен список.)

Answer 2

Если порядок не важен, это работает:

map (\xs@(x:_) -> (x, length xs)) . group . sort

group . sort предоставит вам список списков, в которых все равные друг другу элементы сгруппированы в один и тот же подсписок (без сортировки будут сгруппированы только последовательные равные элементы). map затем превращает каждый подсписок в (element, lengthOfSublist) -тупле.

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

Answer 3

Самое простое - отсортировать элементы по порядку, использовать «группу», чтобы поместить их в подсписки равных элементов, а затем подсчитать элементы в каждом подсписке.

map (\xs -> (head xs, length xs)) . group . sort

Answer 4

Если список содержит только целые числа, вы также можете использовать

 import qualified Data.IntMap as I

 countElems1 :: [Int] -> [(Int, Int)]
 countElems1 = I.toList . foldr (\k -> I.insertWith (+) k 1) I.empty 

(хотя не забудьте скомпилировать с оптимизацией, иначе это будет в 2 раза медленнее, чем метод group . sort. При -O2 этонемного быстрее на 14%.)

Вы также можете использовать один из мультимножество пакетов , что делает функцию такой простой, как

 import qualified Math.Combinatorics.Multiset as S
 countElems4 = S.toCounts . S.fromList

но будучи менее эффективным.

Все вышеперечисленные решения игнорируют первоначальный порядок.

Answer 5

То, о чем вы говорите, это просто кодировка длины пробега на отсортированных данных: бесплатная онлайн-книга Real World Haskell имеет отличный пример этого .Вы захотите отсортировать список, прежде чем пропустить его через runLengthEncoder.