Lists - combining pairs

Question

I want to make a function that takes a list eg

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

and then adds the numbers together when the letter is the same. So the above input would produce

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

Could someone please just give me an idea of how to approach this, I'd like to try and do as much as possible myself!

Answer 1

In addition to the excellent Map-based solution, I think a purely list-based solution can be quite instructive. As with a Map, the interesting bit is grouping together those elements with the same first element. There's a built-in function group (and its generalized version groupBy) that coalesces adjacent elements:

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

The first argument tells when to coalesce two elements. For example:

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

Unfortunately, as we can see here, it only coalesces adjacent elements, so we need to find a way to bunch up the elements of the original list first so that those with equal keys are next to each other. There's another built-in function for doing something like that: sort. The final trick is to sum up the second elements of chunks that all have equal first elements. Let's write a function that just assumes it's passed a non-empty chunk with all equal first elements:

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

Now we can string all these pieces together:

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

Answer 2

There are several ways to solve this and Adam has already given you an efficient way based on maps. However, I think a solution using only lists and recursion would also be instructive, especially when learning Haskell. Since you've already gotten an answer I hope I can write a solution here without spoiling anything.

The way I approached this is to think of how we can reduce the input list to the output list. We start with

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

The goal is to end up with a result list where each tuple starts with a unique character. Building such a result list can be done incrementally: Start with an empty list, and then insert tuples into the list, making sure not to duplicate the characters. The type would be

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

It takes the pair, like ('A',3) and inserts it into an existing list of unique pairs. The result is a new list of unique pairs. This can be done like this:

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

Explanation: inserting a tuple into an empty result list is easy, just insert it. If the result list is not empty, then we get hold of the first result (c', n') with pattern matching. We check if the characters match with the guard, and add the numbers if so. Otherwise we just copy the result tuple and insert the (c, n) tuple into the remaining results.

We can now do

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

Next step is to use insertInResult repeatedly on the input list so that we build up a result list. I called this function sumPairs' since I called the top-level function sumPairs:

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

It's a simple function that just iterates on the first argument and inserts each pair into the result list. The final step is to call this helper function with an empty result list:

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

It works! :-)

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

The complexity of this solution is not as good as the one based on Data.Map. For a list with n pairs, we call insertInResult n times from sumPairs'. Each call to insertInResult may iterate up to n times until it finds a matching result tuple, or reaches the end of the results. This gives a time complexity of O(n²). The solution based on Data.Map will have O(n log n) time complexity since it uses log n time to insert and update each of the n elements.

Note that this is the same complexity you would have gotten if you had sorted the input list and then scanned it once to add up adjacent tuples with the same character:

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)

Answer 3

You can use Data.Map's fromListWith to construct a map that has the summed values. It's type is this:

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

It takes a list of pairs (as you described) as the first arg, if it sees a duplicate, it uses some function (the first arg), to combine the original value with a new one. From there, you can convert this map back into a list of pairs (also a function in Data.Map).

You could do this with pure lists, but it probably won't be that effecient, as you'll be constructing a new list (or portions of it) quite often.

Answer 4

Well, start by breaking the problem down to smaller pieces.

First, ignore the extra condition. What's the final goal? Adding some numbers together, and you probably know how to do that already.

But you don't want to add all the numbers, how do you know which ones to add? See if the letters match. So you need to compare them somehow.

So once you know how to add numbers, and decide whether you should add any two numbers, you need a way to tackle the whole list. You won't get anywhere with them all mixed together, so you need to separate things based on which numbers to add. You could do this all at once by creating sublists, or you could filter one at a time, or various other approaches, some of which may be more or less efficient than others.

That's the basic idea, anyway. So, going back through the steps, you start with a list, you separate out groups of items based on the comparing letters, then add all the numbers in each resulting group.

I've obviously skipped a few steps--such as how to both compare letters and add numbers when they're combined as tuples--since you did say you'd rather figure things out on your own. :]