实现一个功能来计算列表中每个元素的频率 [英] Implement a function to count frequency of each element in a list

问题描述

我尝试编写一个程序，该程序将计算列表中每个元素的频率.

I try to write a program which will count the frequency of each element in a list.

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

您可以在以下链接中查看我的代码: http://codepad.org/nyIECIT2 在这段代码中，唯一函数的输出将如下所示:

You can view my code in the following link: http://codepad.org/nyIECIT2 In this code the output of unique function would be like this

     In: "aabbcabb"
     Out: "abc"

使用unique的输出，我们将计算目标列表的出现频率.您还可以在此处查看代码:

Using the output of unique we wil count the frequency of the target list. You can see the code here also:

    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中，还显示了其他类型的错误

But in ghci 6.13 other type of error are showing also

很少有人问我使用[[=='a')，(=='，b')，(=='，c')]的目的是什么.我的期望:如果ref ="abc"和target ="aabbaacc"然后

Few asked me what is the purpose of using [(=='a'),(==',b'),(==',c')]. What I expect: If ref="abc" and target="aabbaacc" then

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

将显示["aaaa"，"bb"，"cc"]，然后我可以在该长度上使用地图长度来获取频率在这里根据引用过滤列表我使用[[=='a')，(=='，b')，(=='，c')]

will show ["aaaa","bb","cc"] then I can use map length over this to get the frequency Here for filtering list according with the ref i use [(=='a'),(==',b'),(==',c')]

我认为这里有些逻辑错误在于[[=='a')，(=='，b')，(=='，c')].

I assume some logical error lies [(=='a'),(==',b'),(==',c')] here..

推荐答案

您没有说是要自己编写整个代码，还是可以通过某些标准函数编写它.

You didn't say whether you want to write it whole on your own, or whether it's OK to compose it from some standard functions.

import Data.List

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

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

是标准的快速除污方式.

is the standard quick-n-dirty way to code it.

好的，所以您最初的想法是将其编码为无点样式(某些音调在我的脑海中演奏...):

OK, so your original idea was to Code it Point-Free Style (certain tune playing in my head...):

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.请注意，

I've changed the type here to the more reasonable [a] -> [(a,Int)] btw. Note, that

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(f.g)xs ，所以

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

(对我而言)用列表理解写得更清楚

which is a bit clearer (for my taste) written with a list comprehension,

    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)进一步重写为

Which gives us an idea to re-write (1) further as

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

但是这种对无点代码的迷恋在这里变得毫无意义.

but this obsession with point-free code becomes pointless here.

因此，使用与您的 unique 等效的标准 nub 函数，返回到可读的列表理解，您的想法就会变成

So going back to the readable list comprehensions, using a standard nub function which is equivalent to your unique, your idea becomes

import Data.List

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

此算法实际上是二次算法(〜n ^ 2 )，因此比上面的第一个版本要差，而第一个版本由 sort 主导，即线性等式(〜n log(n)).

This algorithm is actually quadratic (~ n^2), so it is worse than the first version above which is dominated by sort i.e. is linearithmic (~ n log(n)).

尽管此代码可以通过等效转换的原理进行进一步操作:

This code though can be manipulated further by a principle of equivalent transformations:

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

...，因为在列表中搜索与在列表中搜索(排序)相同.在这里做更多的工作-会成功吗?.

... because searching in a list is the same as searching in a list, sorted. Doing more work here -- will it pay off?..

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

...对吗?但是现在， group 已经按(==)对它们进行了分组，因此不需要 filter 调用来重复已经完成的工作.组:

... right? But now, group had already grouped them by (==), so there's no need for the filter call to repeat the work already done by 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

不是吗?这就是本文开头的相同线性算法，实际上是从您的代码中派生，方法是分解出隐藏的通用计算，使它们可供重用和代码使用简化.

isn't it? And here it is, the same linearithmic algorithm from the beginning of this post, actually derived from your code by factoring out its hidden common computations, making them available for reuse and code simplification.

这篇关于实现一个功能来计算列表中每个元素的频率的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！