Lists - pairing

Question

I want to make a function that takes a list like

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

and then adds the numbers together when the letter matches. Thus, the above input would lead to

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

Can someone please just give me an idea of ​​how to approach this, I would like to try to make as much of myself as possible!

Answer 1

You can use Data.Map fromListWith to build a map with summed values. This is the type:

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

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

You can do this with clean lists, but it probably won't be as efficient as you will create a new list (or parts of it) quite often.

Answer 2

Well, start by breaking down the problem into smaller parts.

First, ignore the additional condition. What is the ultimate goal? Adding multiple numbers together, and you probably know how to do this already.

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

So, as soon as you know how to add numbers, and decide whether to add two numbers, you need a way to solve the whole list. You will not be mixed with anyone, so you need to separate things based on which numbers to add. You can do this all at once by creating sub-lists, or you can filter one at a time or various other approaches, some of which may be more or less effective than others.

This is the main idea, anyway. So, let's repeat the steps, you start with a list, you select groups of elements based on a comparison of letters, and then add all the numbers to each resulting group.

I obviously skipped a few steps - for example, how to compare letters and add numbers when they are combined in the form of tuples - since you said that you would have figured it out yourself .:]

Answer 3

In addition to the excellent Map based solution, I think that a purely oriented solution can be very instructive. As with Map , an interesting bit groups these elements with the same first element. There is a built-in group function (and its generic version of groupBy ) that combines related elements:

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

The first argument indicates when to combine the two elements. For instance:

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

Unfortunately, as we see here, it only combines adjacent elements, so we need to find a way to first group the elements of the source list so that those with the same keys are next to each other. There is another built-in function to do something like this: sort . The final trick is to summarize the second element of the pieces that all have equal first elements. Let me write a function that simply assumes that it passed a non-empty piece with all the first elements equal:

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

Now we can combine all these parts:

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

Answer 4

There are several ways to solve this problem, and Adam has already given you an efficient map-based method. However, I think that a solution using only lists and recursion would also be instructive, especially when learning Haskell. Since you already received the answer, I hope I can write a solution here without messing up anything.

The way I approached this is to think about how we can reduce the input list in the output list. Start with

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

The goal is to end the list of results, where each tuple begins with a unique character. Building such a list of results can be done gradually: start with an empty list, and then insert tuples into the list, making sure that you do not duplicate characters. Type will be

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

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

 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 list of results is not empty, we will get the first result (c', n') with comparison with the sample. We check to see if the characters match the guard, and add numbers, if so. Otherwise, we simply copy the tuple of the result and paste the tuple (c, n) into the remaining results.

Now we can do

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

The next step is to use insertInResult several times in the input list so that we create a list of results. 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) 

This is a simple function that simply iterates over the first argument and inserts each pair into a list of results. The final step is to call this helper function with an empty list of results:

 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 that based on Data.Map . For a list with n pairs, we call insertInResult n times from sumPairs' . Each insertInResult call can be repeated up to n times until it finds the corresponding result or reaches the end of the results. This gives a time complexity of O (n²). A 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 n elements.

Note that this will be the same complexity you would get if you sorted the input list and then scanned it once to add 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)