How to make fold perform multiple folds based on a category

Question

What operator can I pass to one of the fold variants that will allow me to sum tuple item 2 grouped by tuple item 1, in a list of tuples?

So, let's say I have the list:

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

and I want to produce the list:

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

You can see it's a Haskell-ized table, and so the actual representation of the table here isn't important; it's the approach to taking the input data and producing the output I am interested in. I am a Haskell newcomer, and have a background in C/C++/C#. I've done enough tutorials to recognise the application of fold here, but can't figure out the sub-folding that appears to be required.

EDIT: In case this helps anyone else, here is my solution using group, foldl1 and map, inspired by ingo's response:

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

When run:

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

mygroup shows how to create groups, by providing an equivalence operator. It says that two members are in the same group if their first tuple items are the same.

myfold shows how to sum two tuples. It uses the first tuple in the list as the initial state for the fold, and composes a result tuple from the the sum of each tuple's second items.

mysum composes these two functions using map.

I might spend a bit more time on this to see if I can break the dependence on the schema of the data, which is currently [(Char,Int)]. I think it means supplying the groupBy operator and the fold operator, and might just be an exercise in composing the groupBy, foldl1 and map. I'm new at this.

Do I get any points for being point-free? :)

Answer 1

What you want is really about grouping items with a specific criteria and then folding over the groups.

The simplest way to implement the example you gave is to use an associative map from Data.Map to group the items.

import qualified Data.Map as Map

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

This uses the function fromListWith to combine items which have the same key, and the resulting map is converted back into a list with assocs.

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