实现一个函数来统计列表中每个元素的频率

Question

实现一个函数来统计列表中每个元素的频率

11

我试图编写一个程序，可以统计列表中每个元素的频率。

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

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

     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"]，然后我可以对其使用map length获取频率。这里为了根据参考值过滤列表，我使用[(=='a')，(==',b')，(==',c')]。

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

- sabu

1

请将代码和错误放在您的问题中。 - Marcin

1

你的缩进有误。在同一 where 子句中的绑定必须从同一列开始。 - Daniel Fischer

2

@SaugataBose 跟着我说：“同一个 where 子句中的所有绑定必须从同一列开始。”然后比较 ans 和 unique 这两个在同一个 where 子句中的列。 - Ingo

@SaugataBose 您能解释一下您认为这个代码 map[(=='a'),(==',b'),(==',c')] 的含义是什么吗？ - Ingo

我感激你的友好努力。 - sabu

显示剩余11条评论

2个回答

12

使用multiset-0.1:

import Data.Multiset

freq = toOccurList . fromList

- Landei

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Will Ness · Accepted Answer

您没有说明是否要自己编写代码，还是可以从一些标准函数中组合。

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)]。注意，

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

不是吗？这里就是从本文开头推导出来的同样的线性对数时间复杂度算法，实际上是通过分解出隐藏的公共计算来从您的代码中“派生”出来的，使它们可供重用和简化代码。