如何使用Haskell在列表中分組相似的項目？

的 DIC

dic = [(1,"aa"),(1,"cc"),(2,"aa"),(3,"ff"),(3,"gg"),(1,"bb")]

如何將商品導致列表GRP其中，

grp = [(1,["aa","bb","cc"]), (2, ["aa"]), (3, ["ff","gg"])]

實際上，我初來乍到的Haskell。 ..似乎正在愛上它..
使用組或組在D ata.List將只在列表中分組相似的項目。我爲此編寫了一個低效率的函數，但由於需要處理非常大的編碼字符串列表，因此導致內存失敗。希望你能幫我找到更有效的方法。

來源

2012-09-13 td123

看起來像一門功課什麼的。最好是增加你的方法，並向社區詢問改進方法，而不是僅僅詢問答案。 – Satvik

對不起，我是一個新手來stackoverflow ..apologies不知道社區規則。 – td123

這裏是我的解決方案：

import Data.Function (on) 
import Data.List (sortBy, groupBy) 
import Data.Ord (comparing) 

myGroup :: (Eq a, Ord a) => [(a, b)] -> [(a, [b])] 
myGroup = map (\l -> (fst . head $ l, map snd l)) . groupBy ((==) `on` fst) 
      . sortBy (comparing fst)

這是通過先用sortBy排序列表：

[(1,"aa"),(1,"cc"),(2,"aa"),(3,"ff"),(3,"gg"),(1,"bb")]  
=> [(1,"aa"),(1,"bb"),(1,"cc"),(2,"aa"),(3,"ff"),(3,"gg")]

然後分組由相關的密鑰列表中的元素與groupBy：

[(1,"aa"),(1,"bb"),(1,"cc"),(2,"aa"),(3,"ff"),(3,"gg")] 
=> [[(1,"aa"),(1,"bb"),(1,"cc")],[(2,"aa")],[(3,"ff"),(3,"gg")]]

，然後將分組項目轉換爲t uples與map：

[[(1,"aa"),(1,"bb"),(1,"cc")],[(2,"aa")],[(3,"ff"),(3,"gg")]] 
=> [(1,["aa","bb","cc"]), (2, ["aa"]), (3, ["ff","gg"])]`)

測試：

> myGroup dic 
[(1,["aa","bb","cc"]),(2,["aa"]),(3,["ff","gg"])]

來源

2012-09-13 02:08:45

非常感謝。這真的有用。我其實是Haskell的新手，我對圖書館知之甚少。再次感謝您的聰明回答！ – td123

@ Mikhail：嘿，你確定這個工作，即使類似的鍵值不相鄰嗎？例如，如果dic = [（1，「aa」），（2，「bb」），（1，「cc」）]？結果應該是[（1，[「aa」，「cc」]），（2，「bb」）]。 – td123

^@ td123在這種情況下，您應該事先對列表進行排序。 –

如果列表中沒有的第一個元素上排序，我不認爲你可以爲O做的更好（n日誌（N））。
- 一個簡單的方法是隻sort，然後使用任何從第二部分的答案。
- 您可以從Data.Map使用類似Map k [a]的地圖來使用元組的第一個元素作爲關鍵字並繼續添加值。
- 你可以編寫自己的複雜函數，即使你所有的嘗試仍然會採取O（nlog（n））。
如果列表中的第一個元素上歸類爲是你的榜樣的話，那麼在回答鑑於@Mikhail或使用foldr相似，並有許多其他方式的任務是微不足道的東西像GROUPBY 。

用foldr的一個例子是在這裏：

grp :: Eq a => [(a,b)] -> [(a,[b])] 
    grp = foldr f [] 
    where 
     f (z,s) [] = [(z,[s])] 
     f (z,s) [email protected]((x,y):xs) | x == z = (x,s:y):xs 
          | otherwise = (z,[s]):a

來源

2012-09-13 02:16:02 Satvik

感謝您的信息......我將使用Data.Map。 – td123

您也可以使用TransformListComp擴展名，例如：

Prelude> :set -XTransformListComp 
Prelude> import GHC.Exts (groupWith, the) 
Prelude GHC.Exts> let dic = [ (1, "aa"), (1, "bb"), (1, "cc") , (2, "aa"), (3, "ff"), (3, "gg")] 
Prelude GHC.Exts> [(the key, value) | (key, value) <- dic, then group by key using groupWith] 
[(1,["aa","bb","cc"]),(2,["aa"]),(3,["ff","gg"])]

來源

2012-09-13 02:25:51

只要有可能，重用庫代碼。

import Data.Map 
sortAndGroup assocs = fromListWith (++) [(k, [v]) | (k, v) <- assocs]

嘗試一下在ghci中：

*Main> sortAndGroup [(1,"aa"),(1,"cc"),(2,"aa"),(3,"ff"),(3,"gg"),(1,"bb")] 
fromList [(1,["bb","cc","aa"]),(2,["aa"]),(3,["gg","ff"])]

來源

2012-09-13 03:23:20

真的很酷的解決方案。永遠不會想到它，但考慮到Data.Map的本質，這很有意義。 – identity

這是我的答案。我簡單地暫停了一下思考效率 - 我使用'toList。 fromListWith操作模式很多，但我想知道，從「Map」進行轉換和從「Map」進行轉換相比，手動轉換列表和進行分組的成本有多高。 –

@ChrisTaylor這個解決方案是O（n log n），這是給定約束條件下最好的希望。 –

{-# LANGUAGE TransformListComp #-} 

import GHC.Exts 
import Data.List 
import Data.Function (on) 

process :: [(Integer, String)] -> [(Integer, [String])] 
process list = [(the a, b) | let info = [ (x, y) | (x, y) <- list, then sortWith by y ], (a, b) <- info, then group by a using groupWith]

來源

2016-04-12 14:27:00

如何使用Haskell在列表中分組相似的項目？

回答

相關問題