Haskell:将(a,b)键值对(带有可能重复的键)的列表转换为按键分组的(a,[b])列表

Question

我是Haskell的初学者.假设我想编写一个函数convertKVList,该函数采用键值对的平面列表,其中一些键可能会重复,并将其转换为从键到值列表的映射,其中所有键都是唯一的.例如,在Ints 对的列表中,我想要这样的行为:

> convertKVList [(1, 2), (1, 4), (1, 3), (2, 3)]
[(1,[3,4,2]),(2,[3])]

这似乎是一个足够普遍的任务,应该有一个库函数可以做我想要的,但是当我看时我找不到任何东西.最后,有人建议我撰写Map.toList有Map.fromListWith (++),我结束了这一点:

import Data.Map as Map (toList, fromListWith)

convertKVList :: (Ord a) => [(a, b)] -> [(a, [b])]
convertKVList ls =
  (Map.toList . Map.fromListWith (++) . map (\(x,y) -> (x,[y]))) ls

我的问题是更有经验的Haskellers,分为两部分:第一,这是你如何去做,或者是否有"更好"(更容易阅读,更有效,或两者兼而有之)的方式？

其次,我怎么能靠自己想出来呢？我知道我想要的类型[(a, b)] -> [(a, [b])],但把它放入Hoogle并没有发现任何有用的东西.而且我查看了Data.Map文档,但是既没有fromListWith也toList没有跳出来特别有帮助.那么:你会如何考虑这个问题？(我意识到这两个问题都是主观的,特别是第二个问题.)

谢谢!

Answer 1

在编写函数时,最重要的一点是尝试将它应该做的事分割成单独的子任务(最终通过函数组合将它们组合在一起).例如,在您提出的定义中,有三个任务(按应用顺序,即定义中从右到左):

1. 将每对的第二个组件映射到单个列表(从而可以使用Map.fromListWith)
2. 创建一个地图(负责用相同的键合并条目)
3. 把它变成一个列表

我想发布一个不同的解决方案(这是同时发布的代码Mark的完全副本;)).只是要明确说明大部分时间都有不同的路线达到同一目标.在他的定义中,您有不同的任务:

1. 按键排序列表
2. 按键对结果进行分组
3. 将其转换为所需类型的列表

关注点的分离(模块化)是一个重要的原则.只是尝试将它应用于小问题,一旦你获得了一些经验,你就能够为看似困难的问题提出令人惊讶的简单解决方案.

Answer 2

Hoogle不是唯一一个能够通过类型签名搜索Haskell库的搜索引擎,它绝对而且不幸地只涵盖了Hackage的一小部分.使用Hayoo搜索类型签名会[(a,b)]->[(a,[b])]带来这两种实现:

• aggregateAL
• alistCollect

关于你对问题的看法,因为在你的函数中你已经提出了更高级别的数据结构(Map),在输出中降级到更原始的关联列表是没有意义的,因为:

1. 您可以利用这些数据的大多数算法只会从获取Map输入中受益,因为它对于处理键值存储更有效,如果您发现自己仍然需要列表,您可以随时使用toList.
2. Map意味着在类型级别上没有重复键,这并不重要,因为在Haskell中,您应该始终使用类型系统进行最大限度的校样.这个原则本质上是使"如果它编译,它起作用"这句话最接近真理的说法.

换句话说,这是您的功能的正确定义:

convertKVList :: (Ord a) => [(a, b)] -> Map a [b]
convertKVList ls =
  Map.fromListWith (++) . map (\(x,y) -> (x,[y])) $ ls

对该类型签名的干扰也带来了一些已经实现的结果.

关于解决问题,这是经典:"分而治之!" .克里斯在答案中也有一些好处.

Answer 3

虽然这绝不是规范的:

import Data.List
import Data.Ord
import Data.Function (on)

convertKVList :: Ord a => [(a,b)] -> [(a,[b])]
convertKVList = map (\x -> (fst $ head x,  map snd x)) . groupBy ((==) `on` fst) . sortBy (comparing fst)

它确实具有不拉入Data.Map的优点.应该渐近相同,没有基准.我认为你可以使用Control.Arrow清理第一个块(类似于(fst.head &&& map snd)),但它显然不是很清晰.

但是不知道你是怎么做到的,除非知道它或者在#haskell中询问.