haskell列表中的独特元素

Question

好吧,这可能会出现在前奏中,但是:有没有标准的库函数来查找列表中的唯一元素？我的(重新)实施,澄清,是:

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

Answer 1

我搜索(Eq a) => [a] -> [a]上Hoogle.

第一个结果是nub(从列表中删除重复的元素).

Hoogle很棒.

Answer 2

在nub从功能Data.List(不,它实际上不是在前奏)绝对不会像你想要什么,但它并不像你完全一样unique的功能.它们都保留元素的原始顺序,但unique保留每个元素的最后一个出现,同时nub保留第一个出现的元素.

如果这很重要(尽管我感觉不是这样),你可以这样做,使nub行为完全一样unique:

unique = reverse . nub . reverse

此外,nub仅适用于小型列表.它的复杂性是二次的,所以如果你的列表可以包含数百个元素,它会开始变慢.

如果将类型限制为具有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 _ _              = []

事实上,已经提出添加nubOrd到Data.Set.

Answer 3

import Data.Set (toList, fromList)
uniquify lst = toList $ fromList lst