haskell列表中的独特元素 [英] unique elements in a haskell list

问题描述

好吧，这可能会成为序幕，但是：是否有标准的库函数用于查找列表中的独特元素？我的（重新）实施，澄清，是：

  has ::（Eq a）=> [a]  - > a  - > Bool 
 has [] _ = False 
 has（x：xs）a 
 | x == a =真
 |否则=具有xs a 
 
 unique ::（等式a）=> [a]  - > [a] 
 unique [] = [] 
 unique（x：xs）
 |有xs x =唯一的xs 
 |否则= x：唯一xs 
  

解决方案 nub 函数来自 Data.List （不，它实际上不在Prelude中）肯定会做你喜欢的事情，但它不是与您的独特功能非常相似。它们都保留了元素的原始顺序，但是 unique 保留了每个元素的最后
出现次数，而 nub nub 的行为与独特的，如果这很重要的话（尽管我觉得它不是）：

  unique = reverse 。结节。反向
  

此外， nub 仅适用于小名单。
它的复杂性是二次的，所以如果列表可以包含数百个元素，它会变得很慢。

如果您将类型限制为具有Ord实例的类型，你可以让它更好地扩展。
nub 上的这种变化仍然保留了列表元素的顺序，但其复杂性为 O（n * log n）
pre $ 将限定数据集合导入集合

nubOrd :: Ord a = > [a] - > [a]
nubOrd xs = go Set.empty xs其中
go s（x：xs）
| x`Set.member` s = go s xs
|否则= x：go（Set.insert xs）xs
go _ _ = []


实际上，已经建议添加 nubOrd 至 Data.Set 。

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

解决方案

The nub function 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 unique function. They both preserve the original order of the elements, but unique retains the last occurrence of each element, while nub retains the first occurrence.

You can do this to make nub act exactly like unique, if that's important (though I have a feeling it's not):

unique = reverse . nub . reverse

Also, nub is only good for small lists. Its complexity is quadratic, so it starts to get slow if your list can contain hundreds of elements.

If you limit your types to types having an Ord instance, you can make it scale better. This variation on nub still preserves the order of the list elements, but its complexity is 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 proposed to add nubOrd to Data.Set.

这篇关于haskell列表中的独特元素的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！