列表 - 合并成对的元素

Question

列表 - 合并成对的元素

6

I want to make a function that takes a list eg

[('A',3), ('B',2), ('C',2), ('A',5), ('C',3), ('C',2)]

当字母相同时，将数字相加。因此，上述输入将产生以下结果。

[('A',8), ('B',2), ('C',7)].

有人能给我一个想法，如何处理这个问题，我想尽可能多地自己尝试！

- L.R88

4个回答

3

首先，将问题拆分成更小的部分。

忽略额外的条件。最终目标是什么？把一些数字加在一起，你可能已经知道如何做了。

但是你不想加上所有的数字，那么如何知道哪些数字需要相加呢？看看字母是否匹配。因此，你需要以某种方式进行比较。

所以一旦你知道如何添加数字，并决定是否应该添加任何两个数字，你需要一种处理整个列表的方法。如果它们被混合在一起，你就走不远，所以你需要根据哪些数字需要相加来分离事物。你可以通过创建子列表一次性完成所有操作，也可以逐个过滤，还可以使用其他各种方法，其中一些可能比其他方法效率更高或更低。

这就是基本思路。因此，回顾一下这些步骤，你从一个列表开始，根据比较字母将项目分组，然后添加每个结果组中的所有数字。

显然，我跳过了一些步骤——例如如何在元组结合时同时比较字母和添加数字——因为你说过你宁愿自己解决问题。 :]

- C. A. McCann

3

除了优秀的基于Map的解决方案外，我认为纯列表解决方案也可以非常有启发性。与Map一样，有趣的部分是将具有相同第一个元素的元素分组在一起。有一个内置函数group（以及其广义版本groupBy），它将相邻的元素合并：

groupBy :: (a -> a -> Bool) -> [a] -> [[a]]

第一个参数告诉我们何时合并两个元素。例如：

> groupBy (\x y -> odd x == odd y) [1,1,3,4,6,5,7]
[[1,1,3],[4,6],[5,7]]

很不幸，我们可以在这里看到，它仅合并相邻元素，因此我们需要先找到一种将原始列表中具有相等键的元素捆绑在一起的方法。有另一个内置函数可以做到这样：sort。最后的技巧是汇总所有具有相等第一个元素的块的第二个元素。让我们编写一个函数，只假设传递了一个具有相等第一个元素的非空块：

sumSnds :: Num b => [(a,b)] -> (a,b)
sumSnds abs = (a, sum bs) where
    (a:_, bs) = unzip abs

现在我们可以将所有这些部分串联起来：

solution :: (Ord a, Ord b, Num b) => [(a,b)] -> [(a,b)]
solution = map sumSnds . groupBy (\x y -> fst x == fst y) . sort

- Daniel Wagner

1

有几种方法可以解决这个问题，Adam已经给出了一种基于映射的高效方法。然而，我认为只使用列表和递归的解决方案也会很有启发性，特别是在学习Haskell时。既然你已经得到了答案，我希望我可以在这里写出一个解决方案，而不会泄露任何东西。

我处理这个问题的方式是考虑如何将输入列表减少到输出列表。我们从以下内容开始

[('A',3), ('B',2), ('C',2), ('A',5), ('C',3), ('C',2)]

目标是得到一个结果列表，其中每个元组都以一个唯一的字符开头。可以逐步构建这样的结果列表：从空列表开始，然后将元组插入列表中，确保不重复字符。类型将是

insertInResult :: (Char, Integer) -> [(Char, Integer)] -> [(Char, Integer)]

它需要像 ('A',3) 这样的一对数据，并将其插入到现有的唯一数据对列表中。结果是一个新的唯一数据对列表。可以按如下方式完成：

insertInResult (c, n) [] = [(c, n)]
insertInResult (c, n) ((c', n'):results)
  | c == c'   = (c, n + n') : results
  | otherwise = (c', n') : (insertInResult (c, n) results)

解释：将元组插入空结果列表很容易，只需插入即可。如果结果列表不为空，则我们通过模式匹配获取第一个结果 (c'，n')。我们检查字符是否与保护条件匹配，如果是，则添加数字。否则，我们只需复制结果元组并将(c，n)元组插入剩余的结果中。

现在我们可以这样做

*Main> insertInResult ('A',3) []
[('A',3)]
*Main> insertInResult ('B',2) [('A',3)]
[('A',3),('B',2)]

下一步是在输入列表上重复使用insertInResult，以便我们建立一个结果列表。我将这个函数称为sumPairs'，因为我将顶层函数称为sumPairs：

sumPairs' :: [(Char, Integer)] -> [(Char, Integer)] -> [(Char, Integer)]
sumPairs' [] results = results
sumPairs' (p:pairs) results = sumPairs' pairs (insertInResult p results)

这是一个简单的函数，只需在第一个参数上进行迭代，并将每个对插入到结果列表中。最后一步是使用空结果列表调用此辅助函数：

sumPairs :: [(Char, Integer)] -> [(Char, Integer)]
sumPairs pairs = sumPairs' pairs []

它运作了！:-)

*Main> sumPairs [('A',3), ('B',2), ('C',2), ('A',5), ('C',3), ('C',2)]
[('A',8),('B',2),('C',7)]

这个解决方案的复杂度不如基于 Data.Map 的解决方案好。对于一个包含 n 对的列表，我们从 sumPairs' 中调用 insertInResult n 次。每次调用 insertInResult 都可能最多迭代 n 次，直到找到匹配的结果元组或者到达结果的末尾。这给出了 O(n²) 的时间复杂度。基于 Data.Map 的解决方案将具有 O(n log n) 的时间复杂度，因为它使用 log n 的时间来插入和更新每个 n 元素。

请注意，如果您对输入列表进行排序，然后扫描一次以添加相邻元组中相同字符的总和，则会得到相同的复杂度。

sumPairs pairs = sumSorted (sort pairs) []

sumSorted [] result = result
sumSorted (p:pairs) [] = sumSorted pairs [p]
sumSorted ((c,n) : pairs) ((c',n') : results)
  | c == c'   = sumSorted pairs ((c,n + n') : results)
  | otherwise = sumSorted pairs ((c,n) : (c',n') : results)

- Martin Geisler

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Adam Wagner · Accepted Answer

您可以使用 Data.Map 的 fromListWith 函数来构建一个对值求和的映射表。该函数的类型如下所示：

fromListWith :: Ord k => (a -> a -> a) -> [(k, a)] -> Map k a

它需要一个键值对列表（如您所述）作为第一个参数，如果它看到重复项，则使用某个函数（第一个参数）将原始值与新值组合。从那里，您可以将此映射转换回键值对列表（也是Data.Map中的函数）。

您可以使用纯列表来完成此操作，但可能不太有效率，因为您将经常构建一个新列表（或其部分）。