Haskell:将(a，b)键-值对列表(可能包含重复的键)转换为按键分组的(a，[b])列表 [英] Haskell: converting a list of (a, b) key-value pairs (with possibly repeated keys) to a list of (a, [b]) grouped by key

问题描述

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

> 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都没有特别有用.那么:您将如何考虑这个问题? (我意识到这两个问题都是主观的，尤其是第二个问题.)

谢谢！

解决方案

编写函数时，最重要的一点是试图将应执行的操作拆分为多个单独的子任务(这些子任务通常由函数组合在一起)到底).例如，在您提出的定义中，有三个任务(按照应用顺序，即在定义中从右到左):

1. 将每对的第二个组件映射到一个单例列表(从而启用Map.fromListWith的使用)
2. 创建地图(用于合并具有相同键的条目)
3. 将其转换为列表

我想发布一个不同的解决方案(这是同时发布的Mark的精确副本；).只是为了清楚地表明，在大多数情况下，通向同一目标的途径不同.在他的定义中，您有单独的任务:

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

再次，关注点分离(模块化)是一个重要原则.只需尝试将其应用于小问题，一旦您获得了一定的经验，便能够为看似困难的问题提供出乎意料的简单解决方案.

I'm a Haskell beginner. Let's suppose I want to write a function convertKVList that takes a flat list of key-value pairs, where some of the keys might be repeated, and turns it into a mapping from keys to lists of values where all of the keys are unique. For instance, on a list of pairs of Ints, I want this behavior:

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

This seems like a common enough task that there ought to be a library function available to do what I want, but I couldn't find anything when I looked. Finally, someone suggested that I compose Map.toList with Map.fromListWith (++), and I ended up with this:

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

My question is for more experienced Haskellers and is in two parts: First, is this how you would go about it, or is there a "better" (easier to read, or more efficient, or both) way?

Second, how could I have come up with this on my own? I knew that I wanted the type to be [(a, b)] -> [(a, [b])], but putting that into Hoogle didn't turn up anything useful. And I had looked at the Data.Map docs, but neither fromListWith nor toList had jumped out as particularly helpful. So: how would you go about thinking about this problem? (I realize that both of these questions are subjective, especially the second one.)

Thanks!

解决方案

One of the most important points when writing a function, is trying to split what it should do into separate sub-tasks (which are often put together by function composition in the end). E.g., in the definition you came up with, there are three tasks (in order of application, i.e., from right to left in the definition):

1. map the 2nd component of each pair to a singleton list (thereby enabling the use of Map.fromListWith)
2. create a map (which takes care of merging entries with equal keys)
3. turn it into a list

I wanted to post a different solution (which was an exact copy of the code Mark posted in the meanwhile ;)). Just to make clear that most of the time there are different routes to the same goal. In his definition you have the separate tasks:

1. sort the list by keys
2. group the result by keys
3. turn it into a list of the desired type

Once again, separation of concerns (modularity) is an important principle. Just try to apply it to small problems and once you gained some experience you will be able to come up with surprisingly simple solutions to seemingly difficult problems.

这篇关于Haskell:将(a，b)键-值对列表(可能包含重复的键)转换为按键分组的(a，[b])列表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！