如何使用Haskell对列表中的类似项进行分组？

Question

如何使用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只会对列表中相似的相邻项进行分组。我为此编写了一个低效的函数，但由于我需要处理一个非常大的编码字符串列表，因此会导致内存故障。希望你能帮我找到更有效的方法。

Answer 1

这是我的解决方案：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")]]然后将分组的项目转换为元组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"])]

Answer 2

尽可能重用库代码。import&nbsp;Data.Map sortAndGroup&nbsp;assocs&nbsp;=&nbsp;fromListWith&nbsp;(++)&nbsp;[(k,&nbsp;[v])&nbsp;|&nbsp;(k,&nbsp;v)&nbsp;<-&nbsp;assocs]在ghci中尝试一下：*Main>&nbsp;sortAndGroup&nbsp;[(1,"aa"),(1,"cc"),(2,"aa"),(3,"ff"),(3,"gg"),(1,"bb")]fromList&nbsp;[(1,["bb","cc","aa"]),(2,["aa"]),(3,["gg","ff"])]

Answer 3

您也可以使用TransformListComp扩展，例如：Prelude>&nbsp;:set&nbsp;-XTransformListComp&nbsp; Prelude>&nbsp;import&nbsp;GHC.Exts&nbsp;(groupWith,&nbsp;the)Prelude&nbsp;GHC.Exts>&nbsp;let&nbsp;dic&nbsp;=&nbsp;[&nbsp;(1,&nbsp;"aa"),&nbsp;(1,&nbsp;"bb"),&nbsp;(1,&nbsp;"cc")&nbsp;,&nbsp;(2,&nbsp;"aa"),&nbsp;(3,&nbsp;"ff"),&nbsp;(3,&nbsp;"gg")]Prelude&nbsp;GHC.Exts>&nbsp;[(the&nbsp;key,&nbsp;value)&nbsp;|&nbsp;(key,&nbsp;value)&nbsp;<-&nbsp;dic,&nbsp;then&nbsp;group&nbsp;by&nbsp;key&nbsp;using&nbsp;groupWith][(1,["aa","bb","cc"]),(2,["aa"]),(3,["ff","gg"])]