计算枚举值的频率

Question

假设我有一个类似的枚举

data T = A | B | C deriving (Enum)

和枚举值列表作为输入:

[B, C, C, A, C, A, C]

我正在寻找的是一个函数,给定此输入,返回每个元素在输入中出现的频率.输出的简单形式是频率列表([2, 1, 4]在这种情况下),但这不是必需的.我目前的方法如下:

countEnum :: Enum a => [a] -> [a] -> [Word]

countEnum elems =
  let f x = map (fromIntegral . fromEnum . (fromEnum x ==)) [0 .. length elems - 1]
  in foldr (zipWith (+)) (replicate (length elems) 0) . map f

这有效,但我发现至少有两个问题:

1. 它使用该length功能.
2. 它要求调用者在第一个参数中指定所有可能的值.

有没有办法改善这个？

Answer 1

通常比排序列表快一点是使用a Map,

enumFreq :: Enum a => [a] -> Map Int Word
enumFreq = foldl' (\mp e -> Map.insertWith' (+) (fromEnum e) 1 mp) Map.empty

你可以得到

• 每个频率 Map.elems $ enumFreq list
• (value,frequency)每对[(toEnum i, f) | (i,f) <- Map.assocs $ enumFreq list]

如果您的类型本身Ord,您可以跳过fromEnum和toEnum.

如果你有Ix和Bounded实例和类型没有太多的元素,

import Data.Array.Unboxed

enumFreq :: (Ix a, Bounded a) => [a] -> UArray a Word
enumFreq = accumArray (+) 0 (minBound,maxBound) . (`zip` repeat 1)

具有更好的渐近行为,使用更少的内存,并且对于相当短的列表已经更快.(但这取决于列表中存在的大部分类型元素.)