如何有效地计算列表中每个元素的所有出现次数？我想过使用关联列表或一些 HashMap ，但不可变性妨碍了它，而且显然不清楚应该如何(希望如此)优雅的解决方案。

签名可能是这样的:

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

例子:

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

结果

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

(尽管顺序并不重要)。

最佳答案

组。 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) 时间。

https://stackoverflow.com/questions/55143882/