计数每个元件的频率列表中的(Count frequency of each element in a

我试着写一个程序，将统计每个元件的频率在列表中。

    In: "aabbcabb"
    Out: [("a",3),("b",4),("c",1)]

你可以查看我下面的链接代码： http://codepad.org/nyIECIT2在这段代码独特功能的输出会是这样

     In: "aabbcabb"
     Out: "abc"

使用独特的输出之后我们将计算目标列表的频率。您还可以在这里看到的代码：

    frequencyOfElt xs=ans
       where ans=countElt(unique xs) xs
          unique []=[]
      unique xs=(head xs):(unique (filter((/=)(head xs))xs))
      countElt ref target=ans'
             where ans'=zip ref lengths
            lengths=map length $ zipWith($)(map[(=='a'),(==',b'),(==',c')](filter.(==))ref)(repeat target)

    Error:Syntax error in input (unexpected symbol "unique")

但在ghci中6.13其他类型的错误也显示出

很少有问我什么是使用的目的[（== 'A'），（== 'B '），（=='，C'）。我期待什么：如果REF =“ABC”和目标=“aabbaacc”，那么

    zipWith($) (map filter ref)(repeat target)

将显示[“AAAA”，“BB”，“CC”]然后我可以使用地图长度移到该其中i使用ref [（==“A”），（==”根据得到的频率这里过滤列表，b '），（=='，C'）]

我假定一些逻辑错误谎言[（== 'A'），（== 'B '），（=='，C'）]在这里..

Answer 1:

你没有说你是否想将它写在整个你自己的，还是它的确定，从一些标准的功能组成的。

import Data.List

g s = map (\x -> ([head x], length x)) . group . sort $ s

-- g = map (head &&& length) . group . sort     -- without the [...]

是标准的快速正肮脏的方式来编写的。

好了，你最初的想法是代码指向它，自由式 （某一曲调在我的头上打...）：

frequencyOfElt :: (Eq a) => [a] -> [(a,Int)]
frequencyOfElt xs = countElt (unique xs) xs     -- change the result type
  where 
    unique [] = []
    unique (x:xs) = x : unique (filter (/= x) xs)  

    countElt ref target =   -- Code it Point-Free Style  (your original idea)
      zip 
        ref $               -- your original type would need (map (:[]) ref) here
        map length $
          zipWith ($)       -- ((filter . (==)) c) === (filter (== c))
            (zipWith ($) (repeat (filter . (==))) ref)  
            (repeat target)

我在这里改变了类型比较合理[a] -> [(a,Int)] BTW。注意

zipWith ($) fs (repeat z) === map ($ z) fs
zipWith ($) (repeat f) zs === map (f $) zs === map f zs

因此代码可以简化为

    countElt ref target =  
      zip 
        ref $              
        map length $
          map ($ target)      
            (zipWith ($) (repeat (filter . (==))) ref)

然后

    countElt ref target =  
      zip 
        ref $              
        map length $
          map ($ target) $
            map (filter . (==)) ref

但map f $ map g xs === map (fg) xs ，所以

    countElt ref target =  
      zip 
        ref $              
        map (length . ($ target) . filter . (==)) ref      -- (1)

这是一个更清楚一点（对我的口味），与列表理解写的，

    countElt ref target =  
        [ (c, (length . ($ target) . filter . (==)) c) | c <- ref] 
     == [ (c,  length ( ($ target) ( filter (== c))))  | c <- ref]     
     == [ (c,  length $ filter (== c) target)          | c <- ref]

这给了我们一个想法，重新写（1）进一步为

    countElt ref target =  
      zip <*> map (length . (`filter` target) . (==)) $ ref

但这种痴迷与自由点，代码变得毫无意义在这里。

所以，要回读列表理解，使用标准的nub功能，就相当于你的unique ，你的想法变成

import Data.List

frequencyOfElt xs = [ (c, length $ filter (== c) xs) | c <- nub xs]

该算法实际上是二次（ ~ n^2 ），因此它比上面这是由占主导地位的第一个版本的差sort即是linearithmic（ ~ n log(n)

此代码虽然可以用等价转换的原则进一步处理：

  = [ (c, length . filter (== c) $ sort xs) | c <- nub xs]

......因为在列表中搜索相同列表中的搜索，排序。在这里做更多的工作 - 将它还清..

  = [ (c, length . filter (== c) $ sort xs) | (c:_) <- group $ sort xs]

... 对？但现在， group已经通过分组它们(==)所以没有必要为filter调用重复已经完成的工作group ：

  = [ (c, length . get c . group $ sort xs) | (c:_) <- group $ sort xs]
            where get c gs = fromJust . find ((== c).head) $ gs

  = [ (c, length g) | g@(c:_) <- group $ sort xs]

  = [ (head g, length g) | g <- group (sort xs)]

  = (map (head &&& length) . group . sort) xs

不是吗？这里，它就是从这篇文章的开头处具有相同linearithmic算法，通过分解出其隐藏的共同计算，使它们可重用和代码简化您的代码实际上的。

Answer 2:

使用多重集-0.1 ：

import Data.Multiset

freq = toOccurList . fromList