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

本文介绍了如何使用 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"])]