list - 按字符频率对字符串进行排序

Question

我刚开始使用 Haskell，遇到以下问题:我想以特定方式对 String 进行排序。所有字符都应彼此相邻，它们在结果字符串中的一般位置应取决于它们在原始字符串中出现的频率。例如:

“aabcbb”应该返回“caabbb”

我的第一个想法是先对字符串进行排序，然后将字符分组到列表的列表中，比较所述列表的长度并尝试以某种方式对它们进行排序。但是，我坚持尝试将 String 转换为字符列表的列表。我已经完成了我的第一次排序:

listify :: String -> [Char]
listify [] = []
listify (x:xs) = [x] ++ listify isInRest ++ listify notInRest
         where
          isInRest = [y | y <-xs, y==x]
          notInRest = [z | z <-xs, z/=x]

这显然返回一个排序列表，但按出现顺序排列(在我上面的示例中为“aabbbc”)。我真的不知道如何继续。

另外，总的来说，我真的不明白为什么我不能以另一种方式处理我的函数的第一个选项。我试过了

listify :: String -> [Char]
listify (x:xs)
        | x == [] = []
        | x == "" = ""

我不会同时使用这两个选项，但我不确定如何处理这种样式的空列表，因为我收到以下错误并且我不确定如何处理这些错误:

我们将不胜感激。

Answer 1

所有这些函数都已经存在于标准库中。您可以做的最简单的事情是

import Data.Ord
import Data.List

f = concat . sortBy (comparing length) . group . sort

或者，由于 length 是 O(n)，这里有一个更有效的方法:

import Data.Ord
import Data.List
import Control.Arrow

f = concatMap snd . sortBy (comparing fst) . map (length &&& id) . group . sort

此外，String 与 [Char] 相同。

你不能在这里比较x和[]

listify :: String -> [Char]
listify (x:xs)
        | x == [] = []
        | x == "" = ""

因为 x 的类型是 Char，它不是列表。