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

时间 2018-12-01

标签 algorithm functional-programming haskell 栏目应用数学

原文原文链接

我需要一个函数,它接受一个列表并返回唯一元素(如果存在)或[]如果它不存在.如果存在许多独特元素,它应该返回第一个(不浪费时间去寻找其他元素).
另外我知道列表中的所有元素都来自(小而且已知)集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的相等性)也会很好

这就是为什么例如：Counting unique elements in a list没有解决问题 – 所有答案都涉及排序或遍历整个列表以查找所有元素的计数.

问题是：如何在Haskell中正确有效地完成它？

好的,线性时间,来自有限域.运行时间为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

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