在Haskell中完全消除重复项

Question

我有这个代码,但它没有完全做我想要的,我拿了一个元组列表;

[(3,2),(1,2),(1,3),(1,2),(4,3),(3,2),(1,2)]

并给出

[(1,3),(4,3),(3,2),(1,2)]

但我希望它给予

[(1,3),(4,3)]

我哪里做错了？提前致谢.

eliminate :: [(Int,Int)] -> [(Int,Int)]
eliminate [] = []
eliminate (x:xs)
    | isTheSame xs x  = eliminate xs
    | otherwise       = x : eliminate xs


isTheSame :: [(Int,Int)] -> (Int,Int) -> Bool
isTheSame [] _ = False
isTheSame (x:xs) a
    | (fst x) == (fst a) && (snd x) == (snd a)  = True
    | otherwise                 = isTheSame xs a

Answer 1

代码几乎是正确的.只需改变这一行

    | isTheSame xs x  = eliminate xs

至

    | isTheSame xs x  = eliminate $ filter (/=x) xs   

原因是如果x包含在内,则要xs删除所有出现的内容x.

也就是说,代码示例中有一些部分可以更优雅地表达:

• (fst x) == (fst a) && (snd x) == (snd a) 是相同的 x == a
• isTheSame是相同的elem,只是反驳了它的论点

因此,我们可以表达这样的函数eliminate:

eliminate [] = []
eliminate (x:xs)
  | x `elem` xs = eliminate $ filter (/=x) xs
  | otherwise = x : eliminate xs      

Answer 2

这应该这样做:

-- all possibilities of picking one elt from a domain
pick :: [a] -> [([a], a)]
pick []     = [] 
pick (x:xs) = (xs,x) : [ (x:dom,y) | (dom,y) <- pick xs]

unique xs = [x | (xs,x) <- pick xs, not (elem x xs)]

测试:

*Main Data.List> unique [(3,2),(1,2),(1,3),(1,2),(4,3),(3,2),(1,2)]
[(1,3),(4,3)]

更多这里和拆分列表中的可能元组列表

在Landei的带领下,这是一个简短的版本(虽然它将返回其结果排序):

import Data.List

unique xs = [x | [x] <- group . sort $ xs]