Подсчитать все вхождения каждого элемента в списке

Question

Как эффективно подсчитать все вхождения каждого элемента в списке? Я думал об использовании ассоциативного списка или некоторой хэш-карты, но на пути мешает неизменность, и неясно, как должно возникать (надеюсь) элегантное решение.

Подпись может быть такой:

countOccurences :: [a] -> [(a, Int)]

Пример:

countOccurences [1, 1, 2, 3, 1, 2, 4] 

Результаты в

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

(хотя порядок не важен).

Answer 1

group . sort создаст список вывода, такой как

> group . sort $ [1, 1, 2, 3, 1, 2, 4] 
[[1,1,1],[2,2],[3],[4]]

Следовательно,

> map (head &&& length) . group . sort $ [1, 1, 2, 3, 1, 2, 4] 
[(1,3),(2,2),(3,1),(4,1)]

Итак, получаем

import Data.List (group, sort)
import Control.Arrow ((&&&))

countOccurences :: Ord a => [a] -> [(a, Int)]
countOccurences = map (head &&& length) . group . sort

Это должно потребовать только O(n log n) времени.

Answer 2

Так как chi предоставил решение, используя group . sort, вот то, которое использует Data.Map:

import qualified Data.Map.Strict as M
import           Data.Map.Strict (Map)

histogram :: Ord a => [a] -> Map a Int
histogram = M.fromListWith (+) . (`zip` [1,1..])

Это также использует O (n log n) время.

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

Data.Map - это ассоциативная карта на основе дереватак что, возможно, это представление для вас.

Если вы предпочитаете [(a, Int)], M.assocs может преобразовать Data.Map обратно:

countOccurrences :: Ord a => [a] -> [(a, Int)]
countOccurrences = M.assocs . histogram