对具有相同键的所有元组求和（实现 Haskell Data.Map.fromListWith）

Question

我想对具有相同键的元组的值求和。

例如，

foo = [(True, 0), (True, 1), (False, 2), (True, -1), (False,4)] :: [(Bool, Int)]
putStrLn . show $ sumTuples foo

应该显示 [(False,6),(True,0)].

当然，这很容易做到Data.Map.fromListWith：

foo = [(True, 0), (True, 1), (False, 2), (True, -1), (False,4)] :: [(Bool, Int)]
putStrLn . show $ sumTuples foo

但我想在没有帮助的情况下实现它Data.Map。

使用过滤器，我可以这样解决：

sumTuples :: (Ord a, Num b) => [(a, b)] -> [(a, b)]
sumTuples = Map.toList . Map.fromListWith (+)

或带有折叠：

sumByFilter :: [(Bool, Int)] -> [(Bool, Int)]
sumByFilter xs =
  let trues = filter((==True) . fst) xs
      falses = filter((==False) . fst) xs
      summing = sum . map snd
  in [(True, summing trues), (False, summing falses)]

然而，在这两种情况下，我都将第一个参数硬编码为布尔值。但是，我希望能够对任何未预定义的键执行此操作 - 当然，如果我有字符串键，我无法对所有键进行模式匹配。

如何使我的代码具有通用性？

Answer 1

您必须按键排序，然后按键分组，然后对每个组求和：

sumThem = map sumGroup . groupBy fstEq . sortOn fst
  where
    sumGroup (x:xs) = (fst x, sum $ map snd (x:xs))
    sumGroup _ = error "This can never happen - groupBy cannot return empty groups"

    fstEq (a, _) (b, _) = a == b

请注意，排序是此处的基本操作，因为groupBy仅对连续元素进行分组。