查找唯一(仅发生一次)元素haskell

Question

我需要一个函数,它接受一个列表并返回唯一元素(如果存在)或[]如果它不存在.如果存在许多独特元素,则应该返回第一个元素(不浪费时间去寻找其他元素).另外我知道列表中的所有元素都来自(小而且已知)集A.例如,这个函数为Ints做了工作:

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中正确有效地完成它？

Answer 1

好的,线性时间,来自有限域.运行时间为O((m + d)log d),其中m是列表的大小,d是域的大小,当d是固定的时,它是线性的.我的计划是使用集合的元素作为trie的键,将计数作为值,然后通过trie查看计数为1的元素.

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

此函数将第一个参数作为整个域的枚举.我们可能需要一个Bounded a约束并使用[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)才能从中获取任何信息,因为它必须遍历整个列表才能构建表(你必须一直到列表的末尾才能看到元素是否是反复,所以你不能比这更好).

Answer 2

真的没有办法有效地做到这一点Eq.您需要使用一些效率低得多的方法来构建相等元素的组,并且您无法知道在不扫描整个列表的情况下只存在一个特定元素.

另外,请注意,为了避免无用的比较,您需要一种检查以查看之前是否遇到过元素的方法,并且唯一的方法是获得已知多次出现的元素列表,并且检查当前元素是否在该列表中的方法是......比较它与每个元素的相等性.

如果你想让它比O更快(更糟糕的是),你需要这个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.如果它到达带有结果的列表末尾,则返回结果列表前面的那个.

否则,它会检查下一个输入元素:如果它不是候选者,则忽略它并继续.如果它在结果列表中我们已经看过两次,那么将其从结果和候选列表中删除并继续.否则,将其添加到结果中并继续.

不幸的是,这仍然需要扫描整个列表以查找单个结果,因为这是确保它实际上唯一的唯一方法.