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)]

P.s rmdups，从列表中删除重复项，因此 rmdups "aaabc"= abc 并计数 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和rmdups定义它的最短方法。如果您需要按照频率(降序)排序，如您的示例所示，

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

使用Data.List中的sortBy和Data.Ord中的比较。

如果您只有一个 Eq 约束，则无法获得太多效率，但如果您只需要它用于 Ord 中的类型，则可以获得更高效的结果使用例如实现Data.Set 或 Data.Map。