2

假设我有一个像

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. 它要求调用者在第一个参数中指定所有可能的值。

有没有办法改善这一点？

4

3 回答 3

5

通常比使用 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]

如果您的类型本身是 in Ord，则可以跳过fromEnumand toEnum。

如果你有IxandBounded实例并且类型没有太多元素，

import Data.Array.Unboxed

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

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

于 2012-04-08T18:30:23.810 回答
4

也许是这样的？

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]

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

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

> countEnum' [C, C, A, C, A, C]
[2,0,4]
于 2012-04-08T18:11:53.073 回答
2

如果你有Ord，你可以使用键值对

import Control.List
import Control.Arrow

map (head &&& length) $ group $ sort elems
于 2012-04-08T20:37:10.007 回答