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

これは機能しますが、少なくとも 2 つの問題があります。

  1. 機能を利用していlengthます。
  2. 呼び出し元は、最初の引数ですべての可能な値を指定する必要があります。

これを改善する方法はありますか？

4

3 に答える 3

5

通常、リストを並べ替えるよりも少し速いのは、を使用すること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をスキップできます。fromEnumtoEnum

IxインスタンスがありBounded、タイプに要素が多すぎない場合は、

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 に答える
2

をお持ちOrdの場合は、次を使用してキーと値のペアを取得できます

import Control.List
import Control.Arrow

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