haskell - 如何使用 Haskell 对列表中的相似项目进行分组？

Question

给定这样的元组列表:

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

如何对 dic 的项目进行分组，从而生成一个列表 grp，其中，

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

我实际上是 Haskell 的新手……而且似乎爱上了它……
在 Data.List 中使用 group 或 groupBy 只会对列表中相似的相邻项目进行分组。
我为此编写了一个效率低下的函数，但它会导致内存故障，因为我需要处理一个非常大的编码字符串列表。希望您能帮助我找到更有效的方法。

Answer 1

只要有可能，重用库代码。

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

编辑 在评论中，有些人担心 (++)或 flip (++)是正确的选择。文档没有说明事物的关联方式。您可以通过实验找出答案，也可以使用 difference lists 回避整个问题:

sortAndGroup assocs = ($[]) <$> fromListWith (.) [(k, (v:)) | (k, v) <- assocs]
-- OR
sortAndGroup = fmap ($[]) . M.fromListWith (.) . map (fmap (:))

这些替代品的长度与原件的长度大致相同，但它们对我来说可读性差一些。