计算枚举值的频率

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

通常比使用Map对列表进行排序要快一些，

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

你可以得到

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

如果您的类型本身在 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)

具有更好的渐近行为，使用更少的内存，并且对于相当短的列表已经更快。（但这取决于列表中存在很大比例的类型元素。

Answer 2

也许是这样的？

import Control.Arrow ((&&&))
import Data.Function (on)
import Data.List (groupBy, sortBy)
data T = A | B | C deriving Enum
countEnum :: Enum a => [a] -> [Int]
countEnum = map length . groupBy ((==) `on` snd) . sortBy (compare `on` snd) . map (id &&& fromEnum)

例如：

> countEnum [B, C, C, A, C, A, C]
[2,1,4]

如果可以为T定义一个Bounded实例，则有可能计算零次出现：

countEnum' :: (Bounded a, Enum a) => [a] -> [Int]
countEnum' = map pred . countEnum . (++ enumFromTo minBound maxBound)
> countEnum' [C, C, A, C, A, C]
[2,0,4]

Answer 3

如果您有 Ord ，则可以使用

import Control.List
import Control.Arrow
map (head &&& length) $ group $ sort elems