0

我想打印那些在列表中多次出现的元素。你能告诉我我该怎么做吗？我是haskell的新手。

例如，如果我有 [1,2,3,3,2,4,5,6,5] 我只想得到 [2,3,5] 因为这些是列表中的重复元素。

4

3 回答 3

2

Data.Map.Lazy并且Data.Map.Strict托管了许多用于构建地图的有趣函数（关联地图、字典，无论您想如何称呼它们）。其中之一是fromListWith

fromListWith :: Ord k => (a -> a -> a) -> [(k, a)] -> Map k a

您想要构建的是一张地图，它会告诉您输入列表中的每个值出现的频率。值将是映射的键（类型k），它们的计数将是与键关联的值（类型a）。您可以为此使用以下表达式：

fromListWith (+) . map (\x -> (x, 1))

首先，列表中的所有值都放入一个元组中，计数为 1。然后，fromListWith从列表中构建一个地图；如果一个键已经存在，它会使用 计算一个新的计数(+)。

完成此操作后，您只对多次出现的元素感兴趣。为此，您可以使用filter (> 1)from Data.Map。

最后，您只想知道地图中保留的所有键。为此使用该功能keys。

最后，您将获得以下模块：

import qualified Data.Map.Strict as M

findDuplicates :: (Ord a) => [a] -> [a]
findDuplicates
    = M.keys
    . M.filter (> 1)
    . M.fromListWith (+)
    . map (\x -> (x, 1 :: Integer))

导入某些包（如Data.Mapqualified）是一种常见的做法，以避免模块之间的名称冲突（例如filter，fromData.Map和一个 fromPrelude非常不同）。在这种情况下，最好选择Data.Map.Strict; 见顶部的解释Data.Map。

这种方法的复杂度应该是O(n log n)。

我认为可以通过使用布尔标志来优化它以指示该值是重复的。然而，结果却慢了大约 20%。

于 2013-09-08T15:46:18.693 回答
2

另一种解决方案：首先对列表进行排序，然后对相等的元素进行分组，并只取出现多次的元素：

>>> :m + Data.Maybe Data.List
>>> let xs = [1..100000] ++ [8,18..100] ++ [10,132,235]
>>> let safeSnd = listToMaybe . drop 1
>>> mapMaybe safeSnd $ group $ sort xs
[8,10,18,28,38,48,58,68,78,88,98,132,235]

group $ sort xs是一个列表列表，其中每个列表包含所有相等的元素。

mapMaybe safe2nd仅返回那些具有第二个元素的列表（= 原始元素在原始列表中多次出现）。

这种方法应该比 using 更快nub，尤其是对于大型列表。

于 2013-09-08T13:17:57.753 回答
1

您基本上是在寻找不唯一的元素列表，或者换句话说，原始列表和唯一元素列表之间的差异。在代码中：

xs \\ (nub xs)

如果您不想在结果列表中有重复项，则需要nub再次调用：

nub $ xs \\ (nub xs)
于 2013-09-08T09:32:57.193 回答