如何创建"计数"过滤器？

Question

我有一个对列表,我需要一个过滤器,只保留该对的第一个成员至少出现两次的元素:

someFilter :: Eq a => [(a, b)] -> [(a, b)]
someFilter   [("a",1),("a",2),("b",1)]
  `shouldBe` [("a",1),("a",2)]         -- "a" occurs in two pairs, retain both

someFilter   [("a",1),("a",2),("b",1),("b",2)]
  `shouldBe` [("a",1),("a",2),("b",1),("b",2)] -- "a" and "b" occur twice

someFilter   [("a",1),("b",2),("c",1),("d",2)]
  `shouldBe` [] -- no string occurs twice

我不确定如何实现这样的过滤器.通常filter只在元素方面起作用.怎么会写someFilter？

Answer 1

您可以首先按元组的第一个元素对元组进行分组,然后连接至少包含两个元素的组.该解决方案不是O(n ^ 2),而是强加Ord约束.

import Data.List (groupBy, sortBy)
import Data.Function (on)
import Data.Ord (comparing)

someFilter :: Ord a => [(a, b)] -> [(a, b)]
someFilter = concat
           . filter ((>= 2) . length)
           . groupBy ((==) `on` fst)
           . sortBy (comparing fst)