list - 如何通过列表理解计算频率？

Question

count :: Eq a => a -> [a] -> Int
count n [] = 0
count n (x:xs) | n == x = 1 + count n xs
           | otherwise = count n xs



rmdups :: Eq a => [a] -> [a]
rmdups [ ] = [ ]
rmdups (x:xs) = x : rmdups (filter(/= x) xs)

使用这两个函数，需要创建第三个函数，称为频率：它应该计算列表中每个不同值在该列表中出现的次数。例如：频率“ababc”，应返回 [(3,'a'),(2,'b'),(1,'c')]。频率布局为：

frequency :: Eq a => [a] -> [(Int, a)]

Ps rmdups，从列表中删除重复项，因此 rmdups "aaabc" = abc 和 count 2 [1,2,2,2,3] = 3。

到目前为止，我有：

frequency :: Eq a => [a] -> [(Int, a)]
frequency [] = []
frequency (x:xs) = (count x:xs, x) : frequency (rmdups xs)

但这部分存在，（错误）。谢谢

Answer 1

frequency xs = map (\c -> (count c xs,c)) (rmdups xs)

或者，通过列表理解，

frequency xs = [(count c xs, c) | c <- rmdups xs]

count是使用and定义它的最短方法rmdups。如果您需要按照示例中的频率（降序）对其进行排序，

frequency xs = sortBy (flip $ comparing fst) $ map (\c -> (count c xs,c)) (rmdups xs)

使用sortByfromData.List和comparingfrom Data.Ord。

如果您所拥有的只是一个Eq约束，那么您将无法获得太多效率，但如果您只需要它用于类型 in ，则可以使用例如orOrd获得更有效的实现。Data.SetData.Map

Answer 2

这是我自己的“懒惰”答案，它不调用 rmdups：

frequency [] = []
frequency (y:ys) = [(count y (y:ys), y)] ++ frequency (filter (/= y) ys)

Answer 3

import qualified Data.Set as Set

frequency xs = map (\x -> (length $ filter (== x) xs, x)) (Set.toList $ Set.fromList xs)