11

我尝试编写一个程序来计算列表中每个元素的频率。

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

您可以在以下链接中查看我的代码： http: //codepad.org/nyIECIT2 在此代码中，唯一函数的输出将是这样的

     In: "aabbcabb"
     Out: "abc"

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

    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" 和 target="aabbaacc" 那么

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

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

我假设一些逻辑错误在于 [(=='a'),(==',b'),(==',c')] 这里..

4

2 回答 2

22

您没有说是否要自己编写它，或者是否可以从一些标准函数组合它。

import Data.List

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

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

是标准的快速n脏编码方式。

好的，所以您最初的想法是编写无点样式（某些曲调在我脑海中播放...）：

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 (f.g) 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即以线性（~ 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

不是吗？在这里，与本文开头的线性算法相同，实际上是通过分解隐藏的常见计算从您的代码中派生出来的，使它们可用于重用和代码简化。

于 2012-11-22T17:18:03.260 回答
12

使用multiset-0.1：

import Data.Multiset

freq = toOccurList . fromList
于 2012-11-22T21:19:09.517 回答