計算列表中的唯一元素

是否有標準高階函數的簡單組合來計算列表中的唯一元素？計算列表中的唯一元素

例如，對於

[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

回答