list Haskell 列表中的唯一元素
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/3098391/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
unique elements in a haskell list
提问by muhmuhten
okay, this is probably going to be in the prelude, but: is there a standard library function for finding the unique elements in a list? my (re)implementation, for clarification, is:
好的，这可能是前奏，但是：是否有标准库函数用于查找列表中的唯一元素？为了澄清起见，我的（重新）实施是：
has :: (Eq a) => [a] -> a -> Bool
has [] _ = False
has (x:xs) a
| x == a = True
| otherwise = has xs a
unique :: (Eq a) => [a] -> [a]
unique [] = []
unique (x:xs)
| has xs x = unique xs
| otherwise = x : unique xs
回答by Artelius
回答by Yitz
The nubfunction from Data.List(no, it's actually not in the Prelude) definitely does something like what you want, but it is not quite the same as your uniquefunction. They both preserve the original order of the elements, but uniqueretains the last
occurrence of each element, while nubretains the first occurrence.
在nub从功能Data.List（不，它实际上不是在前奏）绝对不会像你想要什么，但它并不像你完全一样unique的功能。它们都保留元素的原始顺序，但unique保留每个元素的最后一次出现，同时nub保留第一次出现。
You can do this to make nubact exactly like unique, if that's important (though I have a feeling it's not):
如果这很重要（尽管我觉得它不是），您可以这样做以使nub行为完全像unique：
unique = reverse . nub . reverse
Also, nubis only good for small lists.
Its complexity is quadratic, so it starts to get slow if your list can contain hundreds of elements.
此外，nub仅适用于小型列表。它的复杂性是二次的，所以如果你的列表可以包含数百个元素，它就会开始变慢。
If you limit your types to types having an Ord instance, you can make it scale better.
This variation on nubstill preserves the order of the list elements, but its complexity is O(n * log n):
如果您将类型限制为具有 Ord 实例的类型，则可以使其更好地扩展。这种变化nub仍然保留了列表元素的顺序，但它的复杂性是O(n * log n)：
import qualified Data.Set as Set
nubOrd :: Ord a => [a] -> [a]
nubOrd xs = go Set.empty xs where
go s (x:xs)
| x `Set.member` s = go s xs
| otherwise = x : go (Set.insert x s) xs
go _ _ = []
In fact, it has been proposedto add nubOrdto Data.Set.
事实上，已经有人提议添加nubOrd到Data.Set.
回答by Daniel Patru
import Data.Set (toList, fromList)
uniquify lst = toList $ fromList lst
回答by Adam Grant
I think that unique should return a list of elements that only appear once in the original list; that is, any elements of the orginal list that appear more than once should not be included in the result.
我认为 unique 应该返回一个在原始列表中只出现一次的元素列表；也就是说，原始列表中出现多次的任何元素都不应包含在结果中。
May I suggest an alternative definition, unique_alt:
我可以建议一个替代定义，unique_alt：
unique_alt :: [Int] -> [Int]
unique_alt [] = []
unique_alt (x:xs)
| elem x ( unique_alt xs ) = [ y | y <- ( unique_alt xs ), y /= x ]
| otherwise = x : ( unique_alt xs )
Here are some examples that highlight the differences between unique_alt and unqiue:
以下是一些突出显示 unique_alt 和 unqiue 之间差异的示例：
unique [1,2,1] = [2,1]
unique_alt [1,2,1] = [2]
unique [1,2,1,2] = [1,2]
unique_alt [1,2,1,2] = []
unique [4,2,1,3,2,3] = [4,1,2,3]
unique_alt [4,2,1,3,2,3] = [4,1]
回答by Craig Norton
I think this would do it.
我认为这会做到。
unique [] = []
unique (x:xs) = x:unique (filter ((/=) x) xs)
回答by Juan Kujarchi
Another way to remove duplicates:
删除重复项的另一种方法：
unique :: [Int] -> [Int]
unique xs = [x | (x,y) <- zip xs [0..], x `notElem` (take y xs)]
回答by Manuel
Algorithm in Haskell to create a unique list:
Haskell 中创建唯一列表的算法：
data Foo = Foo { id_ :: Int
, name_ :: String
} deriving (Show)
alldata = [ Foo 1 "Name"
, Foo 2 "Name"
, Foo 3 "Karl"
, Foo 4 "Karl"
, Foo 5 "Karl"
, Foo 7 "Tim"
, Foo 8 "Tim"
, Foo 9 "Gaby"
, Foo 9 "Name"
]
isolate :: [Foo] -> [Foo]
isolate [] = []
isolate (x:xs) = (fst f) : isolate (snd f)
where
f = foldl helper (x,[]) xs
helper (a,b) y = if name_ x == name_ y
then if id_ x >= id_ y
then (x,b)
else (y,b)
else (a,y:b)
main :: IO ()
main = mapM_ (putStrLn . show) (isolate alldata)
Output:
输出：
Foo {id_ = 9, name_ = "Name"}
Foo {id_ = 9, name_ = "Gaby"}
Foo {id_ = 5, name_ = "Karl"}
Foo {id_ = 8, name_ = "Tim"}
