Подсчитать вхождения в списке и вернуть его в другой список

Question

Я хочу сделать функцию с именем countAll. Эта функция должна получить список чисел и вернуть список (элемент, количество вхождений). Например : countAll [1,2,3,4,4,4] должен вернуться [(1,1), (2,1), (3,1), (4,3)] Я вынужден использовать функцию count, которую я разместил ниже.

count :: Eq a=> a -> [a] -> Int
count e [] = 0
count e (x:xs) 
 | e == x = 1 + count e xs
 | otherwise = count e xs

Answer 1

Использование быстрой структуры данных, например Data.IntMultiSet. Пусть ls = [1,2,3,4,4,4]

import qualified Data.IntMultiSet as IntMultiSet

IntMultiSet.fromList ls 

Альтернативное использование IntMap:

import qualified Data.IntMap.Strict as IntMap

IntMap.fromListWith (+) [(k,1) | k <- ls]

Answer 2

Мы можем добиться большего успеха, чем nub (что составляет O(n^2)), если элементы списка также являются экземплярами Ord, не требуя тяжелой техники IntMultiSet, сложив одинаковые элементы вместе с sort, а затемсгруппировать их в подсписки с group.Например, group . sort $ [1,2,3,4,4,4] дает [[1], [2], [3], [4,4,4]].

Как только мы упорядочим эти элементы в подсписки, мы можем подсчитать каждый подсписок:

countAll = map (\(x:xs) -> (x, count x (x:xs))) . group . sort

(Обратите внимание, что group гарантирует, чтоне будет пустых подсписков, поэтому мы знаем, что нам не нужно проверять регистр [] в нашей отображаемой функции, даже если компилятор этого не делает.)

Если нам не нужно использовать count, мы можем вместо этого использовать

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

или, с помощью удобного (&&&) комбинатора из Control.Arrow,

countAll = map (head &&& length) . group . sort

Поскольку список ассоциаций изэлементы с их количеством - это удобный способ представить сумку , мне нравится называть это

bag = map (head &&& length) . group . sort

bag равно O(n log n), что только на лог-фактор хуже, чемIntMultiSet версия.

Answer 3

Один из способов сделать это - понимание списка :

countAll xs = nub [(x, count x xs) | x <- xs]

nub удаляет дубликаты, и вам потребуется import Data.List (nub), чтобы использовать его.