Haskell 中是否有一个函数可以接收任何数据类型的列表（特别是 a String）并检查列表中是否有重复的元素，即 ? 中是否有重复的字母String？
问问题
1228 次
4 回答
8
nub来自Data.List模块的功能
nub :: (Eq a) => [a] -> [a]
删除已在列表中看到的重复项，否则保留顺序。
ghci> nub [1,3,5,3,6,5]
[1,3,5,6]
您可以使用此函数将您正在寻找的函数编写为简单的单行。Eq由于惰性，它也与仅使用约束时一样高效！（不过，如果你需要，你可以做得更好Ord）
于 2013-10-07T17:01:35.657 回答
4
这是更高级的治疗方法。考虑到懒惰，到目前为止的所有答案（包括我的另一个答案）都没有达到最佳效果。他们来了：
import Data.List (nub, group, sort)
hasDup_nub, hasDup_any :: (Eq a) => [a] -> Bool
hasDup_sort :: (Ord a) => [a] -> Bool
hasDup_nub xs = nub xs /= xs
hasDup_any [] = False
hasDup_any (x:xs) = any (x ==) xs || hasDup_any xs
hasDup_sort = any ((> 1) . length) . group . sort
一个很好的启发式检查某个东西是否表现得很好 lazily - 也就是说，它是否会在尽可能少地评估的同时给出答案 - 看看它在无限列表上的工作情况如何。我们不能指望任何人hasDup在 上给出答案hasDup [1,2..]，因为从未出现过重复，但我们从不评估整个列表，因此无法判断将来是否会有一个。但是，hasDup [1,1..]肯定应该返回True——前两个元素甚至是相同的。让我们看看他们的表现：
>>> hasDup_nub [1,1..]
^CInterrupted.
>>> hasDup_any [1,1..]
True
>>> hasDup_sort [1,1..]
^CInterrupted.
nub [1,1..]是[1（如果你允许我这样写——也就是说，如果你尝试评估更多元素，它是一个后跟无限循环），所以在检查列表是否相等时，我们检查第二个元素是否是1，我们进入一个无限循环。 sort [1,1..]只是简单的旧底部（另一种说法是无限循环），所以我们永远不会从中获得任何信息。 hasDup_any没问题，因为它会根据列表的其余部分检查第一个元素。但它很容易被挫败：
>>> hasDup_any (1:[2,2..])
^CInterrupted.
我们在尝试评估时陷入困境any (1 ==) [2,2..]，因为我们永远找不到 a 1，但我们不知道是否只需要继续寻找更远的地方。
在懒惰的情况下，这三者的表现确实不同。这是hasDup_nub其他人不返回时返回的地方：
>>> hasDup_nub (1:2:2:[3,3..])
True
那是因为nub (1:2:2:[3,3..]) = [1,2,3 （在我的无限循环符号中），这足以说明它不等于，[1,2,2,3,3,3..]因为它们在第三个元素上不同。
hasDup_sort是最严格的——当其他两个不返回答案时，它也不会。
但是，@Satvik 的回答指出它hasNub_sort比其他两个具有更好的复杂性。它的渐近复杂度是O(n log n)，而其他两个是O(n^2)。
事实证明，有一个非常简单的解决方案，它具有hasNub_sort' 的渐近复杂性，并且比任何其他解决方案都具有更好的严格性。我们只是在列表中咀嚼，记录到目前为止我们所看到的，如果我们遇到我们已经看到的元素，则返回。如果我们使用 aData.Set来跟踪我们所看到的内容，那么针对该集合的插入和测试是O(log n)时间，我们会得到一个O(n log n)的解决方案。
import qualified Data.Set as Set
hasDup_set :: (Ord a) => [a] -> Bool
hasDup_set = go Set.empty
where
go seen [] = False
go seen (x:xs)
| x `Set.member` seen = True
| otherwise = go (Set.insert x seen) xs
到目前为止，它对任何无限测试用例都没有问题：
>>> hasDup_set [1,1..]
True
>>> hasDup_set (1:[2,2..])
True
>>> hasDup_set (1:2:2:[3,3..])
True
当然，如果你给它一个没有重复的无限列表，它仍然无法分辨。没有可计算的函数可以（同时仍然尊重引用透明度）：
>>> hasDup_set [1,2..]
^CInterrupted.
我相信hasDup_set在渐近复杂性和惰性方面都可以做到最好*（但我绝对愿意接受挑战）。幸运的是，可以同时获得它们——有时你必须做出重要的权衡。
*** 不使用unamb，往往可以达到更大程度的懒惰。我没有讨论过unamb，因为这对我来说很难，而且我还没有（据我所知也没有人）想出一个有效使用它的好方法。 请参阅此处进行尝试，以及它可以变得多么复杂和微妙的示例。
于 2013-10-07T17:42:22.193 回答
2
自己写也不难。一个天真的解决方案
import Data.List
isRepeat :: Ord a => [a] -> Bool
isRepeat = any ((>1) . length) . group . sort
Eq可以仅使用（按照@luqui的建议使用）来编写解决方案nub，但这至少是O（n ^ 2）（我可能错了）。使用Ord约束可以让您灵活地以较低的复杂性进行操作。
正如@luqui 所指出的，上述解决方案不够懒惰，无法处理无限列表。这是他指出的解决方案中最快的解决方案之一。似乎使用 Set 版本会给你两全其美。
以下是基准测试结果。
warming up
estimating clock resolution...
mean is 1.639027 us (320001 iterations)
found 2846 outliers among 319999 samples (0.9%)
1988 (0.6%) high severe
estimating cost of a clock call...
mean is 43.37523 ns (12 iterations)![enter image description here][1]
found 2 outliers among 12 samples (16.7%)
1 (8.3%) high mild
1 (8.3%) high severe
benchmarking Repeats in a list/Repeat with Sort
mean: 546.5002 us, lb 543.3960 us, ub 552.4869 us, ci 0.950
std dev: 21.33737 us, lb 12.23079 us, ub 35.02675 us, ci 0.950
found 17 outliers among 100 samples (17.0%)
6 (6.0%) high mild
11 (11.0%) high severe
variance introduced by outliers: 35.597%
variance is moderately inflated by outliers
benchmarking Repeats in a list/Repeat with set
mean: 585.5344 us, lb 582.7982 us, ub 589.2482 us, ci 0.950
std dev: 16.17934 us, lb 12.98695 us, ub 20.36634 us, ci 0.950
found 14 outliers among 100 samples (14.0%)
10 (10.0%) high mild
4 (4.0%) high severe
variance introduced by outliers: 21.917%
variance is moderately inflated by outliers
benchmarking Repeats in a list/Repeat with nub
mean: 10.24364 ms, lb 10.12385 ms, ub 10.40203 ms, ci 0.950
std dev: 700.2262 us, lb 561.3143 us, ub 851.5999 us, ci 0.950
found 17 outliers among 100 samples (17.0%)
2 (2.0%) high mild
15 (15.0%) high severe
variance introduced by outliers: 63.587%
variance is severely inflated by outliers
benchmarking Repeats in a list/Repeat with any
mean: 6.796171 ms, lb 6.712188 ms, ub 6.941347 ms, ci 0.950
std dev: 552.0155 us, lb 380.1686 us, ub 859.1697 us, ci 0.950
found 13 outliers among 100 samples (13.0%)
4 (4.0%) high mild
9 (9.0%) high severe
variance introduced by outliers: 71.738%
variance is severely inflated by outliers
x 轴以 ms 为单位。
于 2013-10-07T17:02:08.453 回答
1
当发现重复时，此解决方案将短路。我已经包含了完整性的any定义。(||)Prelude
import Prelude hiding (any, (||))
x,y :: [Char]
x = "hello"
y = "helo"
main :: IO ()
main = mapM_ print [hasDupe x, hasDupe y]
hasDupe :: Eq a => [a] -> Bool
hasDupe [] = False
hasDupe (x:xs) = any (==x) xs || hasDupe xs
any :: (a -> Bool) -> [a] -> Bool
any f [] = False
any f (x:xs) = f x || any f xs
(||) :: Bool -> Bool -> Bool
True || _ = True
False || x = x
于 2013-10-07T17:10:01.477 回答