计算列表中每个元素的所有出现次数

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