haskell - 如何使折叠根据类别执行多次折叠

Question

我可以将什么运算符传递给允许我在元组列表中对按元组项目 1 分组的元组项目 2 求和的折叠变体之一？

所以，假设我有 list :

[ ('A', 1) , ('A', 3) , ('B', 4 ) , ('C', 10) , ('C', 1) ]

我想生成列表:

[ ('A', 4) , ('B', 4) , ('C', 11) ]

你可以看到它是一个 Haskell 化的表，所以这里表的实际表示并不重要；这是获取输入数据并生成我感兴趣的输出的方法。我是 Haskell 新手，有 C/C++/C# 背景。我已经做了足够多的教程来识别 fold 在这里的应用，但无法弄清楚似乎需要的子折叠。

编辑:
如果这对其他人有帮助，这里是我使用 group、foldl1 和 map 的解决方案，灵感来自 ingo 的回应:

import qualified Data.List as List

mygroup :: [ (Char,Int) ] -> [ [(Char,Int)] ]
mygroup = List.groupBy (\x y -> fst x == fst y) 

myfold :: [(Char,Int)] -> (Char,Int)
myfold = foldl1 (\x y -> (fst x, snd x + snd y))

mysum :: [(Char,Int)] -> [(Char,Int)]
mysum = map myfold . mygroup

运行时:

*ListSum> mysum [ ('A',1) , ('A',2) , ('B',3) , ('C',4) , ('C',5) ]
[('A',3),('B',3),('C',9)]

我的群 展示了如何通过提供等价运算符来创建组。它表示如果两个成员的第一个元组项相同，则他们在同一个组中。

myfold 显示如何对两个元组求和。它使用列表中的第一个元组作为折叠的初始状态，并从每个元组的第二个项目的总和组成一个结果元组。

mysum 使用 map 组合这两个函数。

我可能会花更多的时间在这上面，看看我是否可以打破对数据模式的依赖，目前是 [(Char,Int)] .我认为这意味着提供 groupBy 运算符和 fold 运算符，并且可能只是组合 groupBy、foldl1 和 map 的练习。我是新手。

我可以因为没有积分而获得积分吗？ :)

Answer 1

您真正想要的是使用特定标准对项目进行分组，然后折叠这些组。

实现您给出的示例的最简单方法是使用来自 Data.Map 的关联映射。对项目进行分组。

import qualified Data.Map as Map

sumGroups :: [(Char, Int)] -> [(Char, Int)]
sumGroups = Map.assocs . Map.fromListWith (+)

这使用函数 fromListWith 组合具有相同键的项目，并将结果映射转换回带有 assocs 的列表.

*Main> sumGroups [ ('A', 1) , ('A', 3) , ('B', 4 ) , ('C', 10) , ('C', 1) ]
[('A',4),('B',4),('C',11)]