首頁猿問如何使用Haskell對列表中的類...

如何使用Haskell對列表中的類似項進行分組？

源碼算法與數(shù)據(jù)結(jié)構(gòu)

30秒到達戰(zhàn)場 2019-08-23 09:33:56

如何使用Haskell對列表中的類似項進行分組？給出一個像這樣的元組列表：dic = [(1,"aa"),(1,"cc"),(2,"aa"),(3,"ff"),(3,"gg"),(1,"bb")]如何對列表grp的dic項進行分組，其中，grp = [(1,["aa","bb","cc"]), (2, ["aa"]), (3, ["ff","gg"])]我實際上是Haskell的新手......并且似乎愛上了它。在Data.List中使用group或groupBy只會對列表中相似的相鄰項進行分組。我為此編寫了一個低效的函數(shù)，但由于我需要處理一個非常大的編碼字符串列表，因此會導(dǎo)致內(nèi)存故障。希望你能幫我找到更有效的方法。

查看完整描述

3 回答

牧羊人nacy

TA貢獻1862條經(jīng)驗獲得超7個贊

這是我的解決方案：

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")]

然后按相關(guān)鍵對列表元素進行分組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")]]

然后將分組的項目轉(zhuǎn)換為元組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"])]

反對回復(fù) 2019-08-23

溫溫醬

TA貢獻1752條經(jīng)驗獲得超4個贊

盡可能重用庫代碼。

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"])]

反對回復(fù) 2019-08-23

子衿沉夜

TA貢獻1828條經(jīng)驗獲得超3個贊

您也可以使用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"])]

反對回復(fù) 2019-08-23