Подсчет частоты перечисления значений

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
• пары (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) 

имеет лучшую асимптотику, использует меньше памяти и быстрее уже довольно короткие списки. (Но это зависит от высокой доли элементов типа бытия присутствует в списке.)

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] 

Если вы можете определить 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] 

Answer 3

Если у вас есть Ord, вы можете иметь пары ключ-значение с помощью

import Control.List 
import Control.Arrow 

map (head &&& length) $ group $ sort elems