实现一个函数来计算列表中每个元素的频率 [英] 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)] 顺便说一句.请注意，

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.

所以回到可读列表推导式，使用标准的nub函数，相当于你的unique，你的想法变成>

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屋！