16

我是 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特别有用。那么：您将如何思考这个问题？（我意识到这两个问题都是主观的，尤其是第二个问题。）

谢谢！

4

6 回答 6

9

编写函数时最重要的一点是，尝试将它应该做的事情拆分成单独的子任务（这些子任务通常最终通过函数组合组合在一起）。例如，在您提出的定义中，有三个任务（按应用顺序，即定义中从右到左）：

  1. 将每对的第二个组件映射到一个单例列表（从而允许使用Map.fromListWith）
  2. 创建一个映射（负责合并具有相同键的条目）
  3. 把它变成一个列表

我想发布一个不同的解决方案（这是同时发布的代码 Mark 的精确副本；））。只是要明确一点，大多数时候有不同的途径可以达到同一个目标。在他的定义中，您有单独的任务：

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

再次强调，关注点分离（模块化）是一个重要原则。只需尝试将其应用于小问题，一旦您获得了一些经验，您将能够为看似困难的问题提出令人惊讶的简单解决方案。

于 2013-03-20T03:36:23.430 回答
8

虽然这绝不是规范的：

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 中询问之外，不知道您是如何得到它的。

于 2013-03-20T03:25:52.540 回答
8

Hoogle 并不是唯一能够通过类型签名搜索 Haskell 库的搜索引擎，而且它肯定而且不幸地只涵盖了 Hackage 的一小部分。使用Hayoo搜索类型签名会[(a,b)]->[(a,[b])]出现以下两种实现：

关于你对这个问题的看法，因为在你的函数中你已经提出了一个更高级别的数据结构（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

Hayooing 对该类型签名也带来了一些已经实现的结果。

关于逼近问题，有句经典：“分而治之！” . 克里斯的回答也有一些优点。

于 2013-03-20T06:47:05.660 回答
3

这看起来是一个可以理解的解决方案，您可以稍微清理一下：

导入 Data.Map (toList, fromListWith)
导入 Control.Arrow（二）

convertKVList :: Ord a => [(a, b)] -> [(a, [b])]
转换KVList = toList 。来自ListWith (++) 。地图（第二个（：[]））

关于您如何自己想出这个：假设您从 开始Data.Map，那么您想使用映射将值与相等的键组合起来。Hackage的文档Data.Map说a是值和k键的类型。

知道了这一点，您可以搜索a -> a -> a以查找可能将 a 中的两个值组合Map k a以产生新a值的函数。这将 API 缩小到少数函数，如insertWith、fromListWith和fromAscListWith.

同样，要将您的转换Map k a为[(k, a)]，您可以搜索文档Map k a -> [(k, a)]并仅找到几个函数，例如assocs、toList、toAscList和toDescList。请注意，在您的情况下，[(k, a)]实例化为[(Int, [Int])].

我发现有助于理解标准 Haskell 库的一件事是查看 Hackage 上的源代码。查看哪些函数是根据其他函数实现的，有助于使 API 感觉更小，并且我可以看到哪些函数是基本构建块。

于 2013-03-20T06:54:53.647 回答
3

我怀疑如果不深入研究突变和ST单子，您不太可能改进Map.fromListWith解决方案（或基本等效的替代方案，如 using HashMap.fromListWith）。我会同意的。

a基本上，通过突变，您可以通过使用可变哈希表作为键和可变列表b作为值，在近乎线性的时间内完成此分组。然而，如果没有突变，情况会更糟，因为每个插入平衡的搜索树都是 O(log n); 这是因为“插入”意味着构建每个树节点的新副本，该副本通向您插入的元素进入的那个。并且您需要执行 n 次插入 - 这为您提供了Map.fromListWith函数的 O(n * log n) 边界有。提前对关联列表进行排序并不能从根本上改善这一点，因为排序也是 O(n * log n)。

因此，要改进 O(n * log n)，您需要具有突变的数据结构。我刚刚做了一个快速的谷歌，最好的选择是使用类似于hashtables库的东西来实现标准的命令式算法（我从未尝试过，所以我不能保证它）。要使用它，您需要了解Control.Monad.ST和Data.STRef. monad 是 GHC 提供的ST一种技术，用于在纯函数中“内部”使用突变——它使用一些类型系统扩展来保证在所讨论的函数之外无法观察到副作用。 HaskellWiki 有一些示例，但可能需要一些学习和实践才能对这个感到满意。

我建议的另一件事是，如果您想Data.Map更好地理解或类似的库，请查看 Chris Okasaki 的Purely Functional Data Structures书（或该书所基于的他的论文 (PDF)）。它基于标准 ML 而不是 Haskell，数据结构不一样，阅读起来可能有点困难，但它是一本基础书籍。

于 2013-03-20T07:43:41.157 回答
2

所以，我的解决方案过度使用了模式匹配，因为我实际上并不知道标准库中有哪些函数。

这个想法是，如果列表按键排序，那么您可以随时收集键值。为了执行检查是添加到第一个键值列表还是创建新条目的逻辑，我使用了模式和守卫来定义条件。并自由使用 cons 将值添加到列表中。

如果原始列表未排序，则有一个sortBy.

import Data.List
import Data.Ord

ls = [(2, 1), (1, 2), (1, 4), (1, 3), (2, 3)]

addval [] (k, v)= [(k, [v])]
addval ((k1, vals) : xs) (k2, v) | k1 == k2
  = ((k1, (v : vals)) : xs)
addval ls (k, v) = ((k, [v]) : ls)

convert ls = foldl addval [] (sortBy (comparing fst) ls)

丑陋的代码，但它避免使用 Map。

于 2013-03-20T04:02:08.087 回答