计算列表中的唯一元素

是否有标准高阶函数的简单组合来计算列表中的唯一元素？计算列表中的唯一元素

例如，对于

[1, 1, 4, 0, 4, 4]

结果会是这样的

[(1,2), (4,3), (0,1)]

是为了重要吗？如果是这样的命令？第一次出现的次序？ – sepp2k 2010-09-14 16:53:33

如果顺序并不重要工作的：

map (\[email protected](x:_) -> (x, length xs)) . group . sort

group . sort会给你列出的清单在那里所有相互相等的元素被分组到相同的子列表中（没有吸引子）吨，只有连续相等的元素将被分组在一起）。 map然后将每个子列表变成一个(element, lengthOfSublist) -tuple。

如果要按第一次出现的顺序排序，可以在排序前使用zip向每个元素添加索引，然后在分组后，再次按该索引排序，然后删除索引。

2010-09-14 16:58:23 sepp2k

排序可能是非常昂贵的大名单。使用KennyTM或sdcwc的解决方案来提高性能可能会更好。 – GeneralBecos 2013-05-07 17:58:09

@GeneralBecos为什么排序比创建地图要慢？两者都是'O（n log n）'。 – sepp2k 2013-05-07 18:01:25

由于假定您正在进行频率分布，因此只有最差情况下的元素数量才会与列表中元素的数量相同。在更常见的情况下，分布中元素的数量将会更小。因此，平均而言，地图将优于此类。 – GeneralBecos 2013-05-07 18:07:01

最简单的方法是将项目按顺序排序，使用“group”将它们放入相同元素的子列表中，然后对每个子列表中的项目进行计数。

map (\xs -> (head xs, length xs)) . group . sort

2010-09-14 16:59:12

通过，你可以写的方式'\ XS - >（头XS，长度XS）''作为头&&& length'，使用Control.Arrow模块。 – sdcvvc 2010-09-15 14:09:41

如果列表中只包含整数，你也可以使用

import qualified Data.IntMap as I 

countElems1 :: [Int] -> [(Int, Int)] 
countElems1 = I.toList . foldr (\k -> I.insertWith (+) k 1) I.empty

（但要记住与优化编译，否则这将是比group . sort方法要慢2倍。随着-O2是稍快14％）。

您还可以使用的multiset packages这使得作为

简单的一个功能

import qualified Math.Combinatorics.Multiset as S 
countElems4 = S.toCounts . S.fromList

但效率较低。

以上所有解决方案均忽略原始顺序。

2010-09-14 20:39:43 kennytm

这还没有将近期速度改进容器图书馆，我敢打赌。 – 2010-09-15 00:41:34

你在说什么只是run length encoding在排序的数据：免费的在线预订真实世界哈斯克尔有一个great example of this。在通过runLengthEncoder之前，您需要对列表进行排序。

2010-09-15 00:33:08

这是*不* RLE。RLE会给'[（1,2），（4,1 。），（0,1），（4,2）]' – kennytm 2010-09-15 07:00:24

@KennyTM请注意，我说：“对排序的数据”所以不太RLE但几乎与排序输入我觉得是。不是吗？ – 2010-09-15 07:16:32

使用Data.Map和元组部分：

count = Map.fromListWith (+) . map (, 1)

（添加Map.toList如果你需要一个列表。）

2010-09-15 14:08:01 sdcvvc

回答