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的相等性)也会很好
这就是为什么例如:Counting unique elements in a list没有解决问题 – 所有答案都涉及排序或遍历整个列表以查找所有元素的计数.
问题是:如何在Haskell中正确有效地完成它?
import qualified Data.IntTrie as IntTrie import Data.List (foldl') import Control.Applicative
计算每个元素.这遍历列表一次,用结果(O(m log d))构建一个trie,然后返回一个在trie中查找结果的函数(运行时间为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的值转换为整数,以便在trie中对它们进行索引. Enum实例是你假设a是一个小的有限集的证据的一部分(Bounded将是另一部分,但见下文).
然后寻找独特的.
uniques :: (Eq a, Enum a) => [a] -> [a] -> [a] uniques dom xs = filter (\x -> cts x == 1) dom where cts = counts xs
此函数将第一个参数作为整个域的枚举.我们可能需要一个有界约束并使用[minBound..maxBound]代替,这在语义上很吸引我,因为有限的本质上是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)才能从中获取任何信息,因为它必须遍历整个列表才能构建表(你必须一直到列表的末尾才能看到元素是否是反复,所以你不能比这更好).