如何使用 Haskell 对列表中的相似项目进行分组? [英] How to group similar items in a list using Haskell?

问题描述

给定一个像这样的元组列表:

Given a list of tuples like this:

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

如何对 dic 的项目进行分组，从而得到一个列表 grp where,

How to group items of dic resulting in a list grp where,

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

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

I'm actually a newcomer to Haskell...and seems to be falling in love with it..
Using group or groupBy in Data.List will only group similar adjacent items in a list. I wrote an inefficient function for this, but it results in memory failures as I need to process a very large coded string list. Hope you would help me find a more efficient way.

推荐答案

这是我的解决方案:

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 对列表进行排序:

This works by first sorting the list with 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 通过关联的键对列表元素进行分组:

then grouping the list elements by the associated key with 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 将分组的项目转换为元组:

and then transforming the grouped items to tuples with 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"])]

这篇关于如何使用 Haskell 对列表中的相似项目进行分组?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！