list - 从元组列表中删除反向重复项

Question

所以基本上我有一个元组列表 [(a,b)]，我必须从中进行一些过滤。一项工作是删除倒置重复项，这样如果 (a,b) 和 (b,a) 存在于列表中，我只取其中的一个实例。但是列表理解并不是很有帮助。如何有效地解决这个问题？

谢谢

Answer 1

也许一种有效的方法 (O(n log(n))) 是使用 Set 跟踪已经添加的元组(及其反转)。 :

import qualified Data.Set as Set                                                                                                                                                                        

removeDups' :: Ord a => [(a, a)] -> Set.Set (a, a) -> [(a, a)]
removeDups' [] _ = []
removeDups' ((a, b):tl) s | (a, b) `Set.member` s = removeDups' tl s
removeDups' ((a, b):tl) s | (b, a) `Set.member` s = removeDups' tl s
removeDups' ((a, b):tl) s = ((a, b):rest) where
    s' = Set.insert (a, b) s
    rest = removeDups' tl s'

removeDups :: Ord a => [(a, a)] -> [(a, a)]
removeDups l = removeDups' l (Set.fromList [])

函数 removeDups 使用列表和一个空集调用辅助函数 removeDups'。对于每一对，如果它或其逆在集合中，则通过；否则，将它和它的逆相加，并处理尾部。\

复杂度为 O(n log(n))，因为在每一步中集合的大小至多为 n 线性。

---

示例

...

main = do
    putStrLn $ show $ removeDups [(1, 2), (1, 3), (2, 1)]

和

$ ghc ord.hs && ./ord
[1 of 1] Compiling Main             ( ord.hs, ord.o )
Linking ord ...
[(1,2),(1,3)]