我需要一个函数，它接受一个列表并返回唯一元素，如果它存在或[]，如果它不存在。如果存在许多唯一元素，它应该返回第一个(而不浪费时间寻找其他元素)。此外，我知道列表中的所有元素都来自集合A(小而已知)。例如，下面的函数完成int类型的工作:
unique :: Ord a => [a] -> [a]
unique li = first $ filter ((==1).length) ((group.sort) li)
where first [] = []
first (x:xs) = x
ghci> unique [3,5,6,8,3,9,3,5,6,9,3,5,6,9,1,5,6,8,9,5,6,8,9]
ghci> [1]
然而这还不够好，因为它涉及排序(n log n)，而它可以在线性时间内完成(因为A很小)。此外，它要求列表元素的类型为Ord，而所有需要的是Eq。如果比较的数量尽可能少(即，如果我们遍历列表并遇到元素el两次，我们不测试后续元素是否与el相等)，这也会很好。
这就是为什么对列表中唯一的元素进行计数并不能解决问题——所有的答案都需要排序或遍历整个列表来找到所有元素的计数。
问题是:如何在Haskell中正确有效地做到这一点?
好的，线性时间，从有限域。运行时间为O((m + d) log d)，其中m为列表的大小，d为域的大小，当d固定时，它们是线性的。我的计划是使用集合中的元素作为树的键，将计数作为值，然后在树中查找计数为1的元素。
import qualified Data.IntTrie as IntTrie
import Data.List (foldl')
import Control.Applicative
对每个元素进行计数。它遍历列表一次，用结果(O(m log d))构建一个树，然后返回一个函数，该函数在树中查找结果(运行时间O(log d))。
counts :: (Enum a) => [a] -> (a -> Int)
counts xs = IntTrie.apply (foldl' insert (pure 0) xs) . fromEnum
where
insert t x = IntTrie.modify' (fromEnum x) (+1) t
我们使用Enum约束将a类型的值转换为整数，以便在树中索引它们。Enum实例是您假设a是一个小的有限集的一部分见证(Bounded将是另一部分，但见下文)。
然后寻找唯一的。
uniques :: (Eq a, Enum a) => [a] -> [a] -> [a]
uniques dom xs = filter (x -> cts x == 1) dom
where
cts = counts xs
该函数将整个域的枚举作为其第一个参数。我们本可以要求Bounded a约束并使用[minBound..maxBound]来代替，这在语义上对我很有吸引力，因为finite本质上是Enum + Bounded，但是非常不灵活，因为现在需要在编译时知道域。所以我会选择这个稍微难看但更灵活的变体。
uniques遍历域一次(惰性，因此head . uniques dom将只遍历需要找到的第一个唯一元素-不在列表中，而是在dom中)，对于运行查找函数的每个元素，我们已经建立了O(log d)，因此过滤器需要O(d log d)，并且构建计数表需要O(m log d)。因此，uniques在O((m + d) log d)中运行，当d固定时，它是线性的。它至少需要Ω(m log d)才能从中获得任何信息，因为它必须遍历整个列表来构建表(您必须一直遍历列表的末尾才能查看元素是否重复，所以您不能做得比这更好)。
仅使用Eq确实没有任何方法可以有效地做到这一点。您需要使用一些效率低得多的方法来构建相等元素的组，并且在不扫描整个列表的情况下，您无法知道只有一个特定元素存在。
还要注意，为了避免无用的比较，您需要一种检查方法来查看一个元素之前是否遇到过，而这样做的唯一方法是拥有一个已知多次出现的元素列表，并且检查当前元素是否在该列表中的唯一方法是…比较两者是否相等
如果你想让这个比0更快(这真的很可怕)，你需要Ord约束。
好的，根据评论中的澄清，这里有一个快速而肮脏的例子，我认为你正在寻找:
unique [] _ _ = Nothing
unique _ [] [] = Nothing
unique _ (r:_) [] = Just r
unique candidates results (x:xs)
| x `notElem` candidates = unique candidates results xs
| x `elem` results = unique (delete x candidates) (delete x results) xs
| otherwise = unique candidates (x:results) xs
第一个参数是候选元素列表，最初应该是所有可能的元素。第二个参数是可能结果的列表，它最初应该为空。第三个参数是要检查的列表。
如果没有候选项，或者到达列表末尾没有结果，则返回Nothing。如果它到达结果列表的末尾，它返回结果列表前面的那个。
否则，它检查下一个输入元素:如果它不是候选元素，它忽略它并继续。如果它在结果列表中，我们已经看到它两次，那么从结果和候选列表中删除它，然后继续。否则，将其添加到结果中并继续。
不幸的是，这仍然需要扫描整个列表来获取单个结果，因为这是确保它实际上是唯一的唯一方法。
首先，如果您的函数打算最多返回一个元素，那么几乎肯定应该使用Maybe a而不是[a]来返回结果。
其次，至少你别无选择，只能遍历整个列表:除非你查看了所有其他元素，否则你无法确定某个给定元素是否真正是唯一的。
如果你的元素不是Ord的，但只能测试Eq的质量，你真的没有比这样更好的选择:
firstUnique (x:xs)
| elem x xs = firstUnique (filter (/= x) xs)
| otherwise = Just x
firstUnique [] = Nothing
请注意，如果您不想过滤掉重复的元素，则不需要过滤掉——无论哪种方式，最坏的情况都是二次元。
编辑:
由于上述可能元素的小/已知集合，上述忽略了提前退出的可能性。然而，请注意，最坏的情况仍然需要遍历整个列表:所需要的只是这些可能的元素中至少有一个在列表中缺少…
但是，在set耗尽的情况下提供提前out的实现:
firstUnique = f [] [<small/known set of possible elements>] where
f [] [] _ = Nothing -- early out
f uniques noshows (x:xs)
| elem x uniques = f (delete x uniques) noshows xs
| elem x noshows = f (x:uniques) (delete x noshows) xs
| otherwise = f uniques noshows xs
f [] _ [] = Nothing
f (u:_) _ [] = Just u
注意，如果你的列表有不应该存在的元素(因为它们不在小/已知集合中)，它们将被上面的代码直接忽略…
正如其他人所说，如果没有任何额外的约束，您无法在不到二次元的时间内完成此操作，因为在不了解元素的情况下，您无法将它们保持在某种合理的数据结构中。
如果我们能够比较元素，一个明显的O(n log n)解决方案是先计算元素的计数，然后找到第一个count等于1的元素:
import Data.List (foldl', find)
import Data.Map (Map)
import qualified Data.Map as Map
import Data.Maybe (fromMaybe)
count :: (Ord a) => Map a Int -> a -> Int
count m x = fromMaybe 0 $ Map.lookup x m
add :: (Ord a) => Map a Int -> a -> Map a Int
add m x = Map.insertWith (+) x 1 m
uniq :: (Ord a) => [a] -> Maybe a
uniq xs = find (x -> count cs x == 1) xs
where
cs = foldl' add Map.empty xs
请注意，log n因子来自于我们需要对大小为n的Map进行操作的事实。如果列表只有k个唯一元素，那么映射的大小将最多为k，因此总体复杂度将仅为O(n log k)。
ST单子来对哈希映射执行可变操作，并且我们的元素必须是可哈希的。解决方案基本上与以前相同，只是由于在ST单子内工作而稍微复杂一点:
import Control.Monad
import Control.Monad.ST
import Data.Hashable
import qualified Data.HashTable.ST.Basic as HT
import Data.Maybe (fromMaybe)
count :: (Eq a, Hashable a) => HT.HashTable s a Int -> a -> ST s Int
count ht x = liftM (fromMaybe 0) (HT.lookup ht x)
add :: (Eq a, Hashable a) => HT.HashTable s a Int -> a -> ST s ()
add ht x = count ht x >>= HT.insert ht x . (+ 1)
uniq :: (Eq a, Hashable a) => [a] -> Maybe a
uniq xs = runST $ do
-- Count all elements into a hash table:
ht <- HT.newSized (length xs)
forM_ xs (add ht)
-- Find the first one with count 1
first (x -> liftM (== 1) (count ht x)) xs
-- Monadic variant of find which exists once an element is found.
first :: (Monad m) => (a -> m Bool) -> [a] -> m (Maybe a)
first p = f
where
f [] = return Nothing
f (x:xs') = do
b <- p x
if b then return (Just x)
else f xs'
指出:
- 如果您知道列表中只有少量不同的元素，您可以使用
HT.new而不是HT.newSized (length xs)。这将节省一些内存和一次传递xs，但在许多不同元素的情况下，哈希表将不得不调整几次。
这里有一个版本可以做到:
unique :: Eq a => [a] -> [a]
unique = select . collect []
where
collect acc [] = acc
collect acc (x : xs) = collect (insert x acc) xs
insert x [] = [[x]]
insert x (ys@(y : _) : yss)
| x == y = (x : ys) : yss
| otherwise = ys : insert x yss
select [] = []
select ([x] : _) = [x]
select ((_ : _) : xss) = select xss
因此，首先我们遍历输入列表(collect)，同时维护一个包含相等元素的桶列表，并使用insert更新。然后我们简单地选择出现在单例bucket (select)中的第一个元素。
collect中的每个访问元素，我们需要遍历bucket列表。我担心这是你将不得不为只能够将元素类型限制在Eq中而付出的代价。
像这样的东西看起来很好。
unique = fst . foldl' ((a, b) c -> if (c `elem` b)
then (a, b)
else if (c `elem` a)
then (delete c a, c:b)
else (c:a, b)) ([],[])
折叠结果元组的第一个元素包含您所期望的，一个包含唯一元素的列表。元组的第二个元素是进程记住的内存，无论元素是否已经被丢弃。
关于空间性能。
由于您的问题是设计，因此在显示结果之前，应该遍历列表的所有元素至少一次。而内部算法除了保留好值之外，还必须对丢弃值进行跟踪，但是丢弃值只会出现一次。在最坏的情况下，所需的内存量等于输入列表的大小。这个声音货物如你所说，预期的投入是很小的。
关于时间性能。
由于预期的输入很小，并且默认情况下没有排序，因此尝试将列表排序到算法中是无用的，或者在应用它之前是无用的。实际上，从静态角度来看，我们几乎可以说，将一个元素放置在其有序位置(放入元组(a,b)的子列表a和b中)所花费的时间与检查该元素是否出现在列表中所花费的时间相同。
下面是一个更好的和更明确的折叠版本。
import Data.List (foldl', delete, elem)
unique :: Eq a => [a] -> [a]
unique = fst . foldl' algorithm ([], [])
where
algorithm (result0, memory0) current =
if (current `elem` memory0)
then (result0, memory0)
else if (current`elem` result0)
then (delete current result0, memory)
else (result, memory0)
where
result = current : result0
memory = current : memory0
在嵌套的if ... then ... else ...指令中，列表result在最坏的情况下被遍历两次，这可以使用下面的帮助函数来避免。
unique' :: Eq a => [a] -> [a]
unique' = fst . foldl' algorithm ([], [])
where
algorithm (result, memory) current =
if (current `elem` memory)
then (result, memory)
else helper current result memory []
where
helper current [] [] acc = ([current], [])
helper current [] memory acc = (acc, memory)
helper current (r:rs) memory acc
| current == r = (acc ++ rs, current:memory)
| otherwise = helper current rs memory (r:acc)
但是可以像下面这样使用fold重写帮助器，这肯定更好。
helper current [] _ = ([current],[])
helper current memory result =
foldl' ((r, m) x -> if x==current
then (r, current:m)
else (current:r, m)) ([], memory) $ result